Finite groups admitting a regular tournament $m$-semiregular representation

Dein Wong, Songnian Xu, Chengqi Zhang, Jinxing ZhaoarXiv 2025 · DOI · arXiv

This paper, recently published by researchers from the China University of Mining and Technology and Inner Mongolia University, provides a definitive answer to a specific problem in algebraic graph theory: which finite groups can be represented as the symmetries of a "regular" tournament?

TL;DR

The authors prove that every non-trivial finite group of odd order admits a regular tournament $m$-semiregular representation (TmSR) for any odd integer $m \geq 3$. This result completes the classification of such groups, showing that regularity is achievable for almost all cases where a general representation exists.

What Problem Does This Paper Address?

In the world of algebraic graph theory, a classic challenge is the "representation problem": given an abstract group $G$, can we construct a graph $\Gamma$ such that the group of symmetries (automorphisms) of that graph is exactly $G$?

When the graph is a tournament (a directed graph where every pair of vertices has exactly one directed edge between them), this is called a Tournament Regular Representation (TRR) if the group acts simply transitively on the vertices. However, not all groups have a TRR.

The authors look at a broader version: $m$-semiregular representations (TmSR). Here, the group $G$ acts on the vertices in $m$ different "orbits" (sets of vertices that move into each other under the group's action). A previous researcher, Du, proved that all odd-order groups have a TmSR for $m \geq 2$. But Du left an open question: what if we require the tournament to be regular? In a regular tournament, every vertex must have the exact same number of incoming and outgoing edges. This paper tackles the classification of groups that admit such a representation for odd $m \geq 3$.

Methods

The proof is constructive and combinatorial. The authors don't just prove these representations exist; they show how to build them using $m$-Cayley digraphs.

The researchers partitioned their proof into three main cases based on the number of orbits ($m$) and the size of the group ($n$):

  1. Case I: Large systems where $m \geq 7$, or $m=5$ with group size $n \geq 5$.
  2. Case II: The specific small case where $m=5$ and $n=3$.
  3. Case III: The minimal case of $m=3$.

The core strategy involves "orbit distinguishing." To ensure the automorphism group is exactly $G$, the authors carefully select subsets of the group to define the edges (arcs) such that one specific orbit has a unique "local" structure. By analyzing the in-degrees and out-degrees of vertices within specific sub-graphs, they prove that no symmetry can swap these orbits unless it belongs to the group $G$ itself.

Datasets

Not applicable. This is a theoretical mathematics paper based on formal proofs and group theory constructions. No external datasets or benchmarks were used.

Key Insights and Ideas

  • The Parity Constraint: A tournament can only be regular if it has an odd number of vertices. Since the total number of vertices in an $m$-semiregular representation is $m \times |G|$, and $|G|$ must be odd for tournaments to work, it follows that $m$ must also be odd.
  • Breaking Symmetry via Local Degrees: The "aha moment" in the proof is the use of the least in-degree ($\delta_i$) and least out-degree ($\pi_i$) of induced subgraphs to distinguish orbits. By showing that one orbit has a vertex with a unique degree profile, the authors "pin" the group's action, preventing unwanted extra symmetries.
  • Handling the "Troublemakers": Most odd-order groups have a standard TRR (proven by Godsil in 1986), but two specific groups—$\mathbb{Z}_3^2$ and $\mathbb{Z}_3^3$—do not. The authors had to develop specialized arc-set constructions specifically for these cases to ensure regularity was maintained.

Key Results

The main result is Theorem 1.2:

Let $G$ be a finite group of order $n > 1$. Then $G$ admits a regular TmSR, with $m > 1$, if and only if $n$ and $m$ are odd integers.

This provides a complete classification for all non-identity groups. If you have a group of odd order (greater than 1) and an odd number of orbits (greater than 1), you can always find a regular tournament that represents that group.

Limitations and Future Work

The authors explicitly note one remaining "missing" piece: the trivial group $\mathbb{Z}_1$ (the group consisting only of the identity element).

  • It is already known that $\mathbb{Z}_1$ has no regular T3SR.
  • The authors prove in this paper that it also has no regular T5SR.
  • They conjecture that $\mathbb{Z}_1$ admits no regular TmSR for any odd $m \geq 7$, but they admit that a general proof for this remains "elusive" due to the increasing complexity of larger tournaments.

Summary updated

Abstract

For a positive integer $m$, a finite group $G$ is said to admit a tournament $m$-semiregular representation (TmSR for short) if there exists a tournament $Γ$ such that the automorphism group of $Γ$ is isomorphic to $G$ and acts semiregularly on the vertex set of $Γ$ with $m$ orbits. Clearly, every finite group of even order does not admit a TmSR for any positive integer $m$, and T1SR is the well-known tournament regular representation (TRR for short). In 1986, Godsil \cite{god} proved, by a probabilistic approach, that the only finite groups of odd order without a TRR are $\mathbb{Z}_3^2$ and $\mathbb{Z}_3^3$ . More recently, Du \cite{du} proved that every finite group of odd order has a TmSR for every $m \geq 2$. The author of \cite{du} observed that a finite group of odd order has no regular TmSR when $m$ is an even integer, a group of order $1$ has no regular T3SR, and $\mathbb{Z}_3^2$ admits a regular T3SR. At the end of \cite{du}, Du proposed the following problem. \noindent{\sf\it Problem.} \ \ {\it For every odd integer $m\geq 3$, classify finite groups of odd order which have a regular TmSR.} The motivation of this paper is to give an answer for the above problem. We proved that if $G$ is a finite group with odd order $n>1$, then $G$ admits a regular TmSR for any odd integer $m\geq 3$.
BibTeX
@misc{wong2025finite,
  author = {Dein Wong and Songnian Xu and Chengqi Zhang and Jinxing Zhao},
  title = {{Finite groups admitting a regular tournament $m$-semiregular representation}},
  year = {2025},
  eprint = {2501.13406},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.13406},
  howpublished = {arXiv},
}
Figure