Mantel's theorem for random graphs

DOI10.1002/RSA.20535MaRDI QIDQ3192372zbMATH OpenOpenAlexWikidataFDO

Authors B. DeMarco, J. Kahn

Publication date 12 October 2015

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Mantel's theoremmax cutrandom graphthreshold

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Abstract: For a graph $G$, denote by $t(G)$ (resp. $b(G)$) the maximum size of a triangle-free (resp. bipartite) subgraph of $G$. Of course $t(G)geqb(G)$ for any $G$, and a classic result of Mantel from 1907 (the first case of Tur'an's Theorem) says that equality holds for complete graphs. A natural question, first considered by Babai, Simonovits and Spencer about 20 years ago is, when (i.e. for what $p=p(n)$) is the "ErdH{o}s-R'enyi" random graph $G=G(n,p)$ likely to satisfy $t(G)=b(G)$? We show that this is true if $p>C{n}^{-1/2}lo{g}^{1/2}n$ for a suitable constant $C$, which is best possible up to the value of $C$.

Recommendations

• Extremal subgraphs of random graphs
• Mantel's theorem for random hypergraphs
• On extremal subgraphs of random graphs
• Extremal subgraphs of random graphs
• On triangle-free random graphs

Cites work

• Arithmetic progressions of length three in subsets of a random set
• Extremal subgraphs of random graphs
• Extremal subgraphs of random graphs
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• Independent sets in hypergraphs
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• On \(K^ 4\)-free subgraphs of random graphs
• On Sets of Acquaintances and Strangers at any Party
• On the triangle space of a random graph
• Stability results for random discrete structures
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The clique complex and hypergraph matching
• Topology of random clique complexes

Cited in

(22)

• Random sum-free subsets of abelian groups
• Triangle-free subgraphs of hypergraphs
• On \(k\)-uniform random hypergraphs without generalized fans
• Goldberg's conjecture is true for random multigraphs
• The typical structure of sparse \(K_{r+1}\)-free graphs
• On extremal subgraphs of random graphs
• Extremal subgraphs of random graphs
• Triangle-free subgraphs of random graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• scientific article; zbMATH DE number 5375038 (Why is no real title available?)
• scientific article; zbMATH DE number 1019391 (Why is no real title available?)
• Keller–Osserman estimates and removability result for the anisotropic porous medium equation with gradient absorption term
• Triangle-free subgraphs of random graphs
• Extremal subgraphs of random graphs
• On Erdős-Ko-Rado for random hypergraphs. I
• The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
• Extremal results in random graphs
• Mantel's theorem for random hypergraphs
• On the maximum \(F_5\)-free subhypergraphs of a random hypergraph
• Maximum chordal subgraphs of random graphs
• Turán's theorem for pseudo-random graphs
• On the stability of the Erdős-Ko-Rado theorem

This page was built for publication: Mantel's theorem for random graphs

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