Erdős-Hajnal conjecture for graphs with bounded VC-dimension
From MaRDI portal
Publication:2415381
DOI10.1007/s00454-018-0046-5zbMath1411.05179OpenAlexW2963468679WikidataQ123305545 ScholiaQ123305545MaRDI QIDQ2415381
János Pach, Andrew Suk, Jacob Fox
Publication date: 21 May 2019
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-018-0046-5
Generalized Ramsey theory (05C55) Erd?s problems and related topics of discrete geometry (52C10) Ramsey theory (05D10)
Related Items
Structure and regularity for subsets of groups with finite VC-dimension, Ramsey properties of algebraic graphs and hypergraphs, Nondegenerate spheres in four dimensions, Large homogeneous subgraphs in bipartite graphs with forbidden induced subgraphs, Minimum degree and the graph removal lemma, Regular partitions of gentle graphs, Bounded \(VC\)-dimension implies the Schur-Erdős conjecture, DOMINATION AND REGULARITY
Cites Work
- More results on Ramsey-Turán type problems
- Ramsey-type theorems
- The early evolution of the \(H\)-free process
- Density theorems for bipartite graphs and related Ramsey-type results
- \(\epsilon\)-nets and simplex range queries
- A note on Ramsey numbers
- Almost tight bounds for \(\epsilon\)-nets
- On a Ramsey-Turán type problem
- Asymptotic lower bounds for Ramsey functions
- Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- The VC-dimension of set systems defined by graphs
- The Vapnik-Chervonenkis dimension of a random graph
- Random regular tournaments
- Combinatorics and commutative algebra.
- Bounds for graph regularity and removal lemmas
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Some extremal properties concerning transitivity in graphs
- Crossing patterns of semi-algebraic sets
- A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing
- Regularity partitions and the topology of graphons
- Overlap properties of geometric expanders
- Ramsey-type results for semi-algebraic relations
- On Certain Sets of Positive Density
- Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
- Hypergraph Ramsey numbers
- A Ramsey-Type Result for Convex Sets
- Density and regularity theorems for semi-algebraic hypergraphs
- Partition relations for cardinal numbers
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Some remarks on the theory of graphs
- Combinatorial Theorems on Classifications of Subsets of a Given Set
- Ramsey-Turán theory
- Ramsey-type theorems with forbidden subgraphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
