Regular bipartite multigraphs have many (but not too many) symmetries

Let k and l be integers, both at least 2. A (k,l)-bipartite graph is an l-regular bipartite multigraph with coloured bipartite sets of size k. Define χ(k,l) and μ(k,l) to be the minimum and maximum order of automorphism groups of (k,l)-bipartite graphs, respectively. We determine χ(k,l) and μ(k,l) for k≥8, and analyse the generic situation when k is fixed and l is large. In particular, we show that almost all such graphs have automorphism groups which fix the vertices pointwise and have order far less than μ(k,l). These graphs are intimately connected with both integer doubly-stochastic matrices and uniform set partitions; we examine the uniform distribution on the set of k×k integer doubly-stochastic matrices with all line sums l, showing that with high probability all entries stray far from the mean. We also show that the symmetric group acting on uniform set partitions is non-synchronizing.