Union of pairwise almost disjoint sets

Question

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.

Answer 1

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, 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.$

Answer 2

You won't get an exact bound, as we do not even know for which values do finite projective planes exist. I think that you should find the least $q+1\le n$ for which ${q^2+q+1\choose 2}\ge r{q+1\choose 2}$, build a projective plane on this $q$ (if you can!) and just let the remaining parts of the sets be singletons.

Answer 3

As it happens, $f(30,4)=20.$ It is a fairly unique construction based on some almost magic seeming coincidences. You can check that $f(4,3)=6.$ Given a base set $S=\{a,b,c,d,e,f\}$ there are $\binom63=20$ triples. I'll write $abc$ (in any order) for the triple $\{a,b,c\}.$

Two systems showing $f(4,3)=6$ are $\{ace,adf,bcf,bde\}$ and $\{acf,ade,bce,bdf\}.$ They come in a certain way from the partition $ab|cd|ef$ into disjoint pairs. In all there are $15$ such partitions and $30$ such systems. The details are an easy exercise.

So for $f(30,4)=20$ I take the $20$ "points" to be the triples from $S$ and the $30$ "lines" to be the quadruples of points forming a system as above for $f(4,3)=6.$ Again, this construction does not generalize to other cases.

---

I use the language above to help point to the literature. I'll be a little loose with the definitions here and let you check out all the conditions. Say that a design (another name is hypergraph) is a family $\mathcal{B}$ of $b$ subsets called blocks from a base set $V$ with $v$ points. I've replaces $r$ with $b.$ I will also replace $n$ with $k$ and call the design $k$-uniform if all the blocks have size $k.$

A design, which might or might not be uniform, is called a linear space if every pair of points belongs to a unique block. In that case the blocks are often called lines since two points determine a unique line. A $k$-uniform linear space is called a Balanced Incomplete Block Design BIBD-$(v,b,k,r,1)$ or a Steiner $k$ system. The $r$ is the constant (in this case) number of blocks containing each point. The parameters are related by $vr=bk$ and $v(v-1)=bk(k-1).$ So given $b,k$ both $v$ and $r$ are determined. I think that for fixed $k$ there is such a system provided $b$ is large enough and the values of $v$ and $r$ are integers.

If there is such a system then $f(b,k)=v.$ There can't quite be one with with $b=30,k=4$ since that gives $v(v-1)=360$ but $19\cdot 18=360-19$ and $20\cdot19=360+20.$ However $v=20$ might be just right if we allow each point to have a unique complement not in any block with it. And that works.

A partial linear space (which might be uniform) is like a linear space except that two points determine at most one line. So you have defined $f(b,k)$ to be the smallest $v$ for which there is a $(b,v,k)-$partial linear space. Since we can always throw away some blocks, $f(b-1,k) \le f(b,k)$ so I would expect that $f(b-j,k)=f(b,k)=v$ in the event that there is a BIBD-$(b,v,k,r,1)$ and $j$ is small enough.

The example at the top was a rather nice partially balanced incomplete block design with $\lambda_1+\lambda_2=1.$ That paper shows a few nice constructions. It is from 1955 so more is known now then then, but it is a good place to look.

Answer 4

edit: It seems that you are more interested in the case $r > n$. I hope that answer for $r \leq n$ still helps.

---

Why not simply construct sets such that the union is minimal?

W.l.o.g., the first set is $$X_1 = \{1,2,\ldots, n\}.$$ The second set should intersect this set in at most one element. Now, if it doesn't intersect at all, the union will surely be not minimal, so we should have one element in the intersection, wlog this element is $1$. Then $$X_2 = \{1,n+1,n+2,\ldots, 2n-1\}.$$ With the same argumentation, $X_3$ should intersect both $X_1$ and $X_2$. But it should not intersect them both in the same element $n$, as in this case the union will no longer be minimal. Therefore, wlog we can say that $$X_3 = \{2,n+1,2n,\ldots 3n-3\}.$$

Continuing like that, it should not be hard to show that $$f(r,n) = \sum_{i=1}^r n-i = nr - {n \choose 2}$$ as long as $r \leq n$.