Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.
share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
Thanks for that, that's exactly what I'm after. (...and now I'm slapping myself for not realising this already) –  Douglas S. Stones Jan 13 '11 at 5:33
2  
Doing the same thing with $l$-dimensional flats gives you a family of size $O(n^{l+1})$. –  Chris Eagle Jan 13 '11 at 5:38
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.