Erdos-hajnal conjecture for graphs with bounded VC-Dimension

Fox, Jacob and Pach, János and Suk, Andrew (2017) Erdos-hajnal conjecture for graphs with bounded VC-Dimension. In: 33rd International Symposium on Computational Geometry, SoCG 2017. Leibniz International Proceedings in Informatics, LIPIcs (77). Schloss Dagstuhl Leibniz-Zentrum für Informatik, Dagstuhl, pp. 1-19. ISBN 9783959770385

Preview	Text 1710.03745v1.pdf - Draft Version Download (259kB) | Preview
Preview	Text LIPIcs-SoCG-2017-43.pdf - Published Version Available under License Creative Commons Attribution. Download (518kB) | Preview

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. We show that every n-vertex graph with bounded VC-dimension contains a clique or an independent set of size at least e(log n)1-σ(1). The dependence on the VC-dimension is hidden in the o(1) term. This improves the general lower bound, ec√log n due to Erdos and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our 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Ω(log n). Our results partially explain why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties. Our main tool is a partitioning result found by Lovász-Szegedy and Alon-Fischer-Newman, which is called the "ultra-strong regularity lemma" for graphs with bounded VC-dimension. We extend this lemma to k-uniform hypergraphs, and prove that the number of parts in the partition can be taken to be (1/ϵ)O(d) improving the original bound of (1/ϵ) O(d2) in the graph setting. We show that this bound is tight up to an absolute constant factor in the exponent. Moreover, we give an O(nk)-time algorithm for finding a partition meeting the requirements in the k-uniform setting. © Jacob Fox, János Pach, and Andrew Suk.

Actions (login required)

Edit Item