Skip to main content
2 of 2
added 143 characters in body
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

Intersecting 4-sets

Is it possible to have more than $N = \binom{\lfloor n/2\rfloor}{2}$ subsets of an $n$-set, each of size 4, such that each two of them intersect in 0 or 2 elements?

To see that $N$ is achievable, choose $\lfloor n/2\rfloor$ disjoint pairs and then take each 4-set consisting of two of the pairs. But this is not the unique way of doing it in general.

EDIT: Patricia has provided a counterexample with $n=7$, so I'll remove odd $n$ from the question. Is there a counterexample for even $n$?

Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147