The Weiss conjecture: is the order of a vertex stabiliser in a finite locally primitive vertex-transitive graph bounded by the valency alone?

Richard Weiss conjectured in 1978 that there exists a function $f$ of the valency $d$ alone such that every finite connected $G$-vertex-transitive, $G$-locally primitive graph of valency $d$ satisfies $|G_\alpha|\le f(d)$ for each vertex stabiliser $G_\alpha$. Praeger, Pyber, Spiga and Szabó proved in 2012 that such a bound exists with an extra parameter: $|G_\alpha|\le g(r,d)$ whenever the group $G$ has no section isomorphic to $\operatorname{Alt}(r+1)$ (the class $\mathrm{BCP}(r)$ of Babai, Cameron and Pálfy), and asked explicitly whether the dependence on the composition-factor rank $r$ can be removed, which is precisely the original conjecture. The problem is open: the known reductions (Conder–Li–Praeger; Praeger–Spiga–Verret) leave the almost simple and product-action cases as the hard core; Conder, Li and Praeger confirmed the conjecture for all quasiprimitive O'Nan-Scott types of the vertex action except AS and PA, and Trofimov confirmed it for all primitive local actions except groups of AS type and groups of PA type; further partial cases (locally 2-transitive, locally twisted wreath type, local action containing an abelian regular subgroup) and reformulations (spectral, via Burger–Mozes theory, via graph-restrictive local groups) do not remove the rank restriction; and Spiga's 2025 survey of vertex stabilisers presents the conjecture as unresolved.

Background

Let $\Gamma$ be a finite connected graph and let $G\le\operatorname{Aut}(\Gamma)$ act transitively on the vertex set (so $\Gamma$ is $G$-vertex-transitive). The valency $d$ is the number of neighbours of a vertex, and the vertex stabiliser $G_\alpha$ is the subgroup fixing the vertex $\alpha$. By transitivity, the permutation group that $G_\alpha$ induces on the neighbour set $\Gamma(\alpha)$, called the local action, is the same up to permutational isomorphism at every vertex. The graph is $G$-locally primitive when this local action is a primitive permutation group, that is, a transitive group preserving no nontrivial partition of the set it acts on.

The prototypical result is due to Tutte: in a finite symmetric (arc-transitive) graph of valency 3, the order of a vertex stabiliser divides 48. The permutation-group analogue is the Sims conjecture, proved by Cameron, Praeger, Saxl and Seitz using the classification of the finite simple groups: in a primitive permutation group with a nontrivial suborbit of length $m$, the order of a point stabiliser is bounded by a function of $m$. In 1978 Richard Weiss conjectured the corresponding local-to-global statement for graphs: the order of a vertex stabiliser of a locally primitive vertex-transitive graph should be bounded by a function of the valency alone.

The local-primitivity hypothesis cannot simply be dropped: the wreath graphs $C_n[\overline K_{d/2}]$ (lexicographic products of a cycle with an edgeless graph on $d/2$ vertices) are vertex-transitive of fixed even valency with unbounded vertex stabilisers, and Potočnik, Spiga and Verret constructed further tetravalent arc-transitive graphs with unbounded vertex stabilisers; in all such examples the local action is imprimitive. The content of the conjecture is thus that primitive local actions are exactly strong enough to force a global bound.

Several reductions circumscribe the open core. Conder, Li and Praeger showed that the conjecture for finite non-bipartite graphs reduces to the case where the automorphism group contains a locally primitive almost simple subgroup (a group sandwiched between a nonabelian simple group and its automorphism group). A transitive group is quasiprimitive when every nontrivial normal subgroup is transitive, and biquasiprimitive when it has a subgroup of index at most 2 that is quasiprimitive on each of its two orbits; Praeger, Spiga and Verret gave a genuine reduction of the conjecture, for graphs admitting such groups, to the case where the acting group is a nonabelian simple group; their paper also records Praeger's 1998 locally quasiprimitive generalisation of the conjecture, which remains open in the same way.

The source paper, by Praeger, Pyber, Spiga and Szabó, proved the conjecture for the class $\mathrm{BCP}(r)$ of finite groups with no section isomorphic to the alternating group $\operatorname{Alt}(r+1)$, introduced by Babai, Cameron and Pálfy: there exists $g(r,d)$ such that $|G_\alpha|\le g(r,d)$ for every connected $G$-vertex-transitive, $G$-locally primitive graph of valency at most $d$ with $G\in\mathrm{BCP}(r)$. The proof reduces, via the result of Praeger, Spiga and Verret, to nonabelian simple groups and then applies the product-growth theorem of Pyber and Szabó for finite simple groups of Lie type of bounded rank. Note that for simple groups the $\mathrm{BCP}(r)$ condition exactly excludes alternating groups of large degree and simple groups of Lie type of large Lie rank, so the surviving obstruction to removing $r$ is precisely composition factors of unbounded rank.

