TY - JOUR
T1 - Mantel's theorem for random hypergraphs
AU - Balogh, József
AU - Butterfield, Jane
AU - Hu, Ping
AU - Lenz, John
N1 - 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.
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 - https://www.scopus.com/pages/publications/84953923438
UR - https://www.scopus.com/pages/publications/84953923438#tab=citedBy
U2 - 10.1002/rsa.20629
DO - 10.1002/rsa.20629
M3 - Article
AN - SCOPUS:84953923438
SN - 1042-9832
VL - 48
SP - 641
EP - 654
JO - Random Structures and Algorithms
JF - Random Structures and Algorithms
IS - 4
ER -