Erdős-Hajnal Conjecture for Graphs with Bounded VC-Dimension

Fox, Jacob and Pach, János and Suk, Andrew (2019) Erdős-Hajnal Conjecture for Graphs with Bounded VC-Dimension. DISCRETE AND COMPUTATIONAL GEOMETRY, 61 (4). pp. 809-829. ISSN 0179-5376

Preview

Text 171003745.pdf Available under License Creative Commons Attribution. Download (259kB) | 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(logn)1-o(1). The dependence on the VC-dimension is hidden in the o(1) term. This improves the general lower bound, eclogn, due to Erds 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 Erds-Hajnal conjecture, according to which one can always find a clique or an independent set of size at least e(logn). 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 Lovasz-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/epsilon)O(d), improving the original bound of (1/epsilon)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. Finally, we establish tight bounds on Ramsey-Turan numbers for graphs with bounded VC-dimension.

Actions (login required)

Edit Item