A modern reformulation frames the problem through local groups: following Verret, a finite transitive permutation group $L$ is called graph-restrictive if $|G_\alpha|$ is bounded by a constant depending only on $L$ for every arc-transitive graph whose local action is $L$; the Weiss conjecture is the assertion that every finite primitive permutation group is graph-restrictive, and Potočnik, Spiga and Verret conjectured the sharper statement that the graph-restrictive groups are exactly the semiprimitive groups, those in which every normal subgroup is transitive or semiregular (the identity is the only element fixing a point).

Problem Statement

Does there exist a function $f:\mathbb{N}\to\mathbb{N}$ such that, for every finite connected graph $\Gamma$ of valency $d$ and every subgroup $G\le\operatorname{Aut}(\Gamma)$ acting transitively on vertices with the stabiliser $G_\alpha$ of a vertex $\alpha$ inducing a primitive permutation group on the neighbourhood $\Gamma(\alpha)$ (that is, $\Gamma$ is $G$-vertex-transitive and $G$-locally primitive), the vertex stabiliser satisfies $|G_\alpha|\le f(d)$ for every vertex $\alpha$? Equivalently, in the formulation of the source paper: can the two-variable bound $|G_\alpha|\le g(r,d)$, proved by Praeger, Pyber, Spiga and Szabó for all groups in the class $\mathrm{BCP}(r)$ (groups with no section isomorphic to $\operatorname{Alt}(r+1)$), be chosen independent of the composition-factor rank parameter $r$? The statement is the 1978 conjecture of Richard Weiss; Praeger's locally quasiprimitive generalisation and Questions 6, 7 and 8 of the source paper (minimal local hypotheses, exponent bounds, kernel bounds) are adjacent open problems, distinct from the statement above.

References

