What is the largest family F of subsets of [n] for which any two distinct sets A and B in F have an intersection of size at most min(|A|,|B|)/2? - MathOverflow

What is the largest family F of subsets of [n] for which any two distinct sets A and B in F have an intersection of size at most min(|A|,|B|)/2?

2011-01-13T04:14:29Z

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.

Answer by Aaron Meyerowitz for What is the largest family F of subsets of [n] for which any two distinct sets A and B in F have an intersection of size at most min(|A|,|B|)/2?

2011-01-13T05:12:17Z

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.

Answer by Gerry Myerson for What is the largest family F of subsets of [n] for which any two distinct sets A and B in F have an intersection of size at most min(|A|,|B|)/2?

2011-01-13T05:33:42Z

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.