  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 $\chi(k,l)$ and $\mu(k,l)$ to be the minimum and maximum order of
automorphism groups of $(k,l)$-bipartite graphs, respectively. We determine
$\chi(k,l)$ and $\mu(k,l)$ for $k\geq 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 $\mu(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\times 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.
