Bounding vertex-stabilisers in finite vertex-transitive graphs: the Weiss, Praeger, and PSV conjectures

The Weiss Conjecture (1978), the Praeger Conjecture (1998), and the PSV Conjecture of Potočnik–Spiga–Verret ask whether the order of the stabiliser $G_\alpha$ of a vertex in a finite connected $G$-vertex-transitive graph of valency $d$ is bounded by a function of $d$ alone when the local action of $G_\alpha$ on the neighbours of $\alpha$ is primitive, quasiprimitive, or semiprimitive, respectively. The conjectures are nested, and the 2012 paper of Praeger, Spiga and Verret reduced them to boundedness questions for vertex-transitive actions of nonabelian simple groups, while posing auxiliary problems on which local properties survive this reduction and on the optimality of the resulting transfer functions. The literature through 2025 records substantial partial results — small valency, abelian or nilpotent local structure, bounded-rank composition factors, and all non-almost-simple types of primitive local action — but all three conjectures remain open.

Background

Let $\Gamma$ be a finite simple graph and let $G\le\mathrm{Aut}(\Gamma)$ act transitively on the vertex set $V\Gamma$; then $\Gamma$ is $G$-vertex-transitive, and its valency $d$ (the number of neighbours of a vertex) is constant. The vertex-stabiliser $G_\alpha$ of a vertex $\alpha$ measures how much symmetry is concentrated at $\alpha$, and the central question here is when $|G_\alpha|$ is controlled by $d$ alone. The permutation group induced by $G_\alpha$ on the neighbour set $\Gamma(\alpha)$ is the local action, denoted $G_\alpha^{\Gamma(\alpha)}$; the pair $(\Gamma,G)$ is locally primitive (respectively locally quasiprimitive, locally semiprimitive) when this group is primitive (respectively quasiprimitive, semiprimitive). A permutation group is primitive if it is transitive and preserves no nontrivial partition of the set it acts on; quasiprimitive if every nontrivial normal subgroup is transitive; semiprimitive if every normal subgroup is transitive or semiregular (semiregular meaning every nontrivial element fixes no point). These classes are nested: primitive implies quasiprimitive implies semiprimitive. Since a primitive group is transitive, local primitivity forces $G$ to be transitive on arcs (ordered pairs of adjacent vertices).

