3
$\begingroup$

Let $n$ be a positive integer. Consider all subsets of $\{1,2,\dots,2n\}$ of size $n$. We want to group the subsets in $k$ groups so that any two subsets in the same group intersect in at least two elements. What is the minimum $k$ for which this is possible?

For $n=1$, clearly $k=2$. For $n=2$, we must put each of the $6$ subsets in its own group, so $k=6$. For any $n$, we can get $6$ groups by grouping subsets only according to the intersection of the first four elements $1,2,3,4$ with each subset.

  • The intersection is $\{1,2\},\{1,2,3\},\{1,2,4\},$ or $\{1,2,3,4\}$

  • The intersection is $\{3,4\},\{1,3,4\},$ or $\{2,3,4\}$

  • The intersection is $\{1,4\},\{1\},$ or $\emptyset$

  • The intersection is $\{2,3\}$ or $\{2\}$

  • The intersection is $\{1,3\}$ or $\{3\}$

  • The intersection is $\{2,4\}$ or $\{4\}$

Smylic shows below that $6$ is optimal for $n=3$. Is $6$ optimal for any $n\geq 2$?

$\endgroup$
3
  • $\begingroup$ I think this may be an instance of the Erdos-Ko-Rado theorem $\endgroup$ Jul 11 '17 at 0:07
  • $\begingroup$ I don't understand the 6 groups. For example if $n=5$ the sets $\{1,5,6,7\}$ and $\{1,8,9,10\}$ should be in the third group, since the intersection with the first elements is $\{1\}$. However, they intersect only at one element. $\endgroup$
    – san
    Jul 16 '17 at 20:00
  • $\begingroup$ If $n=5$ each set should contain 5 elements. $\endgroup$
    – pi66
    Jul 16 '17 at 20:14
3
$\begingroup$

If $n = 3$ there are $\frac{6!}{3!3!} = 20$ triples.

Suppose we partition triples into $5$ sets. Then each set consists of $4$ triples. Each set contains $4$ triples that are either subsets of $4$-element set or supersets of $2$-element set. So one of this two options occurs at least $3$ times. We have two cases.

  1. There are at least $3$ sets of subsets of $4$-element sets of size $3$. Without loss of generality let one of these $4$-element sets be $\{\,1, 2, 3, 4\,\}$. Any other should contain at most $2$ elements of these $4$ because otherwise the same triple would be “induced” twice. So again without loss of generality let another set be $\{\,1, 2, 5, 6\,\}$. The third set should contain at most $2$ of $\{\,1, 2, 3, 4\,\}$ therefore it contains $5$ and $6$. Also it should contain at most $2$ of $\{\,1, 2, 5, 6\,\}$ therefore it contains $3$ and $4$. So we have $8$ triples remaining, each of which has $1$ element from each of $3$ following pairs: $\{\,1, 2\,\}$, $\{\,3, 4\,\}$ and $\{\,5, 6\,\}$. It is easy to see that no more set of $4$ triples can be formed, because each pair is contained in at most $2$ triples and each $4$-element set has at most $2$ triples as subsets.

  2. There are at least $3$ sets of supersets of $2$-element sets of size $3$. It is easy to see that two such $2$-element sets have no element in common. (Suppose there are two pairs $\{\,x, y\,\}$ and $\{\,x, z\,\}$. Then triple $\{\,x, y, z\,\}$ should belong to two sets of triple.) Therefore without loss of generality these $2$-element sets are $\{\,1, 2\,\}$, $\{\,3, 4\,\}$ and $\{\,5, 6\,\}$. Then remaining $8$ triples are the same as before and in this case we again cannot produce even $4$ sets of $4$ triples each.

Therefore any collection of $6$ sets of triples is optimal for $n = 3$.

$\endgroup$
0
$\begingroup$

Let $N = \{1,2,...,2n\}$

Say $G_i$ is union of sets in $i$-th group. Then each pair $\{x,y\}\subset N$ is in at most one $G_i$. Since each group is nonempty we have in $G_i$at least ${n\choose 2}$ different pairs. Now do the double counting between the pairs $\{x,y\}\subset N$ and $G_i$ and we get: $$ k\cdot {n\choose 2} \leq {2n\choose 2} \Longrightarrow k\leq {4n-2\over n-1}$$ Thus, if $n\geq 4$ we have $k\leq 4$.

$\endgroup$
1
  • $\begingroup$ Oh, I probably miss understood the problem. There is actually trivial upper bound $k= {2n \choose n}$ if each group there is only one set. I thought that $A$ and $B$ are in the same group iff $ |A\cap B|\geq 2$. But that is not the case. Actually it is if they are in the same set then $ |A\cap B|\geq 2$ and not vice versa. Never mind reading this, I'm only talking to my self. $\endgroup$
    – Aqua
    Jul 20 '17 at 15:35

Your Answer

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

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