Erdos-Hajnal conjecture for graphs with bounded VC-dimension

DOI10.4230/LIPICS.SOCG.2017.43zbMATH Open1432.05065arXiv1710.03745OpenAlexW2920461028MaRDI QIDQ4580118FDOQ4580118

Authors: Jacob Fox, János Pach, Andrew Suk 

Publication date: 13 August 2018

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, $e^{csqrtlogn}$, 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^{Omega(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 Lov'asz-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/varepsilon{)}^{O(d)}$, improving the original bound of $(1/varepsilon{)}^{O(d^2)}$ 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(n^k)$-time algorithm for finding a partition meeting the requirements. Finally, we establish tight bounds on Ramsey-Tur'an numbers for graphs with bounded VC-dimension.

Full work available at URL: https://arxiv.org/abs/1710.03745

Recommendations

• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• Bounded VC-Dimension Implies the Schur-Erdős Conjecture
• Erdős-Hajnal-type theorems in hypergraphs
• Vertex-minors and the Erdős-Hajnal conjecture
• Bounded \(VC\)-dimension implies the Schur-Erdős conjecture
• The Erdős-Sós conjecture for geometric graphs
• The Erdős-Faber-Lovász conjecture for dense hypergraphs
• The Erdős-Faber-Lovász conjecture for weakly dense hypergraphs
• Adjacency properties of graphs and a conjecture of Erdős
• The Erdős-Hajnal conjecture for bull-free graphs

zbMATH Keywords

Ramsey theoryregularity lemmaVC-dimension

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Generalized Ramsey theory (05C55) Erd?s problems and related topics of discrete geometry (52C10) Ramsey theory (05D10)

Cited In (12)

• On low rank-width colorings
• VC-dimension and Erdős-Pósa property
• Caterpillars in Erdős-Hajnal
• The removal lemma for tournaments
• The Erdős–Faber–Lovász conjecture for the class of δEFL graphs
• Large cliques or cocliques in hypergraphs with forbidden order-size pairs
• Erdős-Lovász Tihany conjecture for graphs with forbidden holes
• Induced Turán problem in bipartite graphs
• On the VC-dimension of uniform hypergraphs
• Hitting Set for hypergraphs of low VC-dimension
• Bounded VC-Dimension Implies the Schur-Erdős Conjecture
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension

This page was built for publication: Erdos-Hajnal conjecture for graphs with bounded VC-dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580118)