11
$\begingroup$

Let $U = \{u_1, u_2, \ldots , u_m \}$ where each $u_i$ is an $r$-subset of $[n]$ and $\,\bigcup u_i \!=\! [n]$. Construct the intersection graph of $U$. That is, let node $i$ correspond to $u_i$ and add edge $(i,j)$ if $u_i \cap u_j \neq \emptyset$. For example, suppose $n=8$ and $U = \{123, 124, 234, 567, 568\}$. The intersection graph is

$\qquad \qquad \qquad \qquad \qquad \qquad \quad $ enter image description here

We notice there are two connected components, ie. $\mathcal{C}(U)=2$. Given $n,r,m$ how many sets have exactly $c$ connected components?

$$ \begin{array}{ll} T_{n,r,m}(c) &= \displaystyle \left[x^c\right] \sum_{\left|U\right| = m} x^{\mathcal{C}(U)} \\ &= \displaystyle \left[y^m x^c\right] \sum_U y^{\left|U\right|} x^{\mathcal{C}(U)} \end{array} $$

Can we come up with an expression for $T_{n,r,m}(c)$ or at least some way to efficiently compute it? I would be happy with an algorithm where $n \le 50, r \le 10$ is tractable. I've enumerated all the nonzero values for $n\le6$ to use for verification.


I've posted a partial answer that reduces the problem to counting $T_{n,r,m}(1)$, the sets with a fully connected graph.

$\endgroup$
1
+250
$\begingroup$

New Notations: Always fix $r$. Suppose $L=(c_1, c_2, \ldots, c_l)$ is a list of non-decreasing natural numbers. Denote by $|L|$ ($=l$) the length of the list and $\sum L = c_1 + \ldots + c_l$ the sum of entries in $L$. Let $T(n, L)$ count the number of sets $U = \{u_1, \ldots, u_{m}\}$, where $m=\sum L$, each $u_i$ is an $r$-subset of $[n]$ and $\cup U = [n]$, whose intersection graph have exactly $l$ connected components with sizes $c_1, c_2, \ldots, c_l$.

Relation with the Old Notation: $$T_{n,m}(c)=\sum_{|L| = c, \sum{L}=m}T(n, L).$$

Inductive Property:

  1. If $L = L_1+L_2$ (list concatenation) such that $L_1 < L_2$ (i.e., all entries in $L_1$ is less than the ones in $L_2$), then $$T(n,L)=\sum_{n_1+n_2=n} {n\choose n_1} T(n_1, L_1)T(n_2, L_2).$$
  2. Suppose $L = (c,c,\ldots, c) =: (c)^l$, where $l=|L|$. We have $$T(n, L)=\sum_k\sum_{l_1 + \ldots + l_k = l}\frac{1}{l_1!\ldots l_k!}\sum_{\ n_1 < \ldots < n_k}\frac{n!}{(n_1!)^{l_1}\ldots(n_k!)^{l_k}}1_{l_1n_1 + \ldots + l_kn_k=n}T(n_1, (c))^{l_1}\ldots T(n_k, (c))^{l_k}.$$

Boundary Condition: $T(n, L)=0$ if $n < r$ or $n > r|L|$.

Restriction Formula: Note that the total number of sets $U = \{u_1, \ldots, u_m\}$ each $u_i$ is an $r$-subset of $[n]$ is equal to $${{n\choose r}\choose m}.$$ On the other hand, one can count it using $T_{n,m}(c)$ according to $\cup U$. We get the total number of $U$ is equal to $$\sum_{n_0\leq n}{n\choose n_0}\sum_cT_{n_0, m}(c) = \sum_{n_0\leq n}{n\choose n_0}\sum_l\sum_{|L| = l, \sum{L}=m}T(n_0, L).$$ Therefore we have $$\sum_{n_0\leq n}{n\choose n_0}\sum_l\sum_{|L| = l, \sum{L}=m}T(n_0, L) = {{n\choose r}\choose m}.$$ We rewrite it as $$T(n,(m)) = {{n\choose r}\choose m} - \sum_{n_0 < n}{n\choose n_0}\sum_l\sum_{|L| = l, \sum{L}=m}T(n_0, L) - \sum_{l>1}\sum_{|L| = l, \sum{L}=m}T(n, L)$$

Punch Line: Define $(n_0, L_0) < (n, L)$ if $n_0 < n$ or $n_0 = n$ but $|L_0| > |L|$. Clearly, one can use the inductive properties, the boundary condition and the restriction formula to compute $T(n,L)$ once $T(n_0,L_0)$ are given for all $(n_0, L_0)< (n,L)$ (call $(n,L)$ complexity of $T(n,L)$) since in all formulas involved the complexity on the right hand side is always less than the complexity on the left hand side.