Write $\mathcal{A}(d)$ for the pairs $(\Gamma,G)$ with $\Gamma$ a connected $G$-vertex-transitive graph of valency at most $d$; $(\Gamma,G)$ is $f$-bounded, for a function $f:\mathbb{N}\to\mathbb{N}$, if $|G_\alpha|\le f(d)$ for every vertex $\alpha$. Tutte's classical bound $|G_v|\le 48$ for connected arc-transitive graphs of valency 3 is the prototype of an $f$-boundedness theorem. Gardiner (1973) showed that in a locally primitive graph the pointwise stabiliser of two adjacent vertices together with all their neighbours is a $p$-group, and a series of refinements led Richard Weiss to conjecture in 1978 that local primitivity alone should force boundedness. The analogous statement with $G$ primitive on vertices is the Sims conjecture, proved by Cameron–Praeger–Saxl–Seitz (1983) using the classification of finite simple groups (CFSG, the theorem listing all finite simple groups); those maximal-subgroup methods do not transfer to the merely locally primitive setting. The locally 2-transitive case of Weiss's conjecture was settled through Trofimov's series of papers on graphs with projective suborbits, culminating in 1994, and Conder–Li–Praeger (2000) proved boundedness for six of the eight O'Nan–Scott types of quasiprimitive vertex actions (the O'Nan–Scott subdivision sorting each quasiprimitive group into one of eight structural types; the product-action argument contained an error, and a counterexample appears in the 2012 source paper).

The paper Praeger–Spiga–Verret (J. Combin. Theory Ser. B, 2012) reduced the conjectures to questions about simple groups. Its Theorems 4 and 5 state that if $(\Gamma,G)\in\mathcal{A}(d)$ with $G$ quasiprimitive or biquasiprimitive on vertices (biquasiprimitive meaning that $G$ is transitive, not quasiprimitive, and every nontrivial normal subgroup of $G$ has at most two orbits) and socle factor $T$ (the simple group underlying the socle, the product of the minimal normal subgroups), then either $(\Gamma,G)$ is explicitly bounded, or it uniquely determines a $T$-vertex-transitive pair $(\Lambda,T)$ (respectively two pairs $(\Lambda_i,T)$ of valency at most $d(d-1)$) whose boundedness transfers back to $(\Gamma,G)$ modulo explicit transfer functions that blow bounds up by factorial-type factors (Theorem 10). Praeger's normal-quotient technique (collapsing the orbits of a suitable normal subgroup) reduces general pairs to quasiprimitive or biquasiprimitive ones while preserving local primitivity and quasiprimitivity. In parallel, Potočnik–Spiga–Verret (2012) introduced the graph-restrictive framework: a transitive permutation group $L$ is graph-restrictive if $|G_v|\le c(L)$ for every pair that is locally-$L$ (local action permutation-isomorphic to $L$). They proved that every graph-restrictive group is semiprimitive and proposed the converse, the PSV Conjecture, which is exactly the statement that local semiprimitivity implies $f$-boundedness and which implies both the Praeger and the Weiss conjectures.

Problem Statement

All graphs are finite, simple and connected. Let $\Gamma$ be such a graph and let $G\le\mathrm{Aut}(\Gamma)$ act transitively on the vertex set $V\Gamma$, so that the valency $d$ (the number of neighbours of a vertex) is constant. For a vertex $\alpha$, write $G_\alpha$ for the stabiliser of $\alpha$ in $G$, and write $G_\alpha^{\Gamma(\alpha)}$ for the permutation group induced by $G_\alpha$ on the neighbour set $\Gamma(\alpha)$ (the local action). A permutation group is semiprimitive if every normal subgroup is transitive or semiregular (semiregular meaning that every non-identity element fixes no point), quasiprimitive if every non-identity normal subgroup is transitive, and primitive if it is transitive and preserves no nontrivial partition of the underlying set. The pair $(\Gamma,G)$ is locally semiprimitive (respectively locally quasiprimitive, locally primitive) when $G_\alpha^{\Gamma(\alpha)}$ has the corresponding property at every vertex $\alpha$. Write $\mathcal{A}(d)$ for the pairs $(\Gamma,G)$ of valency at most $d$; a pair $(\Gamma,G)\in\mathcal{A}(d)$ is $f$-bounded, for a function $f:\mathbb{N}\to\mathbb{N}$, if $|G_\alpha|\le f(d)$ for every vertex $\alpha$.

Decide whether there exists a function $f:\mathbb{N}\to\mathbb{N}$ such that

$$|G_\alpha|\le f(d)$$

for every vertex $\alpha$ of every locally semiprimitive pair $(\Gamma,G)\in\mathcal{A}(d)$ (PSV Conjecture). The two weaker levels of the same question replace locally semiprimitive by locally quasiprimitive (Praeger Conjecture, 1998) and by locally primitive (Weiss Conjecture, 1978). Since primitive implies quasiprimitive implies semiprimitive, the PSV Conjecture implies the Praeger Conjecture, which implies the Weiss Conjecture; a counterexample at the Weiss level refutes all three. Each of the three levels is a distinct conjecture, and its negation is an explicit infinite family of connected $G$-vertex-transitive graphs of some fixed valency $d$, locally semiprimitive (respectively locally quasiprimitive, locally primitive, according to the level), whose vertex-stabilisers have unbounded order. A counterexample at the Praeger level likewise refutes the PSV statement, while a proof at the Weiss or the Praeger level leaves the stronger displayed levels open.

The auxiliary Problem 8 of the source paper, on which properties of $(\Gamma,G)$ are inherited by the reduced pairs $(\Lambda,T)$ and $(\Lambda_i,T)$, and the optimality of the factorial transfer functions of Theorem 10, are separate questions and are not part of the question posed above.

References

1. 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, https://doi.org/10.1016/j.jctb.2011.11.004 (arXiv:1102.1543)
2. 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, https://doi.org/10.1016/j.jctb.2011.11.006 (arXiv:1101.5186)
3. Marston D. Conder, Cai Heng Li, Cheryl E. Praeger, On the Weiss conjecture for finite locally primitive graphs, Proceedings of the Edinburgh Mathematical Society (2) 43 (2000) 129-138. DOI: 10.1017/S0013091500020745, https://doi.org/10.1017/S0013091500020745
4. Cheryl E. Praeger, László Pyber, Pablo Spiga, Endre Szabó, Graphs with automorphism groups admitting composition factors of bounded rank, Proceedings of the American Mathematical Society 140 (2012) 2307-2318. DOI: 10.1090/S0002-9939-2011-11100-6, https://doi.org/10.1090/S0002-9939-2011-11100-6
5. Pablo Spiga, On G-locally primitive graphs of locally Twisted Wreath type and a conjecture of Weiss, Journal of Combinatorial Theory, Series A 118 (2011) 2257-2260. DOI: 10.1016/j.jcta.2011.05.005, https://doi.org/10.1016/j.jcta.2011.05.005
6. 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, https://doi.org/10.1112/blms/bdv071 (arXiv:1509.04862)
7. 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, https://doi.org/10.1112/blms/bdu076 (arXiv:1401.3086)
8. 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, https://doi.org/10.1016/j.jalgebra.2014.12.017 (arXiv:1405.1232)
9. Michael Giudici, Luke Morgan, A theory of semiprimitive groups, Journal of Algebra 503 (2018) 146-185. DOI: 10.1016/j.jalgebra.2017.12.040, https://doi.org/10.1016/j.jalgebra.2017.12.040 (arXiv:1607.03798)
10. Pablo Spiga, Gabriel Verret, On intransitive graph-restrictive permutation groups, Journal of Algebraic Combinatorics 40 (2014) 179-185. DOI: 10.1007/s10801-013-0482-5, https://doi.org/10.1007/s10801-013-0482-5 (arXiv:1211.3347)
11. Primož Potočnik, Pablo Spiga, Gabriel Verret, Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs, Journal of Combinatorial Theory, Series B 111 (2015) 148-180. DOI: 10.1016/j.jctb.2014.10.002, https://doi.org/10.1016/j.jctb.2014.10.002 (arXiv:1010.2546)
12. Primož Potočnik, Pablo Spiga, Gabriel Verret, Tetravalent arc-transitive graphs with unbounded vertex-stabilisers, arXiv:1010.2549 (2010), https://arxiv.org/abs/1010.2549
13. 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, https://doi.org/10.1515/jgth-2022-0047 (arXiv:2010.02070)
14. V. I. Trofimov, On the Weiss conjecture. I, Proceedings of the Steklov Institute of Mathematics 319, Suppl. 1 (2022) S281-S290. DOI: 10.1134/S0081543822060244, https://doi.org/10.1134/S0081543822060244 (translation of Trudy Instituta Matematiki i Mekhaniki 28, No. 1 (2022) 247-256)
15. V. I. Trofimov, A graph with a locally projective vertex-transitive group of automorphisms Aut(Fi22) which has a nontrivial stabilizer of a ball of radius 2, Proceedings of the Steklov Institute of Mathematics 323, Suppl. 1 (2023) S300-S304. DOI: 10.1134/S0081543823060238, https://doi.org/10.1134/S0081543823060238
16. V. I. Trofimov, Graphs with projective suborbits, cases of small characteristics, I, Izvestiya Rossiiskoi Akademii Nauk, Seriya Matematicheskaya 58, No. 5 (1994) 124-171; English translation in Izvestiya: Mathematics 45, No. 2 (1995) 353-398. DOI: 10.1070/IM1995v045n02ABEH001645, https://doi.org/10.1070/IM1995v045n02ABEH001645
17. V. I. Trofimov, Graphs with projective suborbits, cases of small characteristics, II, Izvestiya Rossiiskoi Akademii Nauk, Seriya Matematicheskaya 58, No. 6 (1994) 137-156; English translation in Izvestiya: Mathematics 45, No. 3 (1995) 559-576. DOI: 10.1070/IM1995v045n03ABEH001672, https://doi.org/10.1070/IM1995v045n03ABEH001672
18. 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
19. Đorđe Mitrović, Gabriel Verret, On transitive permutation groups with exponential graph growth, arXiv:2508.12588 (2025), https://arxiv.org/abs/2508.12588
20. Maruša Lekše, Stabilizers of consistent walks, arXiv:2405.16691 (2024), https://arxiv.org/abs/2405.16691
21. Marco Barbieri, Pablo Spiga, On the number of generators of groups acting arc-transitively on graphs, arXiv:2405.13603 (2024), https://arxiv.org/abs/2405.13603
22. Nick Gill, A note on the Weiss conjecture, Journal of the Australian Mathematical Society 95 (2013) 356-361. DOI: 10.1017/S144678871300030X, https://doi.org/10.1017/S144678871300030X (arXiv:1303.3784)
23. P. J. Cameron, C. E. Praeger, J. Saxl, G. M. Seitz, On the Sims conjecture and distance transitive graphs, Bulletin of the London Mathematical Society 15 (1983) 499-506. DOI: 10.1112/blms/15.5.499, https://doi.org/10.1112/blms/15.5.499
24. A. Gardiner, Arc-transitivity in graphs, Quarterly Journal of Mathematics (Oxford) 24 (1973) 399-407. DOI: 10.1093/qmath/24.1.399, https://doi.org/10.1093/qmath/24.1.399
25. R. Weiss, s-transitive graphs, in: Algebraic Methods in Graph Theory, Colloquia Mathematica Societatis János Bolyai 25, North-Holland, Amsterdam (1978) 827-847. [No DOI exists for this Bolyai conference volume]
26. W. T. Tutte, On the symmetry of cubic graphs, Canadian Journal of Mathematics 11 (1959) 621-624. DOI: 10.4153/CJM-1959-057-2, https://doi.org/10.4153/CJM-1959-057-2
27. Cheryl E. Praeger, Finite quasiprimitive group actions on graphs and designs, in: Groups-Korea '98 (Y. G. Baik, D. L. Johnson, A. C. Kim, eds.), de Gruyter, Berlin (2000) 319-331. DOI: 10.1515/9783110807493-023, https://doi.org/10.1515/9783110807493-023 (source of the 1998 Praeger Conjecture as Problem 7)