I asked this question on stackexchange :


<https://math.stackexchange.com/questions/2570199/union-of-pairwise-almost-disjoint-sets>


but I got no answer after 24 hours, so I ask it here.


Let $r$ and $n$ be two natural numbers, with $n \geq 2$. What is known about the least possible cardinality of the union of $r$ sets with cardinality $n$, such that any two of these sets have at most one element in common ?


Let $f(r, n)$ denote this least possible cardinality.


If $n = 2$, the condition that two of the sets have at most one common element amounts to say that these sets are distinct, thus $f(r, 2)$ is the least natural number $k$ such that ${k \choose 2} \geq r$.


In the general case, each of the $r$ sets contains $n \choose 2$ pairs and two sets never contain a same pair, thus the union of the $r$ sets contains at least $r {n \choose 2} $ pairs, thus


(1) $f(r, n) \geq k(r, n)$, where $k(r, n)$ denotes the least $k$ such that ${k \choose 2} \geq r {n \choose 2}$.


This is not optimal, in the sense that $f(r, n) > k(r, n)$ happens. For example, $f(2, 3) = 5$ and $k(2, 3) = 4$.


I have two questions :


1° do you know a better minoration of $f(r, n)$ than (1) ?


2° (1) gives $f(30, 4) \geq 20$; can it be proved that $f(30, 4) \geq 21$ ?


Thanks in advance.



Union of pairwise almost disjoint sets
Your question is a special case of the set packing problem. My reference for this stuff (which I know nothing about) is A. E. Brouwer, Packing and covering of $\binom kt$ sets, in: A. Schrijver (ed.), *Packing and Covering in Combinatorics*, Mathematical Centre Tracts 106 (1979), 89–97. (This is obviously not the last word on the subject, but for some reason I happen to have a copy.) Paraphrasing the definition from Brouwer:



> 
> Let $0\le t\le k\le v,$ and define
>  $$D(t,k,v)=\max\{|\mathcal B|:\mathcal B\subset\mathcal P\_k(v)\text{ and no two elements of }\mathcal B\text{ have }t\text{ points in common}\}$$
>  where $\mathcal P\_k(v)$ is the collection of $k$-subsets of a fixed $v$-set.
> 
> 
> 


In this notation, your $f(r,n)$ is the least $v$ such that $D(2,n,v)\ge r.$


According to Brouwer's 1979 survey, the exact values of $D(2,k,v)$ are known for $k=3$ and $k=4.$ For $k=4$ the results are attributed to A. E. Brouwer, Optimal packings of $K\_4$'s into a $K\_n,$ Math. Centre Report no. zw 92/97, Math. Centre, Amsterdam, 1977; [J. Combinatorial Theory (A) 26 (1979), 278–297](http://www.sciencedirect.com/science/article/pii/0097316579901055), and are as follows (paraphrased):



> 
> For $v\ne8,9,10,11,17,19,$ we have
>  $$D(2,4,v)=\left\lfloor\frac v4\left\lfloor\frac{v-1}3\right\rfloor\right\rfloor-\varepsilon,$$
>  where $\varepsilon=1$ for $v\equiv7$ or $10\pmod{12}$ and $\varepsilon=0$ otherwise;  
> 
>   
> and for $v=8,9,10,11,17,19$ we have $D(2,3,v)=2,3,5,6,20,25.$
> 
> 
> 


In particular, $D(2,4,19)=25$ and $D(2,4,20)=30,$ so $f(30,4)=20.$


