Emory Discrete Mathematics Seminars
When: bi-weekly Wednesdays 4-5pm
Note that the time and the place are subject to change based on speaker's or attendees' availability, always double-check on a particular date.
April 1, 2022, 4-5pm, W303 - Zilin Jiang, Arizona State University
April 13, 2022 - Alexey Pokrovskiy, University College of London
March 16, 2022, E406 - Anton Bernshteyn, Georgia Tech
Title: Weak degeneracy of graphs
Abstract: Motivated by the study of greedy algorithms for graph coloring, we introduce a new graph parameter, which we call weak degeneracy. This notion formalizes a particularly simple way of "saving" colors while coloring a graph greedily. It turns out that many upper bounds on chromatic numbers follow from corresponding bounds on weak degeneracy. In this talk I will survey some of these bounds as well as state a number of open problems. This is joint work with Eugene Lee (Carnegie Mellon University).
February 23, 2022, W303 - Bharghav Narayanan , Rutgers University
Title: Probabilistic Bezout over finite fields, and some applications
Abstract: What is the distribution of the number of distinct roots of k random polynomials (of some fixed degree) in k variables? I will talk about a recently proved Bezout-like theorem that gives us a satisfactory answer over (large) finite fields. This result can be used to construct several interesting families of “extremal graphs”. I shall illustrate this method by 1) discussing the easiest applications in detail, reproving some well-known lower bounds in extremal graph theory, and 2) outlining how this method has recently found applications in establishing hardness results for a few basic computational problems.