The Weiss conjecture: valency-only bounds on vertex stabilizers of locally primitive vertex-transitive graphs and its equivalent second-singular-value formulation

The Weiss conjecture (1978) asserts that there exists a function $f:\mathbb{N}\to\mathbb{N}$ such that, whenever a finite group $G$ acts vertex-transitively and locally primitively on a graph $\Gamma$ of valency $k$, the vertex stabilizer satisfies $|G_v|<f(k)$. Nick Gill (2013) proved that this statement, and its semiprimitive strengthening, is equivalent to a spectral expansion property: the second singular value $\lambda_2$ of the adjacency operator of an explicitly constructed bipartite multigraph $\mathcal{G}$, built from the coset geometry of the action, must be bounded by a function of $k$ alone. Despite substantial partial results (bounded-rank composition factors, all O'Nan-Scott local types except AS and PA, local actions containing an abelian regular subgroup), both the group-theoretic conjectures and the spectral reformulation remain open as of a December 2024 survey devoted to this topic, and the spectral formulation has attracted essentially no follow-up work. The problem is to determine the truth of the Weiss conjecture and of its semiprimitive variant, equivalently of the corresponding $\lambda_2$ bound for the associated family of bipartite multigraphs, either by a proof that such a bound exists or by an explicit family of actions of fixed valency with unbounded vertex stabilizers.

Background

A finite graph $\Gamma$ with vertex set $V$ and valency (degree) $k$ is vertex-transitive under a group $G\leq\mathrm{Aut}(\Gamma)$ if $G$ has a single orbit on $V$. The vertex stabilizer $G_v$ is the subgroup of elements fixing a chosen vertex $v$, and the local action at $v$ is the permutation group $G_v^{\Gamma(v)}$ induced by $G_v$ on the set $\Gamma(v)$ of the $k$ neighbours of $v$. The action is locally primitive when this induced group is primitive, meaning transitive and preserving no nontrivial partition of the neighbour set. A transitive permutation group is semiregular if only the identity fixes a point, and semiprimitive if every normal subgroup is transitive or semiregular; every primitive group is semiprimitive, so replacing 'primitive' by 'semiprimitive' in the hypothesis yields a strictly stronger conjecture.

A classical theme of permutation group theory is that strong symmetry at one point forces global structure. The Sims conjecture for primitive permutation groups, proved in the 1980s, states that a primitive group with an orbital (an orbit of a point stabilizer on the remaining points, also called a suborbit) of length $k$ has point stabilizers bounded by a function of $k$; and Tutte's 1947 theorem showed that vertex stabilizers of cubic arc-transitive graphs (graphs of valency 3 whose group is transitive on ordered edges) have order dividing a fixed constant, the first instance of the phenomenon for graphs. In 1978 Richard Weiss conjectured the corresponding local-to-global statement for locally primitive graph actions: there should exist $f:\mathbb{N}\to\mathbb{N}$ with $|G_v|<f(k)$ whenever $G$ acts vertex-transitively and locally primitively on a graph of valency $k$. The conjecture has been confirmed in many special cases (almost simple reductions, bounded-rank composition factors, twisted wreath type, local actions containing an abelian regular subgroup, and all primitive local actions outside the O'Nan-Scott types AS and PA - the O'Nan-Scott classification sorts finite primitive permutation groups into structural types, among which AS denotes almost simple groups and PA product actions built on almost simple groups), but it remains open in general; a parallel conjecture of Praeger asks the same for locally quasiprimitive actions (quasiprimitive means every nontrivial normal subgroup of the group is transitive), and Potočnik, Spiga and Verret proposed the semiprimitive strengthening together with the conjecture that a permutation group is 'graph-restrictive' exactly when it is semiprimitive (a permutation group is graph-restrictive if the vertex stabilizers of all connected vertex-transitive graphs having it as local action are bounded by a constant depending only on that group).

Gill's note supplies an equivalent spectral formulation. By a theorem of Sabidussi, a $G$-vertex-transitive graph is a coset graph: $\Gamma\cong\mathrm{Cos}(G,G_v,S)$, where $S$ is an inverse-invariant union of double cosets (sets $G_vaG_v$) and the vertices are the left cosets of $G_v$. From this one builds a finite regular bipartite multigraph $\mathcal{G}$ whose two parts $X$ and $Y$ are copies of $V$, the number of edges between $x\in X$ and $y\in Y$ being the number of elements $s\in S$ with $s(x)=y$. The biadjacency matrix of $\mathcal{G}$ (rows indexed by $X$, columns by $Y$) defines a linear map $\mathbb{R}^{X}\to\mathbb{R}^{Y}$ whose singular values $\lambda_1\geq\lambda_2\geq\cdots$ (the nonnegative square roots of the eigenvalues of the corresponding $AA^{\mathsf{T}}$) are the standard spectral statistics of a bipartite graph, playing the role that eigenvalues play for ordinary graphs; bounding $\lambda_2$ is the classical route to expansion and to rapid mixing of random walks (a small $\lambda_2$ forces every set of vertices to have proportionally many neighbours outside itself). In this construction $\lambda_1=k|G_v|$, so the degree of $\mathcal{G}$ itself grows with the stabilizer, and Gill's Proposition 6 shows that, unless the graph is tiny ($|V|<2k$), one has $|G_v|<\sqrt{2}\,\lambda_2/k$. His Theorem 1 deduces that, for any family of finite vertex-transitive actions, bounding the stabilizer order by a function of the valency is equivalent to bounding $\lambda_2$ by a function of the valency. The Weiss conjecture is therefore exactly the assertion that the explicit family of bipartite multigraphs arising from locally primitive (or semiprimitive) actions satisfies a one-sided expansion property with a valency-only bound - while standard expander technology, which prescribes bounded degree, does not transfer directly to this family.

Problem Statement

Determine the truth of the Weiss conjecture and of its semiprimitive strengthening. Precisely: does there exist a function $f:\mathbb{N}\to\mathbb{N}$ such that every finite group $G$ acting vertex-transitively and locally primitively on a (connected) graph $\Gamma$ of valency $k$ satisfies $|G_v|<f(k)$; and does the same hold, with some function $f'$, when 'locally primitively' is weakened to 'locally semiprimitively' (every normal subgroup of the local action $G_v^{\Gamma(v)}$ transitive or semiregular)? The two statements are nested - a bound for the semiprimitive class implies one for the locally primitive class, and a counterexample for the locally primitive class refutes the semiprimitive variant.

By Gill's equivalence this is the same question as a spectral one: for the family of bipartite multigraphs $\mathcal{G}=\mathcal{G}(G,\Gamma)$ constructed from such actions (both parts copies of $V(\Gamma)$, the multiplicity of the edge $\{x,y\}$ equal to the number of $s\in S$ with $s(x)=y$, where $\Gamma\cong\mathrm{Cos}(G,G_v,S)$), does there exist a bound on the second singular value $\lambda_2$ of the adjacency operator that depends on the valency $k$ alone?

The dichotomy is: either a valency-only bound exists for the locally primitive class, or for the strictly larger locally semiprimitive class (thereby settling both statements positively); or the conjecture is refuted by an explicit infinite family of finite groups $G_i$ acting vertex-transitively and locally primitively (respectively semiprimitively) on graphs $\Gamma_i$ of some fixed valency $k$ with $|(G_i)_{v_i}|$ unbounded - equivalently, a family of the associated bipartite multigraphs with $\lambda_2$ unbounded at fixed $k$.

References

1. R. M. Weiss, 's-transitive graphs', in Algebraic Methods in Graph Theory, Vol. II (Conf. Szeged, 1978), Colloq. Math. Soc. János Bolyai 25, North-Holland, Amsterdam, 1981, pp. 827-847. Zbl 0475.05040, https://zbmath.org/?q=an%3A0475.05040
2. W. T. Tutte, 'A family of cubical graphs', Proc. Cambridge Philos. Soc. 43 (1947), 459-474. DOI: 10.1017/S0305004100023720, https://doi.org/10.1017/S0305004100023720
3. M. D. E. 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
4. 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
5. 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
6. 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
7. 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
8. 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
9. N. Gill, 'A note on the Weiss conjecture', J. Aust. Math. Soc. 95 (2013), no. 3, 356-361. DOI: 10.1017/S144678871300030X, arXiv:1303.3784, https://doi.org/10.1017/S144678871300030X
10. 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, arXiv:1509.04862, https://doi.org/10.1112/blms/bdv071
11. V. I. Trofimov, 'On the Weiss Conjecture. I', Proc. Steklov Inst. Math. 319 (2022), S281-S290. DOI: 10.1134/S0081543822060244, https://doi.org/10.1134/S0081543822060244
12. M. Giudici, L. Morgan, 'A theory of semiprimitive groups', J. 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
13. 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