Combinatorics and Probability Seminar

Andrew Suk
Erdos-Hajnal conjecture for graphs with bounded VC-dimension
Abstract: The Vapnik-Chervonenkis dimension (in short, VC-dimension) of a graph is defined as the VC-dimension of the set system induced by the neighborhoods of its vertices. In this talk, I will sketch a proof showing that every $n$-vertex graph with bounded VC-dimension contains a clique or an independent set of size at least $e^{(\log n)^{1 - o(1)}}$. The dependence on the VC-dimension is hidden in the $o(1)$ term. This improves the general lower bound, $e^{c\sqrt{\log n}}$, due to Erdos and Hajnal. This result is almost optimal and nearly matches the celebrated Erdos-Hajnal conjecture, according to which one can always find a clique or an independent set of size at least $e^{\Omega(\log n)}$ If time permits, I will also discuss a multicolor Ramsey theorem for graphs with bounded VC-dimension. This is joint work with Jacob Fox and Janos Pach.
Thursday February 6, 2020 at 2:00 PM in 1227 SEO
Web Privacy Notice HTML 5 CSS FAE
UIC LAS MSCS > persisting_utilities > seminars >