Regular bipartite multigraphs have many (but not too many) symmetries
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914071936237568 |
|---|---|
| author | Cameron, Peter J. del Valle, Coen Roney-Dougal, Colva M. |
| author_facet | Cameron, Peter J. del Valle, Coen Roney-Dougal, Colva M. |
| contents | 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\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 $μ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_20002 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Regular bipartite multigraphs have many (but not too many) symmetries Cameron, Peter J. del Valle, Coen Roney-Dougal, Colva M. Combinatorics Group Theory 05C25 (Primary), 60B20 (Secondary) 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\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 $μ(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. |
| title | Regular bipartite multigraphs have many (but not too many) symmetries |
| topic | Combinatorics Group Theory 05C25 (Primary), 60B20 (Secondary) |
| url | https://arxiv.org/abs/2405.20002 |