2
$\begingroup$

This question is related to one I asked previously.

Consider all ${n\choose k}$ ways of choosing $k$ integers from $\{0,n-1\}$ in sorted order. For example, if $n=5$ and $k=3$ we have:

 (0, 1, 2),
 (0, 1, 3),
 (0, 1, 4),
 (0, 2, 3),
 (0, 2, 4),
 (0, 3, 4),
 (1, 2, 3),
 (1, 2, 4),
 (1, 3, 4),
 (2, 3, 4)

Let us now regard each combination as a subset of integers.

Looking at this list from top to bottom, I would like to group consecutive subsets together in a greedy way so that the size of the intersection of all the subsets in a grouping is at least $k-1$.

So starting from the top I collect $\{(0, 1, 2), (0, 1, 3),(0, 1, 4)\}$ together as their intersection has size $k - 1 = 2$. I then need to start a new grouping and collect $\{(0, 2, 3),(0, 2, 4)\}$, then afterwards $\{(0,3,4)\}$ on its own in a grouping and so on. In this case I end up with $5$ groupings.

Is it possible to give an exact formula for this count for arbitrary positive integers $n> k$?

$\endgroup$
  • $\begingroup$ Just to clarify & so I understand the question ... let $A_{1}, \cdots ,A_{\binom{n}{k}}$ be the list of subset of subset of ${0,\cdots ,(n-1)}$ of cardinality $k$. Now you want to partition this set into $m$ parts of differing sizes. $\{\{A_{a_{1,1}}, \cdots , A_{a_{1,s_1}}\},\{A_{a_{2,1}}, \cdots , A_{a_{2,s_2}}\}, \cdots ,\{A_{a_{m,1}}, \cdots , A_{a_{m,s_m}}\}\}$ so that $\mid \cap_{j=1}^{s_i} A_{a_{i,j}} \mid =k-1$ for $i=1, \cdots , m$ ... is this right ? $\endgroup$ – Donald Splutterwit Apr 8 '17 at 10:34
  • $\begingroup$ @DonaldSplutterwit Yes except that it has to be $ \geq k-1$ as a subset on its own will have size $k$ . In this question we are just applying the greedy algorithm to do this partitioning to the subsets in sorted order. $\endgroup$ – felipa Apr 8 '17 at 10:56
1
$\begingroup$

If $n>k+1$, then the last combination containing $0$ is not going to have overlap $k-1$ with the first combination not containing $0$. (In your example, $(0,3,4)$ and $(1,2,3)$ do not have overlap $k-1$.)

So we will greedily choose a partition of the combinations containing $0$, and then greedily choose a partition of the combinations not containing $0$, and these two steps will not interact in any way.

When $n=k+1$, and $k>1$, we will start by choosing a group of combinations containing $(1,2,\dots,k-1)$. All of them will be part of that group except the last element, so we get two groups.

Let $g(n,k)$ be the size of the partition we get. We have $g(n,n-1)=2$; also, $g(n,1) = 1$ because in that case, we can put everything into one partition. The recursive argument above tells us that when $n>k>0$, $g(n,k) = g(n-1,k-1) + g(n-1,k)$, as:

  • When working with combinations containing $0$, the element $0$ is going to be in all of them, so we are really looking for overlap $k-2$ in their last $k-1$ elements.
  • With the other combinations, it's as though $0$ was never an element to begin with.

These imply some sort of binomial solution; in fact, any linear combination of binomial coefficients will satisfy the recurrence, so we just have to find one that satisfies the base cases. I claim that $$g(n,k) = \binom{n-2}{k-1} + \binom{n-3}{k-2}$$ works: we can check that $g(n,1) = \binom{n-2}{0} = 1$ and $g(n,n-1) = \binom{n-2}{n-2} + \binom{n-3}{n-3} = 2$ for all $n$.

$\endgroup$
  • $\begingroup$ As a side note, I originally misunderstood the problem to mean that in any group, any two sets must share $k-1$ elements, but the whole group doesn't need to (so $\{(1,2), (1,3), (2,3)\}$ is valid). In that case, $g(n,k) = \binom{n-2}{k-1}$ is the solution. $\endgroup$ – Misha Lavrov Apr 8 '17 at 17:35
  • $\begingroup$ This is great, thank you. We know that this answer has to be bigger than $t(k,k-1) \binom{n}{k-1}$ in your answer to math.stackexchange.com/questions/2222441/…. Is it obvious why this should be the case? $\endgroup$ – felipa Apr 9 '17 at 9:04
  • $\begingroup$ Only asymptotically, and asymptotically $g(n,k) \sim \binom{n}{k-1}$ as $n\to\infty$. $\endgroup$ – Misha Lavrov Apr 9 '17 at 14:33
  • $\begingroup$ Thank you again. Is it simple to show that $\binom{n-2}{k-1} + \binom{n-3}{k-2} \sim {n \choose k-1}$ as $n \to \infty$? $\endgroup$ – felipa Apr 9 '17 at 14:54
  • 1
    $\begingroup$ We can ignore the lower-order term $\binom{n-3}{k-2}$, and $\binom{n-2}{k-1} \sim \binom{n}{k-1}$ because they are both degree $k-1$ polynomials in $n$ with leading term $\frac1{(k-1)!}$. $\endgroup$ – Misha Lavrov Apr 9 '17 at 14:57

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.