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

Abstract

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 $\ddot{I}‡(k,l)$ and $\hat{I}¼(k,l)$ to be the minimum and maximum order of automorphism groups of $(k,l)$-bipartite graphs, respectively. We determine $\ddot{I}‡(k,l)$ and $\hat{I}¼(k,l)$ for $k\ge 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 $\hat{I}¼(k,l)$. These graphs are intimately connected with both contingency tables with uniform margins and uniform set partitions; we examine the uniform distribution on the set of $k\times k$ contingency tables with uniform margin $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.

25 pages