Update: For computational reasons (as OP mentioned in the comment), one may want to replace the inductive property 2 by a simpler recursion $$T(n,(c)^l)=\sum_{k}{n-1\choose k-1}T(k,(c))T(n-k,(c)^{l-1}).$$ Again the idea in the inductive properties is indeed based on OP's answer.

$\endgroup$
7
  • $\begingroup$ Very nice and thank you for taking the time! The trick at the end seems to be what I was missing in my relations (assuming they are error-free). I get $\; T_{n,m} = {{n \choose r} \choose m} - \sum_{c>1} T_{n,m}^{c,\infty} - \sum_{\kappa<n} {n \choose \kappa} \sum_{c} T_{\kappa, m}^{c, \infty}$ $\endgroup$ – Andrew Szymczak Mar 19 '15 at 6:48
  • $\begingroup$ This is actually very similar to my initial idea (partitioning the graph by $L$) which I tried to encapsulate in my recurrences; if you expand the triple summation for $T_{n,m}^{c,\ell}$ you'll see that you end up with every possible partition $L$ in conjunction with your equation (1.). The main difference between our relations is the case when $L=(c,c,\ldots,c)=(c)^l$ where $l>1$. This is your equation (2.) and my equation for $T_{n}^{l \, \times \, c}$. $\endgroup$ – Andrew Szymczak Mar 19 '15 at 8:39
  • $\begingroup$ In (2.) you specify that there are $l_i$ components that cover $n_i$ elements and you take care of overcounting with the factors $\frac{1}{\prod l_i!}$ and ${n \choose n_1 \ldots n_1 \ldots n_k \ldots n_k} \delta_{\boldsymbol{l} \cdot \boldsymbol{n}, n} $. This looks correct to me. See if you find anything wrong with my idea; we pick the component that covers "1" and then recurse. $ T_{n}^{l \, \times \, c} = \sum_{\kappa < n} {n-1 \choose \kappa-1} \, T_{\kappa,c} \, T_{n-\kappa}^{(l-1) \, \times \, c} $ $\endgroup$ – Andrew Szymczak Mar 19 '15 at 8:45
  • $\begingroup$ This is equivalent to $$ \begin{array} {lrl} T_{n}^{l \, \times \, c} &= \displaystyle \sum_{n_1 + \ldots + n_l=n} & {n-1 \choose n_1-1} {n-n_1-1 \choose n_2-1} \ldots {n-\ldots -n_{l-1} - 1 \choose n_l-1} \, T_{n_1,c} \ldots T_{n_l,c} \\ &= \displaystyle \sum_{n_1 + \ldots + n_l=n} & \displaystyle (n-1)! \prod_i \frac{T_{n_i,c}}{(n_i - 1)! \,\left(\delta_{i,l} + \sum_{j>i} n_j \right)} \end{array}$$ $\endgroup$ – Andrew Szymczak Mar 19 '15 at 8:46
  • $\begingroup$ You are welcome. My solution is indeed inspired by your partial solution. I just find it more clear for me to think in terms of "list". The real innovation lies in the restriction formula which was missing in your approach. $\endgroup$ – Zilin J. Mar 19 '15 at 11:39
1
$\begingroup$

I recently came up with a faster solution to this problem that reduces the recurrence dimension by 1.

Let $T_r(n, m, c)$ represent the number we are looking for, ie. the number of ways to take $m$ subsets of $[n]$ such that each subset has size $r$, the subsets cover $[n]$, and their intersection graph has $c$ connected components. I made $r$ a subscript because it is held fixed throughout. The logic is similar to $T_n^{c \times \ell}$ in my answer above. Consider the connected component that covers the element "1" from the ground set. Suppose it consists of $s$ subsets and that it covers $k$ total elements. There are $\binom{n - 1}{k - 1}$ ways to choose the covered elements which leads to the recurrence for $c > 1$.

$$T_r(n, m, c) = \sum_{k} \sum_{s} \binom{n - 1}{k - 1} \; T_r(n\!-\!k, \,m\!-\!s,\,c\!-\!1) \; T_r(k, s, 1) $$

For connected graphs $c = 1$ we get the same restriction formula from before: all the possible graphs given $m$ minus those that don't cover $[n]$ minus those that have more than 1 connected component.

$$ T_r(n, m, 1) \; = \; {{n \choose r} \choose m} \; - \; \sum_{k \, < \, n} \sum_{c} {n \choose k} T_r(k, m, c) \; - \; \sum_{c \, > \, 1} T_r(n, m, c)$$

