Finite locally-quasiprimitive graphs: completing the Li–Praeger–Venkatesh–Zhou structure theory and the Weiss-type vertex-stabiliser bound

Let Γ be a finite graph with a vertex-transitive group G of automorphisms such that every vertex stabiliser $G_α$ acts quasiprimitively on the neighbour set $Γ(α)$. Li–Praeger–Venkatesh–Zhou (Discrete Mathematics 246 (2002) 197–218) built a normal-quotient reduction theory for this class — a quasiprimitive and bi-quasiprimitive taxonomy of basic graphs, a multicover/extender correspondence, and partial reconstruction theorems — and closed the paper with six open problems: a detailed O'Nan–Scott-style structural analysis of basic locally-quasiprimitive graphs; a structure theorem for bi-quasiprimitive permutation groups; necessary and sufficient conditions to reconstruct a graph from its basic normal quotients; conditions under which a single quotient determines the graph; inheritance of local quasiprimitivity and basicness by the full automorphism group; and a Weiss-type conjecture that vertex-stabiliser order is bounded by a function of the valency alone. One of these six problems — the structure theorem for bi-quasiprimitive permutation groups — has since been settled by Praeger (2003) and is not part of the task. The remaining components, notably the stabiliser-bound conjecture (which contains the famous 1978 Weiss conjecture for locally-primitive graphs and Praeger's 1998 conjecture as special cases), remain open, with substantial partial progress. The problem posed is to complete this surviving program.

Background

