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 p m o (1)) n^{2} / 5

. More generally, let

f^{(r)} (n; k, s)

be the maximum number of edges of an

r

-uniform hypergraph on

n

~vertices not containing a subgraph with

k

~vertices and

s

~edges. In 1973, Brown, ErdH{o}s and S'os conjectured that the limit

l i m_{n o i n f t y} 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

.

Recommendations

Cites Work

Cited In (11)

This page was built for publication: Triple systems with no three triples spanning at most five points