Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 641-654 |
Number of pages | 14 |
Journal | Random Structures and Algorithms |
Volume | 48 |
Issue number | 4 |
DOIs | |
State | Published - Jul 1 2016 |
Keywords
- Extremal problems
- Random hypergraphs
- Turán number
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics