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 most recent 30 from http://mathoverflow.net 2013-05-25T20:04:27Z http://mathoverflow.net/feeds/question/51909 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/51909/what-is-the-largest-family-f-of-subsets-of-n-for-which-any-two-distinct-sets-a 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? Douglas S. Stones 2011-01-13T04:14:29Z 2011-01-13T07:59:39Z <p>This problem arose in the study of Latin squares with a large number of subsquares, although it appears interesting in its own right.</p> <blockquote> <p><strong>Question</strong>: 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|)$?</p> </blockquote> <p>Some observations:</p> <ul> <li>We have the trivial lower bound $\max |F| \geq {n \choose 2}$ by taking all the subsets of size 2.</li> <li>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.</li> <li>$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).</li> <li>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.</li> </ul> http://mathoverflow.net/questions/51909/what-is-the-largest-family-f-of-subsets-of-n-for-which-any-two-distinct-sets-a/51915#51915 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? Aaron Meyerowitz 2011-01-13T05:12:17Z 2011-01-13T07:59:39Z <p>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.</p> <p>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.</p> <p>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.</p> <p>I would expect even better numbers for bigger subsets with a big enough $n$.</p> <p>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.</p> http://mathoverflow.net/questions/51909/what-is-the-largest-family-f-of-subsets-of-n-for-which-any-two-distinct-sets-a/51917#51917 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? Gerry Myerson 2011-01-13T05:33:42Z 2011-01-13T05:33:42Z <p>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. </p>