For most graphs H , most H -free graphs have a linear homogeneous set

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

zbMATH Keywords

hypergraphsfinite graphsRamsey-type problems\(r\)-partitions

Mathematics Subject Classification ID

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