Let $r$ and $n$ be two natural numbers, with $n \geq 2$. What can be said 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 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.

  • $\begingroup$ If $r\le n+1$ then it is easy to see that $f(r,n) = nr - \binom r2$ $\endgroup$ – Exodd Dec 17 '17 at 9:35
  • $\begingroup$ @Exodd : yes, but, as my question 2° shows, I'm interested in the other case. $\endgroup$ – Panurge Dec 17 '17 at 9:38
  • $\begingroup$ Now asked on MO: Union of pairwise almost disjoint sets. $\endgroup$ – Martin Sleziak Dec 18 '17 at 13:07

Your Answer

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

Browse other questions tagged or ask your own question.