Is every semiprimitive transitive permutation group graph-restrictive? (the converse implication of the Potočnik–Spiga–Verret conjecture)

For a finite connected graph Γ with a vertex-transitive group G of automorphisms, the local action at a vertex x is the permutation group induced by the vertex stabilizer G_x on the neighbourhood Γ(x); the pair (Γ,G) is locally-L when this local action is a fixed transitive group L at every vertex. A transitive group L is graph-restrictive if there is a constant c(L) bounding the order of the arc stabilizer G_uv in every locally-L pair. Potočnik, Spiga and Verret conjectured that a permutation group is graph-restrictive if and only if it is semiprimitive (every normal subgroup transitive or semiregular), and proved the implication graph-restrictive ⇒ semiprimitive. The open converse — whether every semiprimitive transitive permutation group is graph-restrictive — strictly generalizes the 1978 Weiss conjecture (primitive local actions) and Praeger's quasiprimitive analogue, and remains open. Three of the four small-degree exceptions listed in the source paper have since been positively resolved, leaving the full conjecture open, with Sym(5) on the ten unordered pairs of a 5-set as the smallest surviving unresolved instance.

Background

Let $\Gamma$ be a finite connected graph and let $G$ be a subgroup of $\mathrm{Aut}(\Gamma)$ acting transitively on the vertex set. For a vertex $x$, write $G_x$ for the stabilizer of $x$ and $\Gamma(x)$ for the set of its neighbours; the permutation group induced by $G_x$ on $\Gamma(x)$ is denoted $G_x^{\Gamma(x)}$ and called the local action. A pair $(\Gamma,G)$ is locally-$L$, for a transitive permutation group $L$, if $G_x^{\Gamma(x)}$ is permutation isomorphic to $L$ for every vertex $x$. An arc is an oriented edge, and $G_{uv}$ is the pointwise stabilizer of the arc $(u,v)$. Following Potočnik–Spiga–Verret, a transitive permutation group $L$ is called graph-restrictive if there exists a constant $c(L)$, depending only on $L$, such that $|G_{uv}|\le c(L)$ for every locally-$L$ pair $(\Gamma,G)$ and every arc; equivalently (in the formulation used by Morgan), there is a radius $r$ such that the pointwise stabilizer $G_x^{[r]}$ of the ball of radius $r$ around $x$ is trivial for every locally-$L$ pair, so that $|G_x|$ is bounded in terms of $L$ alone. The concept grew out of Tutte's classical theorem that the stabilizer of a vertex in a finite connected cubic (that is, 3-valent) graph admitting a group of automorphisms transitive on its arcs has order at most 48, which says precisely that the two transitive permutation groups of degree 3 are graph-restrictive.

A transitive permutation group is primitive if it preserves no nontrivial partition of the set it acts on, and semiregular if no nonidentity element fixes a point; a transitive group is semiprimitive if every normal subgroup is transitive or semiregular. This class contains all primitive groups, all quasiprimitive groups (those in which every nontrivial normal subgroup is transitive), and the innately transitive groups (those with a transitive minimal normal subgroup), but also many imprimitive groups. Richard Weiss conjectured in 1978 that for connected finite vertex-transitive graphs whose local action is primitive, the order of a vertex stabilizer is bounded by a function of the valency alone — in the above language, that every primitive group is graph-restrictive. The 2-transitive case (local action transitive on ordered pairs of distinct points) is classical (work of Trofimov and Weiss), as is the case of primitive groups of linear type (containing $\mathrm{PSL}(n,q)$ acting on $m$-subspaces of its natural module); Spiga settled in 2016 the locally affine case, where the local action contains an abelian regular subgroup (a subgroup acting transitively with trivial point stabilizers), thereby completing the affine case of the Weiss conjecture. Trofimov confirmed in 2022, in the first part of an ongoing program, that the Weiss conjecture holds for all primitive local groups except those of almost-simple type (groups lying between a non-abelian simple group and its automorphism group) and product-action type (primitive wreath-product groups acting on a cartesian product of sets) — two classes of the O'Nan–Scott taxonomy, the standard classification of primitive groups by the structure and action of their minimal normal subgroups — which constitute the conjecture's remaining open core. Praeger proposed the analogous conjecture for quasiprimitive groups.

Potočnik, Spiga and Verret (2012) unified these threads: they proved that every graph-restrictive group is semiprimitive (by constructing, from any non-semiprimitive $L$, locally-$L$ pairs with arbitrarily large arc stabilizers) and proposed their Conjecture 3: a permutation group is graph-restrictive if and only if it is semiprimitive. The unproven direction — semiprimitive implies graph-restrictive — is the problem studied here. The accumulated positive evidence includes: all semiprimitive groups of degree at most 13 with four listed possible exceptions (their Proposition 13); an infinite family generalizing Tutte's theorem, proved with the amalgam method — the detailed study of the group amalgam formed by the stabilizers of two adjacent vertices — which raised the smallest open imprimitive degree to 12 (Giudici–Morgan 2014); semiprimitive local actions with a regular nilpotent normal subgroup, handled at valency coprime to 6 with a structure theorem in the remaining cases (Giudici–Morgan 2015); the structure theory of semiprimitive groups via plinths (minimal transitive normal subgroups), showing in particular that semiprimitive groups with more than one plinth are graph-restrictive (Giudici–Morgan 2018); and the whole family $\mathrm{Sym}(n)$ acting on ordered pairs of distinct elements, proved graph-restrictive by Morgan (2023). On the negative side, Mitrović–Verret (2025) identified very large classes of transitive groups with exponential graph growth — vertex stabilizers growing exponentially in the number of vertices, hence not graph-restrictive — but every known such class fails semiprimitivity, and no semiprimitive group is known to fail graph-restrictiveness.

