Mantel's theorem for random hypergraphs1. Issue 4 (6th January 2016)

• Record Type: Journal Article
• Authors: Balogh, József; Butterfield, Jane; Hu, Ping; Lenz, John
• Is Part Of: Random structures & algorithms. Volume 48:Issue 4(2016)
• Page Start: 641
• Page End: 654
• Publication Date: 2016-01-06
• Subjects: Turán number -- random hypergraphs -- extremal problems; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20629
• Languages: English
• ISSNs: 1042-9832

Abstract

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