# Union of sets with pairwise intersection having half of the elements

Consider $k$ sets $S_1, S_2, \ldots, S_k$, of the following properties:

• For every $i$, $\left|S_i\right| = p$
• For every pair of $i$ and $j$, $\left|S_i \cap S_j\right| = \frac{p}{2}$

Now I need to find the minimum of $\left|\bigcup S_i\right|$ in terms of $k$ and $p$.

(Assume $p$ is large enough to be divisible by any small enough integers)

Via trial and error I suspect the answer to be $$\frac{\left(2^{m + 1} - 1\right)p}{2^m}$$ where $m = \lfloor\log_2 k\rfloor$, but cannot prove it.

That's also why I give that assumption about $p$, so that one do not need to worry about the situation where $\frac{p}{2^m}$ is not an integer.

Edition: actually, I verified that my suspected answer is wrong. For example, when $k = 5$, I managed to construct the sets using $\frac{5p}{6}$ elements. Now I am not sure what the actual answer should be. :(

Correction: I think I had mistaken $p$ with another variable I used in a larger problem where this proof is required, when giving the $\frac{5p}{6}$ lower bound in the edition above. It should be $\frac{5p}{3}$.

An example would be when $k = 5$ and $p = 6$ (to be divisible by both $2$ and $3$), then my $5$ sets would be $$\left\{1, 2, 3, 4, 5, 6\right\}, \left\{1, 2, 3, 7, 8, 9\right\}, \left\{1, 4, 6, 7, 9, 10\right\}, \left\{2, 4, 5, 7, 8, 10\right\}, \left\{3, 5, 6, 8, 9, 10\right\}$$ using $10$ elements. They are obtained basically as I try to "average" the occurrences of each number (in this example, specifically, letting each number appear $3$ times). Maybe we can go from here, but how to prove in general that this average is reachable?

• Equivalent problem: find smallest $n$ such that there exists a $n \times k$ boolean matrix $A = [\mathbf{c}_1\ \mathbf{c}_2\ \dots \ \mathbf{c}_k]$ such that for all $i$ we have $\mathbf{1}^T\mathbf{c}_i = p$, and for each pair of columns $\mathbf{c}_i, \mathbf{c}_j$ we have $\mathbf{c}_i^T \mathbf{c}_j = p/2$. Explanation: $n$ is the universe $|\cup S_i|$, each column is a set encoded by a binary yes/no for each element in the universe whether it's included in the set. – orlp Sep 19 '18 at 10:54
• I'm skeptical of your $\frac{5p}{6}$ construction. What does it construct for $p = 4$? The minimum solution I can find has $|\cup S_i| = 7$, and my solver says no solution exists for $|\cup S_i| = 6$, whereas you claim it can be done in $4$ (assuming we round up). My solution is $$\{2, 3, 4, 5\}, \{3, 5, 6, 7\}, \{1, 2, 3, 7\}, \{1, 3, 4, 6\}, \{1, 4, 5, 7\}$$. – orlp Sep 19 '18 at 11:55
• It is impossible to get $\frac{5p}6$ since $|\bigcup_i S_i|\ge |S_1|=p$. Also, if you want us to help you, do not withhold information. Tell us about the construction you found, and why you suspected your original guess. – Mike Earnest Sep 19 '18 at 17:56
• @MikeEarnest Sorry I made a mistake in the edition. I have fixed it and provided a construction for the minimum I suspected. Please see correction in the problem body. The original guess related to powers of $2$ was made by trying out the best way of adding a $4^\text{th}$ set onto an optimal $3$ sets containing the least total elements, but it seems that this method is already shown incorrect anyways. – Beanandbean Sep 20 '18 at 6:38

Some estimation:

Let $$M:=\bigcup S_i = \{1,2,...,n\}$$ Let $$d_i$$ be a number of sets that $$i\in M$$ is in them. Then we have $$\sum_{i=1}^n d_i =k\cdot p$$ and $${k\choose 2}{p\over 2} = \sum _{i=1}^n{d_i\choose 2}$$

By Jensen we have:

$$\sum _{i=1}^n{d_i\choose 2} \geq {{1\over n}(\sum d_i)^2-(\sum d_i)\over 2}$$

so we have $${k\choose 2}{p\over 2}\geq {{1\over n}(kp)^2-(kp)\over 2}$$ and thus $${k-1\over 2}\geq {1\over n}kp-1$$ so $$n\geq {2kp\over k+1}$$

But I don't know how to find a configuration with $$n=\Big[{2kp\over k+1}\Big]$$. However, for odd $$k$$ equality is achieved if $$d_1=d_2=...=d_n = {k+1\over 2}$$

• (1) typo? last inequality should be $n \ge {2kp \over k+1}$... right? (2) I'd think for general $p, k$ this bound is very loose. E.g for $p=2$ and large $k$ this bound becomes $n \ge 4$, but I think (99% sure) such an example can only be achieved with $n=k+1$, where each set has one element unique to itself and one element common to everybody. (3) In my answer, Family 1 does achieve the bound: my $U =$ your $n = {2kp \over k+1}$ whenever $k=2^d - 1$. – antkam Sep 21 '18 at 19:34
• (4) actually in my answer, Family 2 also achieves your bound: my $U=$ your $n= {2kp \over k+1}$ for odd $k$ and $p = {k-1 \choose ({k-1 \over 2})}$. Furthermore, in those Family 2 examples, $d_1 = ... = d_n = {k+1 \over 2}$. – antkam Sep 21 '18 at 20:09

Discussion: For shorthand, write $$U = |\bigcup S_i|$$. Let $$f(k,p)$$ denote the minimum $$U$$, as a function of both $$k$$ (integer) and $$p$$ (even integer). There is no decomposition $$f(k,p) = g(k) \cdot p$$ that holds exactly for all $$k,p$$. (E.g. if $$p=2, k=5$$, the only solution I can think of has $$U = 6$$ where every set has 1 element unique to itself and 1 element common to every set, so $$g(5) = 6/2=3$$. Meanwhile the OP showed an example for $$p=6, k=5, U=10$$ so $$g(5) = 10/6 = 5/3$$.) For that reason, I also find it strange to say lets "assume" $$p$$ is large and highly composite... unless what you are actually interested in minimizing the ratio $$U/p$$, e.g. for large $$p$$, or for optimal $$p$$. E.g., were you perhaps interested in $$h(k) = \min_p {f(k,p) \over p}$$, i.e. the minimum ratio (that holds for some $$p$$, i.e. minimized over all possible even integers $$p$$)?

Anyway, depending on whether you want to minimize universe size $$U$$, or minimize the ratio $$U/p$$, the answers may be different. The rest of this post shows 2 separate families of solutions, one better at minimizing $$U$$ and the other better at minimizing $$U/p$$.

Family 1: based on $$d$$-bit binary vectors

Consider $$d$$-bit binary vectors $$v \in \{0,1\}^d$$. Let $$D=\{1, 2, ..., d\}$$ denote the bit positions. Let $$T$$ be a non-empty subset of $$D$$. There are $$2^d - 1$$ such subsets, which we name $$T_1, T_2, ..., T_{2^d -1}$$.

• Define $$S_i = \{v \in \{0,1\}^d: \sum_{t \in T_i} v_t = 1 \pmod 2\}$$. I.e., for any vector $$v$$, sum up (modulo 2) all the bits $$v_t$$ at positions $$t \in T_i$$, and if the sum is $$1$$ then the vector belongs in $$S_i$$, otherwise it doesnt. E.g. for $$T_i = \{2,3,5\}$$, any vector $$(*,1,1,*,1,*,*) \in S_i$$ but any vector $$(*,1,0,*,1,*,*) \notin S_i$$, where $$*$$ denotes wildcard ($$0$$ or $$1$$).

• For any $$i$$, it is obvious that exactly 1/2 of all vectors are in $$S_i$$, i.e. $$|S_i| = 2^{d-1} = p$$.

• I think it's also true (although I cannot think of a short proof) that for any $$i, j$$, exactly 1/4 of all vectors are in $$S_i \cap S_j$$, i.e. $$|S_i \cap S_j| = 2^{d-2} = p/2$$.

Thus the sets $$S_i$$ meet the OP's requirements. There are $$2^d - 1$$ such sets, and of course you don't have to use all of them. In other words we have constructed examples, parameterized by $$d$$, where:

• individual set size $$p = 2^{d-1}$$
• no. of sets $$k \le 2^d - 1$$
• universe size $$U = 2^d - 1$$, because every vector is in the union EXCEPT the zero vector
• ratio $$U/p = {2^d - 1 \over 2^{d-1}}$$, akin to the original formula the OP suggested.

Family 2: based on $$m$$-choose-$$n$$

Let me now exhibit a different family of solutions generalizing the OP's $$k=5, p=6$$ example.

Suppose you have $$m$$ distinct objects $$\{1, 2, ..., m\}$$ and you choose $$n of them. There are of course $$L={m \choose n}$$ ways to do this, i.e. there are $$L$$ such size-$$n$$ subsets. Order these $$L$$ subsets lexicographically and call them $$T_1, T_2, ... T_L$$. E.g. if $$n=3$$ then $$T_1 = \{1,2,3\}, T_2 = \{1,2,4\}, ..., T_L = \{m-2, m-1, m\}$$, etc. Now form the following $$m\times L$$ matrix $$A$$:

• $$A_{ij}=1$$ if object $$i \in T_j$$.
• $$A_{ij}=0$$ otherwise.

I.e. the $$j$$th column of $$A$$ is the Boolean vector for membership in $$T_j$$. Now switch your perspective and...

• Identify the rows of $$A$$ as the OP's $$S_i$$ sets.

• Identify the set of columns as the universe $$\bigcup S_i$$, and in particular, $$L = |\bigcup S_i| = U$$.

The following statements hold:

• Each row contains the same number of $$1$$s: indeed, $$\forall i, \sum_j A_{ij} = {m-1 \choose n-1}$$, independent of $$i$$. This is the number of subsets $$T_j$$ that contains $$i$$, which equals the number of ways to choose the remaining $$n-1$$ elements out of the remaining $$m-1$$ possibilities. Since we identify each row $$i$$ as the OP's set $$S_i$$, this means $$|S_i| = p = {m-1 \choose n-1}$$.

• For any two rows $$i, i'$$, their intersection contains the same number of $$1$$s: indeed, $$\forall i, i', \sum_j (A_{ij}A_{i'j}) = {m-2 \choose n-2}$$, independent of $$i, i'$$. This is the number of subsets $$T_j$$ that contains both $$i$$ and $$i'$$, which equals the number of ways to choose the remaining $$n-2$$ elements out of the remaining $$m-2$$ possibilities. Since we identify rows $$i, i'$$ as the OP's sets $$S_i, S_{i'}$$, this means $$|S_i \cap S_{i'}| = p/2 = {m-2 \choose n-2}$$.

• Now we solve: $${m-2 \choose n-2} = {1 \over 2} {m-1 \choose n-1} \implies n = 1 + {m-1 \over 2} = {m+1 \over 2}$$.

In other words, parameterized by odd integer $$m$$, we can define $$n = {m+1 \over 2}$$ and we have exhibited a collection of sets (rows of $$A$$) where:

• individual set size $$p={m-1 \choose n-1}$$
• no. of sets $$k \le m$$
• universe size $$U = L = {m \choose n}$$, the no. of columns of $$A$$
• ratio $$U/p = {m \choose n} / {m-1 \choose n-1} = m/n = {2m \over m+1}$$

Examples and comparisons:

The follow table lists, for several choices of $$k$$, the "best" examples offered by each family and the resulting $$p, U, U/p$$. (In each family, the best is obtained by taking the smallest $$d$$ or $$m$$ possible.)

                Family 1             Family 2
--------             --------
k     d   p   U   U/p      m   n   p   U   U/p
---     ---------------      -------------------
3     2   2   3   3/2      3   2   2   3   3/2
4,5     3   4   7   7/4      5   3   6  10   5/3
6,7     3   4   7   7/4      7   4  20  35   7/4
8,9     4   8  15  15/8      9   5  70 126   9/5
10,11    4   8  15  15/8     11   6 252 462  11/6
12,13    4   8  15  15/8     13   7   .   .  13/7
14,15    4   8  15  15/8     15   8   .   .  15/8


As can be seen, Family 1 generally has much smaller $$U$$ (except equality when $$k=3$$), but Family 2 has smaller $$U/p$$ ratio (except equality when $$k=3, 6,7, 14, 15$$, and if I may extrapolate: $$k= 30, 31, 62, 63,$$ etc)