# Large Intersecting Subsets of a Set

I am sure the answer to this question is well known, but I am not able to figure it out.

Question: Let $U$ be a finite set. Let $F=(S_1,S_2,...,S_n)$ be such that:

(1) $S_i\subset U$

(2) $|S_i|=n$

(3) $|S_i\cap S_j|\leq n/2$

Then, what is the lowerbound on $|U$|? In other words, what is the smallest $U$ for which there exists an $F$ satisfying the above conditions.

Clearly, if $U$ has size $n^2$, it easy to construct such an $F$. You can also do this with just $n^2/2$ elements in $U$. Can you do this with just $O(n)$ elements? What about $O(n^{1+\epsilon})$ for a constant $\epsilon<1$?

-
I think you got the inequality in (3) backwards. As stated, you can let all the $S_i$'s be the same, and thus get by with a set $U$ of exactly $n$ elements. –  Barry Cipra Oct 23 '12 at 21:11
I took the liberty of editing since the mistake seems like an obvious typo. @Smart_Mathematician, feel free to re-edit if you had something else in mind. –  Tony Huynh Oct 23 '12 at 21:33
O(n^3/2) comes quickly by considering the case n=2. I am confident that O(nlogn) is asymptotically acheivable for n sufficiently large. Gerhard "Ask Me About System Design" Paseman, 2012.10.23 –  Gerhard Paseman Oct 23 '12 at 21:50
With $(2+\epsilon)\cdot n$ elements, you can pick the subsets randomly. It will be exponentially unlikely that two subsets intersect in more than $n/2$ elements, and there are only quadratically many pairs of sets, so for large $n$, the conditions will be met with positive probability. –  Johan Wästlund Oct 23 '12 at 22:00
Here is an explicit construction with $Cn$ elements. Take any prime $p\approx 10n$. Let $n$ be even and $S_j=\{jk:k=1,\dots,n}$ (modulo $p$). Then all intersections are pretty much the same and we just need to prove that $|S_j\cap S_1|\le n/2$ for all $j=2,\dots,p-1$. However, this is obvious for $|j|\le 5, j\ne 1$ and if $6\le|j|\le \frac{p-1}2$, choose the least $u$ such that $u|j|>n$ and notice that if $u=1$, then $jk\in S_1$ implies $j(k+1)\notin S_1$ but if $2\le u\le n/5$, then $jk\in S_1$ implies $j(k+u), j(k+2u)\notin S_1$. –  fedja Oct 24 '12 at 0:40

Likely a lower bound is below $2n$. There are many even $n$ for which a real Hadamard matrix of order $2n$, which when normalized to have a row of all 1's yields $2n-1$ rows (and thus that many sets of $n$ elements), each two of which share exactly $n/2$ columns with values of $-1$. Possibly conference matrices could work for odd $n$, and if only $n$ rows are required, then a lower bound of less than $2n-1$ is possible for many even $n$.

-
Running through small test cases in my head leads me to think that 2n for n odd and 2n-1 for n even is how it will turn out. Gerhard "Leaving The Proof To Others" Paseman, 2012.10.23 –  Gerhard Paseman Oct 24 '12 at 5:22
Although nowhere near as nice as the lower bound argument used by Kevin Costello, one can use small cases to get that the lower bound for n > 4 is bigger than 7n/4 just to get 5 or more sets of size n to have "small" intersections. Such observations build my faith in Kevin's conclusion. Gerhard "Ask Me About Small Examples" Paseman, 2012.10.24 –  Gerhard Paseman Oct 24 '12 at 19:10

As Gerhard has pointed out, if there exists a Hadamard matrix of order $4k$, then there exists a symmetric $(4k-1, 2k-1, k-1)$ design. There are $4k-1$ blocks in this design, each contains $2k-1$ points, and the blocks intersect pairwise in $k-1$ points. So discarding $2k$ of the blocks gives a system with the properties that you desire. Discarding all blocks through a specific point will give a system on $4k-2$ points.

In the even case, taking $2k$ blocks from a $(4k-1, 2k-1, k-1)$ design and simply adjoining a point to all of the blocks gives sets of size $2k$ over a ground set of size $4k$ which intersect in $k$ points. In fact, one can find $8k-2$ sets of size $2k$ intersecting pairwise in at most $k$ points if there exists a Hadamard matrix of order $4k$.

