# Minimal numbers of elements in union of sets

Consider the sets $A_1, A_2, \ldots, A_n$ where $|A_i|=k$, $n \geq k,$ and $|A_i \cap A_j| \leq 1$ for all $i,j$. What is the minimal numbers of elements in their union $|A_1 \cup A_2 \cup \ldots \cup A_n|?$

For $n=k$ I got that the union consist of $\frac{k(k+1)}{2}$ elements but what about the case $n>k?$

Also I have tried to use inclusion–exclusion formula to get any inequality but no success.

## 1 Answer

If $N$ is the number of elements in the union, then we have the lower bound $$N(N-1) \ge n k(k-1).$$ To prove this, let $\deg x$ for an element $x \in A_1 \cup A_2 \cup \dots \cup A_n$ be the number of sets $A_i$ containing $x$. Since $$\sum_x \deg x = \sum_{i=1}^n |A_i| = nk,$$ the average value of $\deg x$ is $\frac{nk}{N}$, so there must be an element $x$ with $\deg x \ge \frac{nk}{N}$.

All the sets $A_i$ containing $x$ must contain $k-1$ other elements, with no repetition. So there are at least $1 + (k-1)\deg x$ elements in the union $A_1 \cup A_2 \cup \dots \cup A_n$. Using our inequality on $\deg x$, we get $$1 + (k-1) \frac{nk}{N} \le N \iff N(N-1) \ge nk(k-1).$$

This is going to be tight whenever $\deg x$ is constant (so that $\deg x = \frac{nk}{N}$ for all $x$) and the union of the sets containing $x$ is the same as the union of all the sets (in other words, for any element $y$ in the union, there is a set containing both $x$ and $y$).

In particular, if $k$ is a prime power, we can take a $d$-dimensional affine space over $\mathbb F_k$, which will have $N = k^d$ points and $n = \frac{k^d(k^d-1)}{k(k-1)}$ lines, giving us infinitely many values of $n$ at which the lower bound is tight.

(More generally, we can achieve the bound by an $(N,k,1)$-block design.)

• Let $k=5,n=20$. The inequality $N(N-1) \geq 20 \cdot 5 \cdot 4$ implies that $N \geq 21$. But I cant construct any $20$ sets from $21$ elements with the conditions $|A_i \cap A_j|\leq 1$. – Leox Aug 26 '18 at 21:13
• You can even construct $21$ such sets: take $$\{1,2,7,8,9\},\{1,3,10,11,12\},\{1,4,13,14,15\},\{1,5,16,17,18\},\{1,6,19,20,21\},\{2,3,13,16,19\},\{2,4,10,17,20\},\{2,5,11,14,21\},\{2,6,12,15,18\},\{3,4,7,18,21\},\{3,5,8,15,20\},\{3,6,9,14,17\},\{4,5,9,12,19\},\{4,6,8,11,16\},\{5,6,7,10,13\},\{7,11,15,17,19\},\{7,12,14,16,20\},\{8,10,14,18,19\},\{8,12,13,17,21\},\{9,10,15,16,21\},\{9,11,13,18,20\}.$$ (If you want $20$ sets, just forget about one of them.) – Misha Lavrov Aug 26 '18 at 21:28
• This construction comes from the finite projective plane of order $4$. – Misha Lavrov Aug 26 '18 at 21:29
• If $|A_i \cap A_j|=2$ then the lower bound is $$N(N-1)(N-2) \geq n k(k-1)(k-2)?$$ – Leox Aug 27 '18 at 7:52
• Yes (and you can prove it in the same way), but I don't know how good the bound is in that case. – Misha Lavrov Aug 27 '18 at 13:37