Mantel's theorem for random hypergraphs1. Issue 4 (6th January 2016) - Balogh, József; Butterfield, Jane; Hu, Ping; Lenz, John
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 > K log n / 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 is sometimes called the generalized triangle, the 3‐uniform hypergraph with vertex set { a, b, c, d, e } and edge set { a b c, a d e, b d e } . One of the first results in extremal hypergraph theory is by Frankl and Fü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 > K log n / n for some constant K and does not hold for p = 0.1 log n / n . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 641–654, 2016