An extension of Mantel's theorem to random 4-uniform hypergraphs

Abstract

A sparse version of Mantel's Theorem is that, for sufficiently large $p$, with high probability (w.h.p.), every maximum triangle-free subgraph of $G(n,p)$ is bipartite. DeMarco and Kahn proved this for $p>K\sqrt{\log n/n}$ for some constant $K$, and apart from the value of the constant, this bound is the best possible. Denote by $T_3$ the 3-uniform hypergraph with vertex set $\{a,b,c,d,e\}$ and edge set $\{abc,ade,bde\}$. Frankl and Füredi showed that the maximum 3-uniform hypergraph on $n$ vertices containing no copy of $T_3$ is tripartite for $n>3000$. For some integer $k$, let $G^k(n,p)$ be the random $k$-uniform hypergraph. Balogh et al. proved that for $p>K\log n/n$ for some constant $K$, every maximum $T_3$-free subhypergraph of $G^3(n,p)$ w.h.p. is tripartite and it does not hold when $p=0.1\sqrt{\log n}/n$. Denote by $T_4$ the 4-uniform hypergraph with vertex set $\{1,2,3,4,5,6,7\}$ and edge set $\{1234,1235,4567\}$. Pikhurko proved that there is an $n_0$ such that for all $n\ge n_0$, the maximum 4-uniform hypergraph on $n$ vertices containing no copy of $T_4$ is 4-partite. In this paper, we extend this type of extremal problem in random 4-uniform hypergraphs. We show that for some constant $K$ and $p>K\log n/n$, w.h.p. every maximum $T_4$-free subhypergraph of $G^4(n,p)$ is 4-partite.

18 pages. arXiv admin note: substantial text overlap with arXiv:1310.1501 by other authors