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.
Upcoming Seminars
April 1, 2022, 4-5pm, W303 - Zilin Jiang, Arizona State University
Title: Forbidden subgraphs and spherical two distance sets
Abstract: Given a real number λ, what can we say about the family G(λ) of graphs with eigenvalues bounded from below by -λ? The Cauchy interlacing theorem implies that that the family G(λ) is closed under taking (induced) subgraphs. Similar to Wagner’s theorem, which describes the family of planar graphs by finite forbidden minors, it is natural to ask for which λ the family G(λ) has a finite forbidden subgraph characterization. In this talk, I will illustrate the key ideas in answering this question, and I will demonstrate a peculiar connection to spherical two distance sets — a set of unit vectors in a Euclidean space the pairwise inner products of which assume only two values. Joint work with Alexandr Polyanskii, Jonathan Tidor, Yuan Yao, Shengtong Zhang and Yufei Zhao.
April 13, 2022 - Alexey Pokrovskiy, University College of London
Past Seminars
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.