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 (8)
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
- 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
- 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
This page was built for publication: Erdős-Hajnal conjecture for graphs with bounded VC-dimension
