2026-07-24T08:31:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7224 2024-03-06T10:40:01Z ddc:004 open_access

Erdös-Hajnal Conjecture for Graphs with Bounded VC-Dimension Fox, Jacob Pach, János Suk, Andrew VC-dimension Ramsey theory regularity lemma 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 - 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, 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(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 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(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 in the k-uniform setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jacob Fox and János Pach and Andrew Suk 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.43 urn:nbn:de:0030-drops-72246 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.43 eng https://creativecommons.org/licenses/by/3.0/legalcode