1. C. E. Praeger, L. Pyber, P. Spiga, E. Szabó, Graphs with automorphism groups admitting composition factors of bounded rank, Proc. Amer. Math. Soc. 140 (2012), no. 7, 2307–2318, doi:10.1090/S0002-9939-2011-11100-6, https://doi.org/10.1090/S0002-9939-2011-11100-6
2. R. Weiss, s-transitive graphs, in: Algebraic methods in graph theory, Vol. II (Conf. Szeged 1978), Colloq. Math. Soc. János Bolyai 25, North-Holland, 827–847 (1981), Zbl 0475.05040, https://zbmath.org/0475.05040
3. W. T. Tutte, A family of cubical graphs, Math. Proc. Cambridge Philos. Soc. 43 (1947), 459–474, doi:10.1017/s0305004100023720, https://doi.org/10.1017/s0305004100023720
4. W. T. Tutte, On the symmetry of cubic graphs, Canad. J. Math. 11 (1959), 621–624, doi:10.4153/cjm-1959-057-2, https://doi.org/10.4153/cjm-1959-057-2
5. P. J. Cameron, C. E. Praeger, J. Saxl, G. M. Seitz, On the Sims conjecture and distance transitive graphs, Bull. London Math. Soc. 15 (1983), no. 5, 499–506, doi:10.1112/blms/15.5.499, https://doi.org/10.1112/blms/15.5.499
6. L. Babai, P. J. Cameron, P. P. Pálfy, On the orders of primitive groups with restricted nonabelian composition factors, J. Algebra 79 (1982), no. 1, 161–168, doi:10.1016/0021-8693(82)90323-4, https://doi.org/10.1016/0021-8693(82)90323-4
7. M. D. Conder, C. H. Li, C. E. Praeger, On the Weiss conjecture for finite locally primitive graphs, Proc. Edinburgh Math. Soc. (2) 43 (2000), no. 1, 129–138, doi:10.1017/S0013091500020745, https://doi.org/10.1017/S0013091500020745
8. C. E. Praeger, P. Spiga, G. Verret, Bounding the size of a vertex-stabiliser in a finite vertex-transitive graph, J. Combin. Theory Ser. B 102 (2012), no. 3, 797–819, doi:10.1016/j.jctb.2011.11.004, https://doi.org/10.1016/j.jctb.2011.11.004 (arXiv:1102.1543)
9. L. Pyber, E. Szabó, Growth in finite simple groups of Lie type, J. Amer. Math. Soc. 29 (2016), no. 1, 95–146, doi:10.1090/s0894-0347-2014-00821-3, https://doi.org/10.1090/s0894-0347-2014-00821-3
10. P. Potočnik, P. Spiga, G. Verret, Tetravalent arc-transitive graphs with unbounded vertex-stabilizers, Bull. Aust. Math. Soc. 84 (2011), no. 1, 79–89, doi:10.1017/s0004972710002078, https://doi.org/10.1017/s0004972710002078
11. G. Verret, On the order of arc-stabilizers in arc-transitive graphs, Bull. Aust. Math. Soc. 80 (2009), no. 3, 498–505, doi:10.1017/s0004972709000550, https://doi.org/10.1017/s0004972709000550
12. P. Potočnik, P. Spiga, G. Verret, On graph-restrictive permutation groups, J. Combin. Theory Ser. B 102 (2012), no. 3, 820–831, doi:10.1016/j.jctb.2011.11.006, https://doi.org/10.1016/j.jctb.2011.11.006 (arXiv:1101.5186)
13. P. Potočnik, P. Spiga, G. Verret, On the order of arc-stabilisers in arc-transitive graphs with prescribed local group, Trans. Amer. Math. Soc. 366 (2014), no. 7, 3729–3745, doi:10.1090/s0002-9947-2014-05992-8, https://doi.org/10.1090/s0002-9947-2014-05992-8 (arXiv:1207.5593)
14. P. Spiga, On $G$-locally primitive graphs of locally twisted wreath type and a conjecture of Weiss, J. Combin. Theory Ser. A 118 (2011), no. 8, 2257–2260, doi:10.1016/j.jcta.2011.05.005, https://doi.org/10.1016/j.jcta.2011.05.005
15. P. Spiga, An application of the Local $C(G,T)$ Theorem to a conjecture of Weiss, Bull. Lond. Math. Soc. 48 (2016), no. 1, 12–18, doi:10.1112/blms/bdv071, https://doi.org/10.1112/blms/bdv071 (arXiv:1509.04862)
16. N. Gill, A note on the Weiss conjecture, J. Aust. Math. Soc. 95 (2013), no. 3, 356–361, doi:10.1017/S144678871300030X, https://doi.org/10.1017/S144678871300030X (arXiv:1303.3784)
17. V. I. Trofimov, On the Weiss Conjecture. I, Proc. Steklov Inst. Math. 319 (2022), suppl. 1, S281–S290, doi:10.1134/S0081543822060244, https://doi.org/10.1134/S0081543822060244
18. M. Giudici, L. Morgan, A class of semiprimitive groups that are graph-restrictive, Bull. Lond. Math. Soc. 46 (2014), no. 6, 1226–1236, doi:10.1112/blms/bdu076, https://doi.org/10.1112/blms/bdu076
19. M. Giudici, L. Morgan, On locally semiprimitive graphs and a theorem of Weiss, J. 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)
20. M. Giudici, L. Morgan, A theory of semiprimitive groups, J. 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)
21. L. Morgan, P. Spiga, G. Verret, On the order of Borel subgroups of group amalgams and an application to locally-transitive graphs, J. Algebra 434 (2015), 138–152, doi:10.1016/j.jalgebra.2015.02.029, https://doi.org/10.1016/j.jalgebra.2015.02.029 (arXiv:1406.1370)
22. S. Tornier, Groups acting on trees with prescribed local action, J. Aust. Math. Soc. 115 (2023), no. 2, 240–288, doi:10.1017/S1446788722000143, https://doi.org/10.1017/S1446788722000143 (arXiv:2002.09876)
23. P. Spiga, An overview on vertex stabilizers in vertex-transitive graphs, Boll. Unione Mat. Ital. 18 (2025), no. 1, 327–346, doi:10.1007/s40574-024-00453-4, https://doi.org/10.1007/s40574-024-00453-4
24. M. Barbieri, P. Spiga, On the number of generators of groups acting arc-transitively on graphs, Australas. J. Combin. 90 (2024), part 2, 187–198, arXiv:2405.13603, https://arxiv.org/abs/2405.13603
25. P. Potočnik, M. Toledo, G. Verret, On orders of automorphisms of vertex-transitive graphs, J. Combin. Theory Ser. B 166 (2024), 123–153, doi:10.1016/j.jctb.2024.01.001, https://doi.org/10.1016/j.jctb.2024.01.001 (arXiv:2106.06750)