$\endgroup$
0
$\begingroup$

Here is a partial answer, which reduces the problem to counting $T_{n,r,m}(1)$, that is, counting the number of sets that have a connected intersection graph ($c=1$). The reduction occurs through a recurrence, with $c=1$ corresponding to the base cases. First let me change the notation. Let $r$ be given as before. Since $r$ is held fixed, I suppress it as an index.

$$ \; $$

  • $T_{n,m}^{c,\ell}$ : This is the same as the old notation $T_{n,r,m}(c)$ with the added constraint that each connected component has less than $\ell$ nodes.

  • $T_{n}^{c\,\times\,\ell}$ : constrains the graph to have exactly $c$ connected components of size $\ell$. The number of nodes is suppressed as an index since it is forced to equal $c\ell$.

  • $T_{n,m} = T_{n,m}^{1,\, \ell_{ > m}} = T_{n}^{1 \, \times \, m}$ : counts the number of connected graphs on $m$ nodes.

$$ \; $$

Remember that for all three of these, each node corresponds to an $r$-subset and their union must equal $[n]$. To compute $T_{n,m}^{c,\ell}$, let $\gamma$ denote the size of the largest connected component, let $\varsigma$ be the number of components of size $\gamma$, let $\kappa$ be the the number of elements covered by such components, and then recurse.

$$ T_{n,m}^{c,\ell} = \sum_{\gamma \,<\, \ell} \; \sum_{\varsigma \,\le\, c} \; \sum_{\kappa \, \le \, n} {n \choose \kappa}\; T_{\kappa}^{\varsigma \, \times \, \gamma} \; T_{n-\kappa,\,m-\gamma\varsigma}^{c-\varsigma,\,\gamma} $$

Note the summation limits can often be pruned. The ${n \choose \kappa}$ picks the elements of $[n]$ covered by the large components. To compute $T_{n}^{c \, \times \ell}$ for $c>1$ we enforce that the "first" component to be the one that covers element "1" and we suppose that it covers $\kappa$ total elements. Then we recurse.

$$ T_{n}^{c \, \times \, \ell} = \sum_{\kappa \, < \, n} {n-1 \choose \kappa - 1} \; T_{\kappa, \ell} \; T_{n-\kappa}^{(c-1) \, \times \, \ell} $$

Thus the problem has been reduced to counting the connected graphs $T_{n,m}$.

Update @roy's restriction formula: by summing over $c$ and picking out the term $T_{n,m}$ we get the expression

$$ T_{n,m} \; = \; {{n \choose r} \choose m} \; - \; \sum_{\kappa \, < \, n} \sum_{c} {n \choose \kappa} T_{\kappa,m}^{c, \infty} \; - \; \sum_{c \, > \, 1} T_{n,m}^{c,\infty}$$

note the third term on the RHS does not produce a $T_{n,m}$ (so there is no cancellation).

$\endgroup$
6
  • $\begingroup$ I am a bit confused by your formula on $T_n^{c\times l}$. How do you specify "the first component"? It is not clear to me that there is an order between the components. When there are two components of size $k$, it seems the formula is over-counting. $\endgroup$ – Zilin J. Mar 19 '15 at 4:27
  • $\begingroup$ @roy_24601 You are right. It seems I imposed an ordering on the nodes and then forgot to enforce it in $T_{n}^{c \, \times \, \ell}$. Which means I should get rid of $\frac{1}{\varsigma!} {m \choose \gamma\varsigma} {\gamma\varsigma \choose \gamma \ldots \gamma}$ in the formula for $T_{n,m}^{c,\ell}$. Now for $T_{n}^{c \, \times \, \ell}$, if I enforce that the "first" component contains the smallest element in the ground set "[n]", then the multiplicative factor becomes ${n \choose \kappa-1}$. I think this is correct. I have yet to read your answer so give me a moment. $\endgroup$ – Andrew Szymczak Mar 19 '15 at 5:46
  • $\begingroup$ Whoops should be ${n-1 \choose \kappa-1}$ $\endgroup$ – Andrew Szymczak Mar 19 '15 at 7:41
  • $\begingroup$ It looks correct to me now. Nice fix! $\endgroup$ – Zilin J. Mar 19 '15 at 11:44
  • $\begingroup$ @roy_24601 I've verified the recurrences btw (they match the brute-forced values that I listed). If you're interested, here is the code and all the values for $r=2, n\le20$. $\endgroup$ – Andrew Szymczak Mar 20 '15 at 22:14

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.