I am studying proper colorings of complete bipartite graphs and I'd like to be able to pick a random proper coloring and the compute some things about it.

Recall that a proper coloring of a complete bipartite graph is precisely a latin rectangle where the $(i,j)$ entry is the color on the edge from vertex $i$ to vertex $j$.

My questions are generally of the form "for a large $m$ and $n$, is there a positive probability that the random proper coloring of $K_{m,n}$ has a copy of the subgraph $H$ which has a specific coloring?"

Thanks for your insights!


Have you seen this paper: http://cs.anu.edu.au/~Brendan.McKay/papers/randomlatin.pdf ? It seems to solve your problem.

  • $\begingroup$ Thanks for the response! I did not know of this paper. After a cursory read through it is not clear how to use their algorithm to answer questions, like what is the probability of having a copy of subgraph $H$ that has all different colors. Is it clear to you how to proceed using tools of probability? In either case I will read through it in detail soon. Thanks agian. $\endgroup$ – user43928 Mar 24 '15 at 2:41

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.