Symmetry hypotheses for finite graphs. For a finite graph Γ and a group $G ≤ Aut(Γ)$, the graph is G-vertex-transitive if G is transitive on the vertex set, and (G,2)-arc-transitive if G is transitive on the 2-arcs, the directed paths of length two (an arc is a directed edge). For a vertex α, the local action at α is the action of the stabiliser $G_α$ on the neighbourhood $Γ(α)$ of vertices adjacent to α. A permutation group is quasiprimitive if each of its nontrivial normal subgroups is transitive; this weakens primitivity, which additionally requires point stabilisers to be maximal. The graph Γ is G-locally-quasiprimitive if G is vertex-transitive and, for every vertex α, the local action of $G_α$ on $Γ(α)$ is quasiprimitive. Since (G,2)-arc-transitivity forces $G_α$ to be primitive on $Γ(α)$, local quasiprimitivity is a genuine weakening of the classical hypotheses, and the family $F$ of finite locally-quasiprimitive graphs — finite graphs admitting at least one such group action — strictly contains all 2-arc-transitive graphs and all locally-primitive vertex-transitive graphs. Cai Heng Li, Cheryl E. Praeger, Akshay Venkatesh and Sanming Zhou (cited as LPVZ below) introduced this family to ask how much of the highly successful theory of 2-arc-transitive graphs survives under only the weaker local hypothesis. The Li–Praeger–Venkatesh–Zhou reduction theory. For $N$ a nontrivial normal subgroup of $G$, the orbits of N form the blocks of a G-invariant partition and the normal quotient $Γ_N$ is the quotient graph on the set of N-orbits, carrying the induced group $G/N$; Γ covers $Γ_N$ if every edge of the quotient lifts to at least one edge at every vertex lying above it (a covering graph in the usual sense when each lift is unique), and LPVZ call Γ a multicover of $Γ_N$ to allow this covering relation without any regularity of the vertex fibres. By their Theorem 1.3, a connected G-locally-quasiprimitive graph either is a complete bipartite double cover $K_2 ⊗ Δ$ of a smaller graph in $F$, or admits a semiregular normal subgroup N with more than two orbits on vertices (semiregular meaning that no nonidentity element of N fixes a vertex), so that $Γ_N$ is a smaller vertex-transitive graph multicovered by Γ; iterating the reduction reaches a quotient that can be reduced no further. The graph is G-basic if no nontrivial normal subgroup of G has more than two orbits on vertices, that is, if it has no nontrivial proper vertex-transitive normal quotient with more than two vertices. LPVZ classified the basic graphs in $F$ into quasiprimitive-type cases, where G is quasiprimitive on vertices, and bipartite cases, where G is bi-quasiprimitive (transitive but not quasiprimitive, with every nontrivial normal subgroup having at most two orbits) and Γ is bipartite with an index-two subgroup of G preserving the two bipartition halves. To describe how a general member of $F$ covers its basic quotients, LPVZ introduced G-extenders, auxiliary data defined from the subgroup lattice of G relative to an edge stabiliser (their Construction 4.2), and proved (Theorem 4.5) that the graphs covering a given basic quotient correspond to G-admissible multicovers of systems of simple covers of extenders. For reconstruction in the opposite direction, their Theorem 5.7 and Lemma 5.5 show that Γ is determined by two normal quotients $Γ_{N_1}$ and $Γ_{N_2}$ whenever $N = N_1N_2$ is semiregular with more than two orbits and a centraliser condition holds, namely triviality of the centraliser of the induced group $G/M$ in $Aut(Γ_M)$ for an auxiliary normal subgroup M supplied by the lemma. O'Nan–Scott background. The analysis of basic graphs proceeds through the structure of the acting permutation group. Quasiprimitive groups admit an O'Nan–Scott-type classification into eight types, due to Praeger (1993) — HA (holomorph of an abelian normal subgroup), HS and HC (holomorph of a simple, respectively compound, normal subgroup), AS (almost simple), SD and CD (simple, respectively compound, diagonal action), PA (product action), and TW (twisted wreath product) — which is the backbone of the classification theory of 2-arc-transitive graphs. The bipartite basic case of the locally-quasiprimitive theory instead requires bi-quasiprimitive groups, for which no such classification existed when LPVZ wrote; obtaining one was their Problem 6.2. Stabiliser bounds. In 1978 Weiss conjectured that the order of a vertex stabiliser in a connected, G-vertex-transitive, G-locally-primitive graph of valency k is bounded by a function of k alone — a graph-theoretic analogue of the Sims conjecture for primitive permutation groups (which asserts that the order of a point stabiliser in a primitive permutation group is bounded by a function of the degree), proved by Cameron–Praeger–Saxl–Seitz (1983) using the classification of finite simple groups. Praeger (Problem 7 of her Groups–Korea '98 survey, published 2000) posed the same conjecture with locally-primitive weakened to locally-quasiprimitive, and LPVZ restated it for the family $F$ as their Conjecture 6.7. Later work weakened the hypothesis further, to locally-semiprimitive graphs (each normal subgroup of $G_α$ transitive or semiregular on $Γ(α)$), and connected the conjectures to the theory of graph-restrictive permutation groups (a transitive permutation group is graph-restrictive if the orders of the vertex stabilisers in the connected vertex-transitive graphs on which it acts transitively are bounded by a constant depending only on the group); all of these conjectures remain open. Status of the six components. The bi-quasiprimitive O'Nan–Scott theorem (Problem 6.2) was established by Praeger (2003). The remaining components — the detailed analysis of basic graphs (Problem 6.1), reconstruction from one or several normal quotients (Problems 6.3 and 6.4), inheritance by the full automorphism group (Problems 6.5 and 6.6), and the Weiss-type stabiliser bound (Conjecture 6.7) — remain open.

Problem Statement

This problem asks to complete the structure theory of the family $F$ of finite locally-quasiprimitive graphs, as posed in the closing section of Li–Praeger–Venkatesh–Zhou (2002), after removal of the one component already resolved. Throughout: Γ is a finite connected graph; $G ≤ Aut(Γ)$ is vertex-transitive and G-locally-quasiprimitive, meaning that for every vertex α the stabiliser $G_α$ acts quasiprimitively on the neighbourhood $Γ(α)$; the valency k is the common size of a neighbourhood; for $N$ a normal subgroup of G, the normal quotient $Γ_N$ is the quotient graph on the set of N-orbits; Γ is G-basic if no nontrivial normal subgroup of G has more than two orbits on vertices; G is bi-quasiprimitive on Γ if G is transitive but not quasiprimitive and every nontrivial normal subgroup of G has at most two orbits. The surviving components are the following. (1) Basic-graph analysis (LPVZ Problem 6.1). Give a detailed structural analysis of the pairs (Γ, G) with Γ in $F$ and Γ G-basic, organised by the O'Nan–Scott type of G — the quasiprimitive types HA, HS, HC, AS, SD, CD, PA, TW of Praeger (1993) and the bi-quasiprimitive types of Praeger (2003) — analogous to the type-by-type analysis available for 2-arc-transitive graphs: for each type, determine the possible local actions, the structure of vertex stabilisers, and the structural constraints that distinguish the locally-quasiprimitive case. (2) Reconstruction from several quotients (LPVZ Problem 6.3). LPVZ's Theorem 5.7 reconstructs Γ from two normal quotients $Γ_{N_1}$ and $Γ_{N_2}$ under sufficient conditions: $N = N_1N_2$ semiregular with more than two orbits, and triviality of the centraliser of the induced group $G/M$ in $Aut(Γ_M)$ for the auxiliary normal subgroup M supplied by their Lemma 5.5. Determine necessary and sufficient conditions: identify the minimal extra data that, together with a family of basic normal quotients $Γ_{N_i}$ whose kernels satisfy $\bigcap_i N_i = 1$, determines Γ and its G-action up to G-admissible multicover. (3) Reconstruction from a single quotient (LPVZ Problem 6.4). Characterise when one basic normal quotient, together with local structure such as the extender or covering data above it, determines Γ; in particular, decide when the covering of a basic quotient by a member of $F$ is unique up to isomorphism. (4) Inheritance by overgroups (LPVZ Problems 6.5 and 6.6). Characterise the pairs (Γ, G) in $F$ such that the full automorphism group $Aut(Γ)$, or a given overgroup, is itself locally quasiprimitive on Γ, and respectively such that Γ remains basic for $Aut(Γ)$. Both properties fail in general — witness the Devillers–Giudici–Li–Praeger infinite families, where bi-quasiprimitivity of the acting group is lost in passing to the full automorphism group, and the Jin–Jin–Li–Li circulant example, where local quasiprimitivity itself is lost — so a characterisation must explain exactly which obstructions occur and when they are absent. (5) Weiss-type stabiliser bound (LPVZ Conjecture 6.7). Prove or disprove: there exists a function $f$ on the natural numbers such that for every finite connected graph Γ in $F$ of valency k, the order of a vertex stabiliser in the full automorphism group satisfies $|Aut(Γ)_α| ≤ f(k)$. The formulation standard in the later literature, and equivalent to this one whenever local quasiprimitivity passes from G to $Aut(Γ)$ (exactly question (4)), is: there exists $f$ such that $|G_α| ≤ f(k)$ for every finite pair (Γ, G) with Γ connected, G vertex-transitive and G-locally-quasiprimitive of valency k (Weiss 1978 for locally-primitive graphs; Praeger 1998, Groups–Korea Problem 7, for locally-quasiprimitive pairs). Either of the two equivalent formulations of item (5) may be resolved. Item (5) — a resolution of the Weiss and Praeger conjectures, in either the positive or the negative direction — is the central open question. LPVZ Problem 6.2, the O'Nan–Scott theorem for bi-quasiprimitive groups, is already resolved (Praeger 2003) and is not part of the open task.

References

1. Cai Heng Li, Cheryl E. Praeger, Akshay Venkatesh, Sanming Zhou, 'Finite locally-quasiprimitive graphs', Discrete Mathematics 246(1-3) (2002) 197–218. DOI: 10.1016/S0012-365X(01)00258-8; https://doi.org/10.1016/S0012-365X(01)00258-8; zbMATH: Zbl 0996.05068 (source of Problems 6.1–6.6 and Conjecture 6.7)
2. Richard Weiss, 's-transitive graphs', in: Algebraic Methods in Graph Theory, Vol. II (Conf. Szeged, 1978), Colloquia Mathematica Societatis János Bolyai 25, North-Holland, Amsterdam, 1981, pp. 827–847. zbMATH: Zbl 0475.05040; https://zbmath.org/?q=an%3A0475.05040 (the 1978 conjecture for locally-primitive graphs; the conference was held in 1978, the volume published in 1981)
3. Peter J. Cameron, Cheryl E. Praeger, Jan Saxl, Gary M. Seitz, 'On the Sims conjecture and distance transitive graphs', Bulletin of the London Mathematical Society 15(5) (1983) 499–504. DOI: 10.1112/blms/15.5.499; https://doi.org/10.1112/blms/15.5.499
4. Cheryl E. Praeger, 'An O'Nan–Scott theorem for finite quasiprimitive permutation groups and an application to 2-arc transitive graphs', Journal of the London Mathematical Society (2) 47(2) (1993) 227–239. DOI: 10.1112/jlms/s2-47.2.227; https://doi.org/10.1112/jlms/s2-47.2.227
5. Cheryl E. Praeger, 'Finite quasiprimitive group actions on graphs and designs', in: Y. G. Baik, D. L. Johnson, A. C. Kim (eds.), Groups – Korea '98 (Pusan, 1998), Walter de Gruyter, Berlin, 2000, pp. 319–331. ISBN 3-11-016588-0; zbMATH: Zbl 0952.20003 (Zbl 1421046); https://zbmath.org/?q=an%3A0952.20003 (Problem 7 states the locally-quasiprimitive stabiliser-bound conjecture)
6. Cheryl E. Praeger, Cai Heng Li, Alice C. Niemeyer, 'Finite transitive permutation groups and finite vertex-transitive graphs', in: G. Hahn, G. Sabidussi (eds.), Graph Symmetry: Algebraic Methods and Applications (NATO Advanced Study Institute, Montréal, 1996), NATO ASI Series C 497, Kluwer, Dordrecht, 1997, pp. 277–318. ISBN 0-7923-4668-8; zbMATH: Zbl 0885.05072; https://zbmath.org/?q=an%3A0885.05072 (survey of the normal-quotient method for vertex-transitive graphs; a different work from the Groups–Korea '98 survey above, sometimes confused with it)
7. 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(1) (2000) 129–138. DOI: 10.1017/S0013091500020745; https://doi.org/10.1017/S0013091500020745
8. Cheryl E. Praeger, 'Finite transitive permutation groups and bipartite vertex-transitive graphs', Illinois Journal of Mathematics 47(1-2) (2003) 461–475. DOI: 10.1215/ijm/1258488166; https://doi.org/10.1215/ijm/1258488166 (resolves LPVZ Problem 6.2: the bi-quasiprimitive O'Nan–Scott theorem)
9. Michael Giudici, Cai Heng Li, Cheryl E. Praeger, 'Analysing finite locally s-arc transitive graphs', Transactions of the American Mathematical Society 356(1) (2004) 291–317. DOI: 10.1090/S0002-9947-03-03361-0; https://doi.org/10.1090/S0002-9947-03-03361-0
10. Sanming Zhou, 'A local analysis of imprimitive symmetric graphs', Journal of Algebraic Combinatorics 22(4) (2005) 435–449. DOI: 10.1007/S10801-005-4627-Z; https://doi.org/10.1007/S10801-005-4627-Z
11. Michael Giudici, Jing Xu, 'All vertex-transitive locally-quasiprimitive graphs have a semiregular automorphism', Journal of Algebraic Combinatorics 25(2) (2006) 217–232. DOI: 10.1007/S10801-006-0032-5; https://doi.org/10.1007/S10801-006-0032-5
12. Robert W. Baddeley, Cheryl E. Praeger, Csaba Schneider, 'Quasiprimitive groups and blow-up decompositions', Journal of Algebra 311(1) (2007) 337–351. DOI: 10.1016/j.jalgebra.2006.11.006; https://doi.org/10.1016/j.jalgebra.2006.11.006 (preprint: arXiv:math/0409449, https://arxiv.org/abs/math/0409449)
13. Alice Devillers, Michael Giudici, Cai Heng Li, Cheryl E. Praeger, 'An infinite family of biquasiprimitive 2-arc transitive cubic graphs', Journal of Algebraic Combinatorics 35(2) (2011) 173–192. DOI: 10.1007/s10801-011-0299-z; https://arxiv.org/abs/1103.5524
14. Pablo Spiga, 'On G-locally primitive graphs of locally Twisted Wreath type and a conjecture of Weiss', Journal of Combinatorial Theory, Series A 118(8) (2011) 2257–2260. DOI: 10.1016/j.jcta.2011.05.005; https://doi.org/10.1016/j.jcta.2011.05.005
15. 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(3) (2012) 797–819. DOI: 10.1016/j.jctb.2011.11.004; https://arxiv.org/abs/1102.1543
16. Primož Potočnik, Pablo Spiga, Gabriel Verret, 'On graph-restrictive permutation groups', Journal of Combinatorial Theory, Series B 102(4) (2012) 820–831. DOI: 10.1016/j.jctb.2011.11.006; https://doi.org/10.1016/j.jctb.2011.11.006
17. Cheryl 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(7) (2012) 2307–2318. DOI: 10.1090/S0002-9939-2011-11100-6; https://doi.org/10.1090/S0002-9939-2011-11100-6
18. Shujiao Song, Cai Heng Li, Dianjun Wang, 'Finite locally-quasiprimitive graphs', Algebra Colloquium 21(4) (2014) 627–634. DOI: 10.1142/S1005386714000571; https://doi.org/10.1142/S1005386714000571
19. 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
20. 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
21. Pablo Spiga, 'An application of the local C(G,T) theorem to a conjecture of Weiss', Bulletin of the London Mathematical Society 48(1) (2016) 12–18. DOI: 10.1112/blms/bdv071; https://doi.org/10.1112/blms/bdv071
22. 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
23. Jin-Xin Zhou, 'On automorphism groups of bi-quasiprimitive 2-arc-transitive graphs', Journal of Algebra 620 (2023) 344–362. DOI: 10.1016/j.jalgebra.2022.12.030; https://doi.org/10.1016/j.jalgebra.2022.12.030
24. John van Bon, 'On the structure of vertex stabilizers of arc-transitive locally quasiprimitive graphs', Journal of Algebraic Combinatorics 60(2) (2024) 389–405. DOI: 10.1007/s10801-024-01333-y; https://doi.org/10.1007/s10801-024-01333-y
25. Pablo Spiga, 'An overview on vertex stabilizers in vertex-transitive graphs', Bollettino dell'Unione Matematica Italiana 18(1) (2025) 327–346. DOI: 10.1007/s40574-024-00453-4; https://doi.org/10.1007/s40574-024-00453-4
26. Lei Chen, Cheryl Praeger, 'Quasiprimitive and bi-quasiprimitive highly-arc-transitive digraphs and finite simple groups', preprint (2025). arXiv:2512.17244; https://arxiv.org/abs/2512.17244
27. Wei Jin, Yu Xiang Jin, Cai Xia Li, Ping Shan Li, 'A classification of locally-quasiprimitive circulant digraphs', preprint (2026). arXiv:2607.18783; https://arxiv.org/abs/2607.18783