License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.43
URN: urn:nbn:de:0030-drops-72246
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7224/
Fox, Jacob ;
Pach, János ;
Suk, Andrew
Erdös-Hajnal Conjecture for Graphs with Bounded VC-Dimension
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 - 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.
BibTeX - Entry
@InProceedings{fox_et_al:LIPIcs:2017:7224,
author = {Jacob Fox and J{\'a}nos Pach and Andrew Suk},
title = {{Erd{\"o}s-Hajnal Conjecture for Graphs with Bounded VC-Dimension}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {43:1--43:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-038-5},
ISSN = {1868-8969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7224},
URN = {urn:nbn:de:0030-drops-72246},
doi = {10.4230/LIPIcs.SoCG.2017.43},
annote = {Keywords: VC-dimension, Ramsey theory, regularity lemma}
}
|
Keywords: |
|
VC-dimension, Ramsey theory, regularity lemma |
|
Collection: |
|
33rd International Symposium on Computational Geometry (SoCG 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
20.06.2017 |
