The typical structure of sparse $K_{r+1}$-free graphs

DOI10.1090/tran/6552zbMath1332.05083arXiv1307.5967OpenAlexW3101177936WikidataQ103203936 ScholiaQ103203936MaRDI QIDQ2790735

József Balogh, Robert Morris, Lutz Warnke, Wojciech Samotij

Publication date: 8 March 2016

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.5967

zbMATH Keywords

\(H\)-free graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Asymptotic enumeration (05A16) Density (toughness, etc.) (05C42)

Related Items

Making K_r+1-free graphs r-partite, Integer colorings with no rainbow 3-term arithmetic progression, The number of the maximal triangle-free graphs, Upper tails via high moments and entropic stability, On the probability of nonexistence in binomial subsets, The exponential growth of the packing chromatic number of iterated Mycielskians, The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups, The Structure of Typical Eye-Free Graphs and a Turán-Type Result for Two Weighted Colours, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Forbidding induced even cycles in a graph: typical structure and counting, An efficient container lemma, Independent sets in hypergraphs, Exact stability for Turán’s Theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extremal results for random discrete structures
• Combinatorial theorems in sparse random sets
• Almost all triangle-free triple systems are tripartite
• On the KŁR conjecture in random graphs
• Hypergraph containers
• The fine structure of octahedron-free graphs
• The structure of almost all graphs in a hereditary property
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• The asymptotic number of graphs not containing a fixed color-critical subgraph
• On \(K^ 4\)-free subgraphs of random graphs
• The number of graphs without forbidden subgraphs
• For which densities are random triangle-free graphs almost surely bipartite?
• Almost all triple systems with independent neighborhoods are semi-bipartite
• Ramsey properties of random discrete structures
• Excluding induced subgraphs: Critical graphs
• Extremal subgraphs of random graphs
• Mantel's theorem for random graphs
• The typical structure of graphs without given excluded subgraphs
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Sharp thresholds of graph properties, and the $k$-sat problem
• Extremal Graph Problems for Graphs with a Color-Critical Vertex
• Random I‐colorable graphs
• Rado Partition Theorem for Random Subsets of Integers
• On triangle-free random graphs
• On the Evolution of Triangle-Free Graphs
• Extremal subgraphs of random graphs
• On the asymptotic structure of sparse triangle free graphs
• Threshold Functions for Ramsey Properties
• Arithmetic progressions of length three in subsets of a random set
• Independent sets in hypergraphs
• Probability Inequalities for Sums of Bounded Random Variables
• Stability results for random discrete structures
• Extremal Results in Random Graphs
• The two possible values of the chromatic number of a random graph