Let $F_{m,n}$ be the set of spanning forests on the complete bipartite graph $K_{m,n}$. Let $$S_{m,n} = \{(r(M), c(M)), M \in B_{m,n} \}$$ where $B_{m,n}$ is the set of $m \times n$ binary matrices and $r(M), c(M)$ are the vectors of row sums and column sums of $M$, respecitvely. That is, $S_{m,n}$ is the set of the distinct row-sum, column-sum pairs of binary matrices. The term spanning forest here refers to a forest that spans all of the vertices of the given graph, it doesn't have to be a maximal acyclic subgraph.
Q: Is it true that $|F_{m,n}| = |S_{m,n}|$? It is true for $m,n \leq 4$. For $m=n$ this is OEIS A297077.
There is an obvious mapping from $F_{m,n} \rightarrow B_{m,n}$ given by taking the reduced adjacency matrix, so if $U = \{u_1, \ldots, u_m\}$, $V = \{v_1, \ldots, v_m\}$ are the color categories we set $M_{ij} = 1$ if $v_i \sim u_j$ in a forest $F$, else $M_{ij} = 0$. However, this does not help because multiple forests may have the same row and column sums - and not every row-sum, column-sum pair is represented by a forest under this mapping.
The numbers $|F_{m,n}|$ are given here:
$$\begin{array}{|c|c|}\hline m\backslash n & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 2 & \\\hline 2 & 4 & 15 \\\hline 3 & 8 & 54 & 328 \\\hline 4 & 16 & 189 & 1856 & 16145 \\\hline 5 & 32 & 648 & 9984 & 129000 & 1475856 \\\hline\end{array}$$
For more see this answer (sum each row.)
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment