TY - JOUR

T1 - Mantel's theorem for random hypergraphs

AU - Balogh, József

AU - Butterfield, Jane

AU - Hu, Ping

AU - Lenz, John

N1 - Funding Information:
Supported by Simons Fellowship (to J. Balogh); NSF CAREER (to J. Balogh) (DMS-0745185); Arnold O. Beckman Research Award (UIUC Campus Research Board 13039); NSF (to J. Butterfield) [EMSW21-MCTP: Research Experience for Graduate Students] (DMS 08-38434); National Security Agency (to J. Lenz) H98230-13-1-0224.
Publisher Copyright:
© 2016 Wiley Periodicals, Inc.

PY - 2016/7/1

Y1 - 2016/7/1

N2 - A classical result in extremal graph theory is Mantel's Theorem, which states that every maximum triangle-free subgraph of Kn 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√logn/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 F5, which is sometimes called 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 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 F5 is tripartite for n>3000. A natural question is for what p is every maximum F5-free subhypergraph of G3(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.1√logn/n.

AB - A classical result in extremal graph theory is Mantel's Theorem, which states that every maximum triangle-free subgraph of Kn 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√logn/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 F5, which is sometimes called 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 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 F5 is tripartite for n>3000. A natural question is for what p is every maximum F5-free subhypergraph of G3(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.1√logn/n.

KW - Extremal problems

KW - Random hypergraphs

KW - Turán number

UR - http://www.scopus.com/inward/record.url?scp=84953923438&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84953923438&partnerID=8YFLogxK

U2 - 10.1002/rsa.20629

DO - 10.1002/rsa.20629

M3 - Article

AN - SCOPUS:84953923438

VL - 48

SP - 641

EP - 654

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 4

ER -