Problem Statement

Is every finite semiprimitive transitive permutation group graph-restrictive? That is: for every finite transitive permutation group $L$ in which each normal subgroup is transitive or semiregular on the point set (such an $L$ is called semiprimitive), does there exist a constant $c(L)$ such that $|G_{uv}|\le c(L)$ for every finite connected graph $\Gamma$ admitting a vertex-transitive group $G\le\mathrm{Aut}(\Gamma)$ whose local action $G_x^{\Gamma(x)}$ — the permutation group induced by the stabilizer $G_x$ of a vertex $x$ on the set $\Gamma(x)$ of its neighbours — is permutation isomorphic to $L$ (equal to $L$ up to a relabelling of the points) at every vertex $x$, and every arc $(u,v)$ of $\Gamma$ (an arc is an oriented edge, and $G_{uv}$ is the pointwise stabilizer of its two endpoints)? Equivalently, is there for every such $L$ a radius $r$ such that the pointwise stabilizer $G_x^{[r]}$ of the ball of radius $r$ about any vertex is trivial in every locally-$L$ pair $(\Gamma,G)$ with this property? This is the unproved implication of Conjecture 3 of Potočnik–Spiga–Verret (the reverse implication, graph-restrictive $\Rightarrow$ semiprimitive, being their Theorem 4), and it implies the Weiss conjecture (every primitive group is graph-restrictive) and Praeger's quasiprimitive analogue. The smallest concrete unresolved instance from the source enumeration is $L=\mathrm{Sym}(5)$ in its primitive action on the ten unordered pairs of a 5-set, and the primitive almost-simple and product-action types constitute the corresponding open core of the Weiss conjecture itself.

References

1. Primož Potočnik, Pablo Spiga, Gabriel Verret, "On graph-restrictive permutation groups", Journal of Combinatorial Theory, Series B 102 (2012) 820–831. DOI: 10.1016/j.jctb.2011.11.006, arXiv:1101.5186, https://doi.org/10.1016/j.jctb.2011.11.006
2. Cheryl E. Praeger, Pablo Spiga, Gabriel Verret, "Bounding the size of a vertex-stabiliser in a finite vertex-transitive graph", Journal of Combinatorial Theory, Series B 102 (2012) 797–819. DOI: 10.1016/j.jctb.2011.11.004, arXiv:1102.1543, https://doi.org/10.1016/j.jctb.2011.11.004
3. Michael Giudici, Luke Morgan, "A class of semiprimitive groups that are graph-restrictive", Bulletin of the London Mathematical Society 46 (2014) 1226–1236. DOI: 10.1112/blms/bdu076, arXiv:1401.3086, https://doi.org/10.1112/blms/bdu076
4. Michael Giudici, Luke Morgan, "On locally semiprimitive graphs and a theorem of Weiss", Journal of Algebra 427 (2015) 104–117. DOI: 10.1016/j.jalgebra.2014.12.017, arXiv:1405.1232, https://doi.org/10.1016/j.jalgebra.2014.12.017
5. Pablo Spiga, "An application of the Local C(G,T) Theorem to a conjecture of Weiss", Bulletin of the London Mathematical Society 48 (2016) 12–18. DOI: 10.1112/blms/bdv071, arXiv:1509.04862, https://doi.org/10.1112/blms/bdv071
6. Michael Giudici, Luke Morgan, "A theory of semiprimitive groups", Journal of Algebra 503 (2018) 146–185. DOI: 10.1016/j.jalgebra.2017.12.040, arXiv:1607.03798, https://doi.org/10.1016/j.jalgebra.2017.12.040
7. Luke Morgan, "Vertex-transitive graphs with local action the symmetric group on ordered pairs", Journal of Group Theory 26 (2023) 519–531. DOI: 10.1515/jgth-2022-0047, arXiv:2010.02070, https://doi.org/10.1515/jgth-2022-0047
8. V. I. Trofimov, "On the Weiss Conjecture. I", Proceedings of the Steklov Institute of Mathematics 319 (2022) S281–S290. DOI: 10.1134/S0081543822060244, https://doi.org/10.1134/S0081543822060244
9. Đorđe Mitrović, Gabriel Verret, "On transitive permutation groups with exponential graph growth", preprint (2025). arXiv:2508.12588, https://arxiv.org/abs/2508.12588
10. Pablo Spiga, "An overview on vertex stabilizers in vertex-transitive graphs", Bollettino dell'Unione Matematica Italiana 18 (2025) 327–346. DOI: 10.1007/s40574-024-00453-4, https://doi.org/10.1007/s40574-024-00453-4