Abstract
The VapnikChervonenkis dimension (in short, VCdimension) of a graph is defined as the VCdimension of the set system induced by the neighborhoods of its vertices. We show that every nvertex graph with bounded VCdimension contains a clique or an independent set of size at least e^{(log n)^{1  o(1)}}. The dependence on the VCdimension 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 ErdosHajnal 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 Ramseytype properties.
Our main tool is a partitioning result found by LovaszSzegedy and AlonFischerNewman, which is called the "ultrastrong regularity lemma" for graphs with bounded VCdimension. We extend this lemma to kuniform 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 kuniform setting.
BibTeX  Entry
@InProceedings{fox_et_al:LIPIcs:2017:7224,
author = {Jacob Fox and J{\'a}nos Pach and Andrew Suk},
title = {{Erd{\"o}sHajnal Conjecture for Graphs with Bounded VCDimension}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {43:143:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7224},
URN = {urn:nbn:de:0030drops72246},
doi = {10.4230/LIPIcs.SoCG.2017.43},
annote = {Keywords: VCdimension, Ramsey theory, regularity lemma}
}
Keywords: 

VCdimension, Ramsey theory, regularity lemma 
Collection: 

33rd International Symposium on Computational Geometry (SoCG 2017) 
Issue Date: 

2017 
Date of publication: 

20.06.2017 