An Extension of Mantel’s Theorem to k-Graphs

Abstract

According to Mantel’s theorem, a triangle-free graph on n points has at most $n^2/4$ edges. A linear k-graph is a set of points together with some k-element subsets, called edges, such that any two edges intersect in at most one point. The k-graph F^k, called a fan, consists of k edges that pairwise intersect in exactly one point v, plus one more edge intersecting each of these edges in a point different from v. We extend Mantel’s theorem as follows: fan-free linear k-graphs on n points have at most $n^2/k^2$ edges.

This extension nicely illustrates the difficulties of hypergraph Turán problems. The determination of the case of equality leads to transversal designs on n points with k groups—for k = 3 these are equivalent to Latin squares. However, in contrast to the graph case, new structures and open problems emerge when n is not divisible by k.

• MSC: Primary 05D05
• Secondary 05B15
• 05C70

Acknowledgment

The authors are grateful for the helpful comments of a referee.