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

  • 2
    $\begingroup$ 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. $\endgroup$ – Barry Cipra Oct 23 '12 at 21:11
  • $\begingroup$ 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. $\endgroup$ – Tony Huynh Oct 23 '12 at 21:33
  • 1
    $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Oct 23 '12 at 21:50
  • 7
    $\begingroup$ 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. $\endgroup$ – Johan Wästlund Oct 23 '12 at 22:00
  • 1
    $\begingroup$ 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$. $\endgroup$ – 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$.

Gerhard "Ask Me About Binary Matrices" Paseman, 2012.10.23

  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Oct 24 '12 at 5:22
  • $\begingroup$ 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 $\endgroup$ – 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$.

  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Oct 25 '12 at 19:17
  • 1
    $\begingroup$ 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$. $\endgroup$ – Barry Cipra Oct 25 '12 at 21:10
  • 1
    $\begingroup$ 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$.) $\endgroup$ – Barry Cipra Oct 25 '12 at 22:11
  • $\begingroup$ 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. $\endgroup$ – Kevin P. Costello Oct 25 '12 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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