Synchronizing groups and weakly perfect graphs: a survey
Abstract
The concept of synchronization has been transferred from finite automata, via transformation semigroups, to permutation groups: a permutation group G on a finite set Ω is said to be synchronizing if, for any non-permutation t on Ω, the transformation monoid ⟨ G,t⟩ contains an element of rank~$1$. Synchronizing permutation groups are primitive and basic, and so are affine, diagonal, or almost simple (in the O'Nan--Scott classification). In an earlier paper, the author, with João Araújo and Ben Steinberg, surveyed what was known at the time about synchronizing permutation groups. Since then, several new classes of groups have been tested for the synchronizing property, using the fact that a group is non-synchronizing if and only if it preserves a nontrivial weakly perfect graph. Cases studied include diagonal groups with more than two socle factors, two natural actions of symmetric groups, and some actions of classical groups; the proofs are scattered in the literature. My primary purpose is to collect these results with their proofs. As a second objective, I will explain the background, and comment on some related topics. (Reading this paper does not require knowledge of the earlier paper.)
Related
- Perfect state transfer on Cayley graphs over dihedral groups: A complete and practical characterization
- Perfect Codes in Cayley Graphs of Hajós Groups
- Random $3$-regular graphs are not globally synchronizing
- On $4$-perfect-matching covers of cubic graphs with two adjacent odd circuits in a $2$-factor
- Dominated Coloring of Some Classes of Perfect and Unicyclic Graphs
BibTeX
@misc{cameron2026synchronizing,
title = {{Synchronizing groups and weakly perfect graphs: a survey}},
author = {Peter J. Cameron},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12811},
eprint = {2609.12811},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12811},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Synchronizing groups and weakly perfect graphs: a survey
AU - Peter J. Cameron
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.12811
UR - https://arxiv.org/abs/2609.12811
AB - The concept of synchronization has been transferred from finite automata, via transformation semigroups, to permutation groups: a permutation group G on a finite set Ω is said to be synchronizing if, for any non-permutation t on Ω, the transformation monoid ⟨ G,t⟩ contains an element of rank~$1$. Synchronizing permutation groups are primitive and basic, and so are affine, diagonal, or almost simple (in the O'Nan--Scott classification). In an earlier paper, the author, with João Araújo and Ben Steinberg, surveyed what was known at the time about synchronizing permutation groups. Since then, several new classes of groups have been tested for the synchronizing property, using the fact that a group is non-synchronizing if and only if it preserves a nontrivial weakly perfect graph. Cases studied include diagonal groups with more than two socle factors, two natural actions of symmetric groups, and some actions of classical groups; the proofs are scattered in the literature. My primary purpose is to collect these results with their proofs. As a second objective, I will explain the background, and comment on some related topics. (Reading this paper does not require knowledge of the earlier paper.)
ER -