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

Regular bipartite multigraphs have many (but not too many) symmetries, Discrete Analysis 2025:22, 25 pp.

This paper concerns the automorphism groups of \(l\)-regular bipartite multigraphs with \(k\) vertices on each side, in the regime where \(k\) is fixed and \(l\) tends to infinity (so there are necessarily highly multiple edges). The vertex sets are considered to be coloured, so as to rule out automorphisms that exchange them. The authors call these objects \((k,l)\)-bipartite multigraphs.

As one might expect, the range of possibilities for the size of the automorphism group of a \((k,l)\)-bipartite graph is very large. One of the main results of the paper is to determine the largest and smallest possible size when \(k\geq 8\). (This assumption is for somewhat technical reasons, and rules out certain types of behaviour that occur only for very small \(k\).) It is relatively straightforward to show that the example with the most symmetries is a disjoint union of \(k\) pairs of vertices, with each pair joined by \(l\) edges, which has \(k!(l!)^k\) automorphisms.

Note that an automorphism here does not just mean a permutation of the vertices that preserves the edge relationships, but rather a permutation of the vertices and edges that preserves them. Thus, if between vertices \(x\) and \(y\) there are \(d(x,y)\) edges, then the number of automorphisms is at least \(\prod_{x,y}d(x,y)!\), from which one can obtain a lower bound of \((l/k)^{k^2}\). The bound obtained by the authors is of this broad form, but is more complicated, depending in a subtle way on the remainder when \(l\) is divided by \(k\), and is sharp. The very broad strategy the authors use is to construct a particular example and to show that any other example has a strictly larger automorphism group. However, there are a few exceptional cases where the proof breaks down, and these have to be dealt with separately.

They also show that the number of symmetries of a typical \((k,l)\)-bipartite multigraph is, again as one might expect, much closer to the lower bound than to the upper bound. Intuitively, the main reason for this is that the edge multiplicities of a random \((k,l)\)-bipartite multigraph have considerable variance, which makes it hard to find symmetries that move vertices.

Note that there is an obvious one-to-one correspondence between \((k,l)\)-bipartite multigraphs and \(k\times k\) matrices with row and column sums that add up to \(l\) – that is, up to a scaling factor, doubly stochastic matrices. This is the perspective taken by the authors. Another way they view \((k,l)\)-multigraphs is as intersection matrices: one takes two partitions of \(\{1,2,\dots,kl\}\) into \(k\) sets of size \(l\) and defines \(A_{ij}\) to be the size of the intersection of the \(i\)th cell of the first partition and the \(j\)th cell of the second. One can show that every \(k\times k\) matrix with row and column sums adding up to \(l\) can be realized in this way.

They also make an observation about non-synchronizing permutation groups. A permutation group \(G\) is a group that has been explicitly realized as a group of permutations of \(\{1,2,\dots,n\}\) for some \(n\): that is, it is a group together with an injective homomorphism into \(S_n\). It is said to be synchronizing if for every function \(f:\{1,2,\dots,n\}\to\{1,2,\dots,n\}\) that is not a permutation, the monoid generated by \(G\) and \(f\) contains a constant map. This concept comes from automata theory: the sequence of transformations that yields the constant map is called a “reset word” because it can be used to reset all states to a particular given state.

The authors consider the actions of \(S_{kl}\) and \(A_{kl}\) on the set \(\mathcal P(k,l)\) of the partitions mentioned above: that is, partitions of a set of size \(kl\) into \(k\) sets of size \(l\). (Note that while \(S_{kl}\) and \(A_{kl}\) are usually defined as the group of permutations of \(\{1,2,\dots,kl\}\) and the group of even permutations of \(\{1,2,\dots,kl\}\), here we are considering them as groups of permutations of a much larger set.) They show that the resulting permutation groups are non-synchronizing, making use of a known result that a permutation group is non-synchronizing if and only if it is contained in the automorphism group of a graph (that is not a complete or an empty graph) with clique number equal to its chromatic number. The graph they take in this case has vertex set \(\mathcal P(k,l)\), with two partitions joined if and only if they have no cell in common.