k-subsets with some pair containing every element

73 Views Asked by At

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

There are 1 best solutions below

4
On BEST 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$