# k-subsets with some pair containing every element

Let $[n] := {1,2, 3, \dots, n}$ and $k$ be some fixed positive number.

• Whats is the smallest number $m$ so that $A_1, A_2, \dots, A_m$ are k-subsets(each of size k) of $[n]$ and for every $x \in [n]$ there exist some pair $i, j$ such that $x \in A_i \cap A_j$?

• How do we enumerate/generate them?

• Is there a name to this in combinatorial designs?

## 1 Answer

Let me suppose $n\geq k$, otherwise there is no point. A lower bound is $2n/k$ since you need to distribute $2 n$ elements to $m$ sets of size $k$, then you need to have enough space in those sets so $mk \geq 2n$ and so $m\geq 2n / k$.

EDIT : Make the following list : $$[1, 2, \dots , n , 1, 2 ,\dots , n]$$ Then take the first $k$ element, put them in $A_1$, then the k following element, put them in $A_2$ and continue until reaching $A_{2n/k}$. These are indeed sets (no repeated elements). Every element is in two of them.

The same distribution can be used to prove that we can achieve $m=\lceil 2n/k \rceil$ by padding the last set with any numbers. So the value of $m$ that is minimal is $m=\lceil 2n/k \rceil$

• If $\frac nk$ is an integer, this construction adds the same set to the family twice. – Misha Lavrov Sep 14 at 13:38
• true, they would need to be disjoints ? if yes then we can take the list $[1,2,\dots n, n, n-1,\dots , 1]$ but there are still ways (n=k) where it would be the same sets, in this case we will always have two times the same set. – P. Quinton Sep 14 at 13:39
• Can somebody illustrate the enumeration for say n = 5 and k = 2? – talegari Sep 15 at 6:06
• The list is $[1,2,3,4,5,1,2,3,4,5]$ in this case and we take elements $2$ by $2$ to get the $2\cdot 5 / 2 = 5$ sets. $A_1=\lbrace 1,2 \rbrace$, $A_2=\lbrace 3,4 \rbrace$, $A_3=\lbrace 5,1 \rbrace$, $A_4=\lbrace 2,3 \rbrace$ and $A_1=\lbrace 4,5 \rbrace$ – P. Quinton Sep 15 at 6:48