An exact Turan result for tripartite 3-graphs

作者：Sanitt Adam^*; Talbot John

来源：Electronic Journal of Combinatorics, 2015, 22(4): P4.3.

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-4(-) = {123, 124, 134}, F-6 = {123, 124, 345, 156} and F = {K-4, F6(}): for n not equal 5 the unique F-free 3-graph of order n and maximum size is the balanced complete tripartite 3 -graph S-3 (n) (for n = 5 it is C-5((3)) = {123, 234, 345, 145, 125}). This extends an old result of Bollobas that S3 (n) is the unique 3 -graph of maximum size with no copy of K-4(-) = {123, 124, 134} or F-5 = {123,124,345}.

• 出版日期2015-10-16