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$):
- Case I: Large systems where $m \geq 7$, or $m=5$ with group size $n \geq 5$.
- Case II: The specific small case where $m=5$ and $n=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