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?

up vote 2 down vote accepted

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.