# How to choose a random proper coloring

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 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. – user43928 Mar 24 '15 at 2:41