Induced subgraph density. VI: Bounded VC-dimension

DOI10.1016/J.AIM.2025.110601MaRDI QIDQ6889812zbMATH OpenFDO

Authors Tung Nguyen, Alex Scott, Paul Seymour

Publication date 4 December 2025

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.AIM.2025.110601

zbMATH Keywords

Erdős-Hajnal conjectureinduced subgraphsVC-dimension

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45) Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Ramsey theory (05D10)

Cites work

• A Guide to NIP Theories
• A note on ``Regularity lemma for distal structures
• A note on the Erdős-Hajnal property for stable graphs
• A Ramsey-Type Result for Convex Sets
• About the Erdős-Hajnal conjecture for seven-vertex tournaments
• Bounded VC-dimension implies the Schur-Erdős conjecture
• Combinatorial complexity in o-minimal geometry
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Crossing patterns of semi-algebraic sets
• Domination in tournaments
• Edge Distribution of Graphs with Few Copies of a Given Graph
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• EH-suprema of tournaments with no nontrivial homogeneous sets
• Erdös–Hajnal conjecture for new infinite families of tournaments
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• Erdős–Hajnal for graphs with no 5‐hole
• Forcing large transitive subtournaments
• How many ways can one draw a graph?
• scientific article; zbMATH DE number 3628985 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 970798 (Why is no real title available?)
• scientific article; zbMATH DE number 7731176 (Why is no real title available?)
• Identifying codes in hereditary classes of graphs and VC-dimension
• Induced Ramsey-type theorems
• Induced subgraph density. I: A loglog step towards Erdős-Hajnal
• Intersection patterns of curves
• NOTES ON THE STABLE REGULARITY LEMMA
• On Rödl's theorem for cographs
• On the Erdős-Hajnal conjecture for six-vertex tournaments
• On the number of zero-patterns of a sequence of polynomials
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the Zarankiewicz problem for graphs with bounded VC-dimension
• On unavoidable-induced subgraphs in large prime graphs
• On universality of graphs with uniformly distributed edges
• Partition relations for cardinal numbers
• Ramsey growth in some NIP structures
• Ramsey properties of algebraic graphs and hypergraphs
• Ramsey-type results for semi-algebraic relations
• Ramsey-type theorems
• Ramsey-type theorems with forbidden subgraphs
• Regularity lemma for distal structures
• Regularity lemmas for stable graphs
• Regularity partitions and the topology of graphons
• String graphs have the Erdős-Hajnal property
• Sunflowers in set systems of bounded dimension
• The 3 and 4-dichromatic tournaments of minimum order
• The Erdős-Hajnal conjecture. A survey

Cited in

(3)

• Induced subgraph density. VII: The five-vertex path
• Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity
• Sublinear hitting sets for some geometric graphs

This page was built for publication: Induced subgraph density. VI: Bounded VC-dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6889812)