Intersection of size at least two

Question

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$?

Answer 1

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

Answer 2

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