Large Intersecting Subsets of a Set

Question

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$?

Answer 1

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$.

Gerhard "Ask Me About Binary Matrices" Paseman, 2012.10.23

Answer 2

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.

Answer 3

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.

Answer 4

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$.