Regular bipartite multigraphs have many (but not too many) symmetries
| Autor: | Cameron, Peter J., del Valle, Coen, Roney-Dougal, Colva M. |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 18 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|