Mantel's theorem for random hypergraphs

József Balogh, Jane Butterfield, Ping Hu, John Lenz

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)641-654
Number of pages14
JournalRandom Structures and Algorithms
Volume48
Issue number4
DOIs
StatePublished - Jul 1 2016

Keywords

  • Extremal problems
  • Random hypergraphs
  • Turán number

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Mantel's theorem for random hypergraphs'. Together they form a unique fingerprint.

Cite this