For most graphs H , most H -free graphs have a linear homogeneous set
From MaRDI portal
Publication:2930050
DOI10.1002/rsa.20488zbMath1302.05116OpenAlexW2022319070MaRDI QIDQ2930050
Ross J. Kang, Bruce A. Reed, Alexander D. Scott, Colin J. H. McDiarmid
Publication date: 17 November 2014
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20488
Combinatorial aspects of partitions of integers (05A17) Hypergraphs (05C65) Generalized Ramsey theory (05C55)
Related Items
Linear-sized independent sets in random cographs and increasing subsequences in separable permutations, Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons, Forbidding induced even cycles in a graph: typical structure and counting
Cites Work
- The structure of almost all graphs in a hereditary property
- Excluding induced subgraphs. II: Extremal graphs
- Erdős-Hajnal-type theorems in hypergraphs
- A new upper bound for diagonal Ramsey numbers
- Ramsey-type theorems
- The Erdős-Hajnal conjecture for bull-free graphs
- Density theorems for bipartite graphs and related Ramsey-type results
- A note on the chromatic number of a dense random graph
- Asymptotics of random partitions of a set
- Non-Ramsey graphs are \(c\log n\)-universal
- The unlabelled speed of a hereditary graph property
- Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
- Excluding induced subgraphs: Critical graphs
- Poisson approximation for large deviations
- Excluding Induced Subgraphs III: A General Asymptotic
- Almost all Berge Graphs are Perfect
- Some remarks on the theory of graphs
- Induced Ramsey-type theorems
- The chromatic number of random graphs
- Ramsey-type theorems with forbidden subgraphs
- On the chromatic number of random graphs
