Skip to main content
4 of 4
deleted 1 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

For an affine space over $\mathbb{z}_2$ with $n=2^k$ we have $\binom{n}{2}=(2^{k}-1)(2^{k-1})$ however there are $\binom{n}{3}/4=\frac{2^{k}(2^{k}-1)(2^{k}-2)}{24}$ 2 dimensional flats of which any pair intersect in at most two points.

Details: Consider the $n=2^k$ binary vectors of length $k$. Among the sets of 4 vectors chose only those of the form $\lbrace x,y,z,x+y+z\rbrace$ in other words those quadruples whose members sum to the all zero vector.

I don't know how close you can get for other values of $n$ to having a family of 4-sets so that any three points is in a unique 4-set.

I would expect even better numbers for bigger subsets with a big enough $n$.

The best one could do with 4-sets when $n=24$ could at the very most $\binom{24}{3}/4=506$. The Steiner system S(5,8,24) is a family of 759 8 element subsets (blocks) of a 24 set so that each 5-set is in a unique block.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104