What proportion of perfect matchings of a complete k-partite graph contain a specific pair?

26 Views Asked by At

(This is a follow on question from this.)

Suppose I have a $k$-partite graph with $n_1, n_2, .., n_k$ vertices in each part.

I am interested in the probability that in a random perfect matching, a given vertex in part $1$ is paired with a vertex in part $2$, and its behaviour asymptotically as the values of the $n_i$ get large but their ratio remain the same.

By the excellent answer on my previous question linked above, we can find a recursive formula for $f(n_1, n_2, ..., n_k)$, the number of perfect matchings for a $k$-partite graph as described above.

Computationally, we can evaluate the probability I am interested in by calculating $$\frac{n_2 f(n_1-1, n_2-1, n_3, ..., n_k)}{f(n_1, n_2, ..., n_k)}$$ calling the recursive function of $f$.

If I calculate $$\frac{pn_2 f(pn_1-1, pn_2-1, pn_3, ..., pn_k)}{f(pn_1, pn_2, ..., pn_k)}$$ for integers $p$, it appears that as $p$ gets large, the ratio converges to some value. The function also appears to be decreasing.

The $k=3$ case has constant ratio for all $p$. This is explained by the closed form given in the answer to my previous question, where the $p$s can cancel when we calculate the ratio. However, for $k > 3$, it is not a constant for most $n_1, ..., n_k$.

What value is this ratio converging to?