This problem arose in the study of Latin squares with a large number of subsquares, although it appears interesting in its own right.

Question: What is the maximum cardinality of a family $F \subseteq 2^{[n]}$ of subsets of $[n]:=\{1,2,\ldots,n\}$ for which any two distinct $A,B \in F$ satisfy $|A \cap B| \leq \tfrac{1}{2} \min(|A|,|B|)$?

Some observations:

  • We have the trivial lower bound $\max |F| \geq {n \choose 2}$ by taking all the subsets of size 2.
  • When $n \geq 3$, $F$ should not have any sets of size 1. If $\{a\} \in F$, then we can replace it by $\{a,x\}$ for all $x \in [n] \setminus \{a\}$ for any $x$ that belongs to a set of size 2 or more (since no other set in $F$ can contain an $a$). If every set has size 1, then $|F|=n$ which can be beaten.
  • $F$ should not have any sets of size 3. If $\{a,b,c\} \in F$, then we can replace it by $\{a,b\},\{a,c\},\{b,c\}$ (since any other set in $F$ may intersect $\{a,b,c\}$ in at most one element).
  • With the above simplifications in mind, I wrote a backtracking algorithm which says that for $3 \leq n \leq 7$ (and it's progressing through $n=8$), that $F$ is uniquely maximized when $F$ consists of all 2-subsets.

2 Answers 2


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.

  • $\begingroup$ Thanks for that, that's exactly what I'm after. (...and now I'm slapping myself for not realising this already) $\endgroup$ Jan 13, 2011 at 5:33
  • 2
    $\begingroup$ Doing the same thing with $l$-dimensional flats gives you a family of size $O(n^{l+1})$. $\endgroup$ Jan 13, 2011 at 5:38

This can be rephrased in the language of coding theory. If you have a binary code with minimal distance $d$ then the words of weight $2d$ form the kind of family you've defined. Tables of good binary codes are widely available on the web.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .