Triple systems with no three triples spanning at most five points

Abstract

We show that the maximum number of triples on n points, if no three triples span at most five points, is ( 1 ± o ( 1 ) ) n 2 / 5 . More generally, let f ( r ) ( n ; k , s ) be the maximum number of edges in an r-uniform hypergraph on n vertices not containing a subgraph with k vertices and s edges. In 1973, Brown, Erdős and Sós conjectured that the limit lim n → ∞ n − 2 f ( 3 ) ( n ; k , k − 2 ) exists for all k. They proved this for k = 4 , where the limit is 1 / 6 and the extremal examples are Steiner triple systems. We prove the conjecture for k = 5 and show that the limit is 1 / 5 . The upper bound is established via a simple optimisation problem. For the lower bound, we use approximate H-decompositions of K n for a suitably defined graph H.

Locations

• Bulletin of the London Mathematical Society - View
• arXiv (Cornell University) - View - PDF
• DataCite API - View