Mantel's theorem for random hypergraphs

DOI10.1002/RSA.20629MaRDI QIDQ5740269zbMATH OpenOpenAlexWikidataFDO

Authors József Balogh, Ping Hu, John Lenz, Jane V. Butterfield

Publication date 25 July 2016

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

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

zbMATH Keywords

extremal problemsrandom hypergraphsTurán number

Mathematics Subject Classification ID

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

Abstract: A classical result in extremal graph theory is Mantel's Theorem, which states that every maximum triangle-free subgraph of $K_n$ is bipartite. A sparse version of Mantel's Theorem is that, for sufficiently large $p$, every maximum triangle-free subgraph of $G(n,p)$ is w.h.p. bipartite. Recently, DeMarco and Kahn proved this for $p>Ksqrtlogn/n$ for some constant $K$, and apart from the value of the constant this bound is best possible. We study an extremal problem of this type in random hypergraphs. Denote by $F_5$, which sometimes called as the generalized triangle, the 3-uniform hypergraph with vertex set {a,b,c,d,e} and edge set {abc, ade, bde}. One of the first extremal results in extremal hypergraph theory is by Frankl and F"{u}redi, who proved that the maximum 3-uniform hypergraph on n vertices containing no copy of $F_5$ is tripartite for n>3000. A natural question is for what p is every maximum $F_5$-free subhypergraph of $G^3(n,p)$ w.h.p. tripartite. We show this holds for $p>Klogn/n$ for some constant K and does not hold for $p=0.1sqrtlogn/n$.

Recommendations

• Keller–Osserman estimates and removability result for the anisotropic porous medium equation with gradient absorption term
• Mantel's theorem for random graphs
• On \(k\)-uniform random hypergraphs without generalized fans
• On a generalisation of Mantel’s Theorem to Uniformly Dense Hypergraphs
• A new generalization of Mantel's theorem to \(k\)-graphs

Cites work

• A new generalization of the Erdős-Ko-Rado theorem
• An exact result for 3-graphs
• Combinatorial theorems in sparse random sets
• Extremal subgraphs of random graphs
• Hypergraph containers
• Independent sets in hypergraphs
• Mantel's theorem for random graphs
• On the Chromatic Thresholds of Hypergraphs
• Stability results for random discrete structures
• Stability theorems for cancellative hypergraphs
• Three-graphs without two triples whose symmetric difference is contained in a third

Cited in

(10)

• On \(k\)-uniform random hypergraphs without generalized fans
• Goldberg's conjecture is true for random multigraphs
• Mantel's theorem for random graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Almost all triangle-free triple systems are tripartite
• On a generalisation of Mantel’s Theorem to Uniformly Dense Hypergraphs
• Keller–Osserman estimates and removability result for the anisotropic porous medium equation with gradient absorption term
• On the maximum \(F_5\)-free subhypergraphs of a random hypergraph
• The degree threshold for covering with all the connected 3-graphs with 3 edges
• An exact Turán result for tripartite 3-graphs

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

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