3
$\begingroup$

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.

$\endgroup$
2
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Leox Aug 26 '18 at 21:13
  • $\begingroup$ 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.) $\endgroup$ – Misha Lavrov Aug 26 '18 at 21:28
  • $\begingroup$ This construction comes from the finite projective plane of order $4$. $\endgroup$ – Misha Lavrov Aug 26 '18 at 21:29
  • $\begingroup$ If $|A_i \cap A_j|=2$ then the lower bound is $$N(N-1)(N-2) \geq n k(k-1)(k-2)? $$ $\endgroup$ – Leox Aug 27 '18 at 7:52
  • $\begingroup$ Yes (and you can prove it in the same way), but I don't know how good the bound is in that case. $\endgroup$ – Misha Lavrov Aug 27 '18 at 13:37

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.