The typical structure of sparse K_r+1-free graphs

DOI10.1090/TRAN/6552MaRDI QIDQ2790735zbMATH OpenOpenAlexWikidataFDO

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

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

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

Abstract: Two central topics of study in combinatorics are the so-called evolution of random graphs, introduced by the seminal work of ErdH{o}s and R'enyi, and the family of $H$-free graphs, that is, graphs which do not contain a subgraph isomorphic to a given (usually small) graph $H$. A widely studied problem that lies at the interface of these two areas is that of determining how the structure of a typical $H$-free graph with $n$ vertices and $m$ edges changes as $m$ grows from $0$ to $extex(n,H)$. In this paper, we resolve this problem in the case when $H$ is a clique, extending a classical result of Kolaitis, Pr"omel, and Rothschild. In particular, we prove that for every $rge2$, there is an explicit constant $het{a}_r$ such that, letting $$, the following holds for every positive constant $varepsilon$. If $mge(1+varepsilon)m_r$, then almost all $K_{r+1}$-free $n$-vertex graphs with $m$ edges are $r$-partite, whereas if $nllmle(1-varepsilon)m_r$, then almost all of them are not $r$-partite.

Recommendations

• The typical structure of graphs with no large cliques
• On the structure of clique-free graphs
• Many cliques in \(H\)-free subgraphs of random graphs
• A stability theorem for maximal \(K_{r+1}\)-free graphs
• The typical structure of graphs without given excluded subgraphs

Cites work

• Almost all hypergraphs without Fano planes are bipartite
• Almost all triangle-free triple systems are tripartite
• Almost all triple systems with independent neighborhoods are semi-bipartite
• Arithmetic progressions of length three in subsets of a random set
• Combinatorial theorems in sparse random sets
• Excluding induced subgraphs: critical graphs
• Extremal Graph Problems for Graphs with a Color-Critical Vertex
• Extremal results for random discrete structures
• Extremal results in random graphs
• Extremal subgraphs of random graphs
• Extremal subgraphs of random graphs
• For which densities are random triangle-free graphs almost surely bipartite?
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3557819 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1380613 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Hypergraph containers
• Independent sets in hypergraphs
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• Mantel's theorem for random graphs
• On \(K^ 4\)-free subgraphs of random graphs
• On the asymptotic structure of sparse triangle free graphs
• On the Evolution of Triangle-Free Graphs
• On the KŁR conjecture in random graphs
• On triangle-free random graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Rado Partition Theorem for Random Subsets of Integers
• Ramsey properties of random discrete structures
• Random graphs.
• Random I‐colorable graphs
• Sharp thresholds of graph properties, and the k-sat problem
• Stability results for random discrete structures
• The asymptotic number of graphs not containing a fixed color-critical subgraph
• The fine structure of octahedron-free graphs
• The number of graphs without forbidden subgraphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The structure of almost all graphs in a hereditary property
• The two possible values of the chromatic number of a random graph
• The typical structure of graphs without given excluded subgraphs
• Threshold Functions for Ramsey Properties

Cited in

(19)

• Many cliques in \(H\)-free subgraphs of random graphs
• Forbidding induced even cycles in a graph: typical structure and counting
• Integer colorings with no rainbow 3-term arithmetic progression
• Upper tails via high moments and entropic stability
• On the probability of nonexistence in binomial subsets
• The number of the maximal triangle-free graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• The typical structure of graphs without given excluded subgraphs
• Exact stability for Turán's theorem
• An efficient container lemma
• Independent sets in hypergraphs
• 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
• Making K_r+1-free graphs r-partite
• The exponential growth of the packing chromatic number of iterated Mycielskians
• On the typical structure of graphs not containing a fixed vertex-critical subgraph
• On the evolution of structure in triangle-free graphs
• On Dedekind's problem, a sparse version of Sperner's theorem, and antichains of a given size in the Boolean lattice
• A general coupling for Ising models and beyond

This page was built for publication: The typical structure of sparse \(K_{r+1}\)-free graphs

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