Combinatorics and Probability Seminar
Andrew Suk
UCSD
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