An exact Turán result for tripartite 3-graphs

2015/04/29 by Adam Sanitt, Sanitt, Adam, John Talbot +1
Mathematics · #05C35 #05D05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35 #msc:05D05

paper · pdf · doi:10.48550/arxiv.1504.07796

12 pages

arxiv created 2015/04/29 · arxiv updated 2015/04/30

Abstract

Mantel's theorem says that among all triangle-free graphs of a given order the balanced complete bipartite graph is the unique graph of maximum size. We prove an analogue of this result for 3-graphs. Let K₄^-=\123,124,134\, F₆=\123,124,345,156\ and F=\K₄^-,F₆\: for n≠ 5 the unique F-free 3-graph of order n and maximum size is the balanced complete tripartite 3-graph S₃(n) (for n=5 it is C₅⁽³⁾=\123,234,345,145,125\). This extends an old result of Bollobás that S₃(n) is the unique 3-graph of maximum size with no copy of K₄^-=\123,124,134\ or F₅=\123,124,345\.

Related

• A hypergraph Turán theorem via lagrangians of intersecting families
• Complete tripartite subgraphs of balanced tripartite graphs with large minimum degree
• Triple systems with bounded matching number: some constructions and exact Turán number
• Complete subgraphs in multipartite graphs
• Hypergraph Turán problem of the generalized triangle with bounded matching number