Clearly at least $3k$ points are required. The type of counting arguments used to prove inequalities for block designs would probably produce something better, but I can't see an obvious approach at the moment. Assuming the Hadamard conjecture, $4k-2$ points suffice for sets of (odd) size $2k-1$ and $4k-1$ points suffice for sets of size $2k$. I would be surprised if the minimal size is much smaller than this.

-

Just to have something for all sufficiently large n, one can also take, for any small enough $\varepsilon>0$, the set $U$ to have $(2+5\varepsilon)n$ points, and then let $S'_i$ be independent random subsets of $U$ each obtained by choosing the points independently with probability $1/2-\varepsilon$. An application of Chernoff's inequality says that the size of any given $S'_i$ is concentrated close to expectation, and in particular greater than $n$. And the expected intersection of any two sets is $(1/4-\varepsilon+\varepsilon^2)(2+5\varepsilon)n$ which is smaller than $n/2$, and also by Chernoff we have good concentration. The failure probability of each of these applications of Chernoff is something like $2^{-\varepsilon^2 n}$. In particular we can certainly take a union bound over all $n+n^2$ applications (in fact we could have exponentially many $S_i$). Alternatively we can take $\varepsilon$ to be something like $\sqrt{\log n/n}$ and get $n$ sets.

So let $S_i$ be a subset of $S'_i$ of size $n$ for each $i$ and the construction is done.

-

Note: The original answer here had (as noted in the comments) an incorrect calculation of $(Ax)^T Ax$. I've replaced it by the trivial bound $(Ax)^T Ax \geq 0$, which weakens the bound to it doesn't quite match the Hadamard bound anymore.

Here's something which shows the constructions yielding $2n$ are almost tight.

Let $A$ be the $|U| \times n$ matrix where the entry $a_{ij}$ is equal to $1$ if $i \in S_j$ and $-1$ otherwise, and let $B=A^T A$.

Then $B$ is an $n \times n$ matrix having diagonal entries equal to $|U|$ and off-diagonal entries equal to $$b_{ij}=|U| - 2 (|S_j \cap S_i^C| + |S_i \cap S_j^C|)$$ $$=|U|-4(n- |S_i \cap S_j| ) \leq |U| - 2n.$$

Letting $x$ be the $n \times 1$ vector of $1$'s, this implies
$$(Ax)^T (Ax) = \sum_i \sum_j b_{ij} = n |U| + \sum_{(i,j), i \neq j} b_{ij} \leq n|U| + n(n-1) (|U|-2n).$$

But this must be at least $0$, which implies $|U| \geq 2n-2$.

If $n$ is odd, we can improve this slightly to $2n-1$ by replacing the bound $|S_i \cap S_j| \leq n/2$ by $|S_i \cap S_j| \leq (n-1)/2$.

-
It wouldn't surprise me if the bound being exact were equivalent to the Hadamard conjecture, but I don't know enough about partial Hadamard designs to be sure. Gerhard "Paging Zare, Orrick, or Huynh" Paseman, 2012.10.25 –  Gerhard Paseman Oct 25 '12 at 19:17
Am I doing something wrong? When I let $n=2$, for which $|U|=3$ is appropriate, I wind up with $(Ax)^T(Ax) = 4$, which is not equal to $n(|U|-2n)^2 = 2(3-4)^2 = 2$. –  Barry Cipra Oct 25 '12 at 21:10
On further thought, there must be something wrong in the answer here: There is nothing to disallow $|U|$ from being arbitrarily large, but the inequality $(|U|-2n)^2 \leq |U| + (n-1)(|U|-2n)$ can't hold for all $|U|$. (Even if you limit $U$ to be the union of the $S_i$'s, you can have $|U|=n^2$, for which the inequality is false for $n>3$.) –  Barry Cipra Oct 25 '12 at 22:11
Yes, the $(Ax)^T (Ax)$ value is just wrong. I think something at least can still be salvaged by just bounding it by $0$ (as in the edit above), but it doesn't give the conjectured bound anymore. –  Kevin P. Costello Oct 25 '12 at 22:21