Aldous property for full-flag Johnson graphs
Gary Greaves Haoran Zhu · 2026
Read Aldous property for full-flag Johnson graphs by Gary Greaves Haoran Zhu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-10406.txt.
Introduction
Gary Greaves and Haoran Zhu prove an Aldous-type result for full-flag Johnson graphs, concerning where their spectral gap comes from. They show the gap of the full graph equals the gap of its Schreier quotient, which arises from the point-stabiliser equitable partition. That equality is the heart of the matter: the smaller quotient already captures the slowest mixing behaviour of the much larger graph. Their work settles two conjectures of Huang, Huang, and Cioabă about this spectral-gap phenomenon.
Catalog record
| CREATOR | Gary Greaves Haoran Zhu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38659 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.10406
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Aldous property for full-flag Johnson graphs Gary Greaves Haoran Zhu Abstract We show that the full-flag Johnson graph has spectral gap equal to that of its Schreier quotient arising from the point-stabiliser equitable partition. Our results confirm two conjectures posed by Huang, Huang, and Cioabă, which imply an Aldous-type spectral-gap phenomenon for full-flag Johnson graphs. Keywords: Spectral gap, Johnson graph, Schreier graph, symmetric group, Aldous’ conjecture. Mathematics Subject Classification: 05C50, 05C25, 20B30, 15A18, 60K35 1 Introduction The second-largest eigenvalue of a regular graph is widely regarded as a key indicator of its global connectivity and expansion properties [ 3 , 4 , 18 , 28 ] . In particular, relative to the degree, a smaller second-largest eigenvalue typically reflects stronger connectivity, faster mixing of random walks, and better expansion. The notion of the Aldous property arises naturally at the interface of algebra, graph theory, and probability. A Cayley graph \operatorname{Cay}(S_{n},\Sigma) on the symmetric group S_{n} with generating set \Sigma is said to have the Aldous property if its second-largest eigenvalue coincides with that of the Schreier graph \operatorname{Sch}(S_{n},[n],\Sigma) , that is, the graph with vertex set [n]:=\{1,\dots,n\} and an arc from i to j for each \sigma\in\Sigma satisfying \sigma(i)=j . Aldous conjectured [ 1 , Open Problem 14.29] that \operatorname{Cay}(S_{n},\Sigma) has the Aldous property when \Sigma is a set of transpositions. This conjecture stimulated nearly two decades of research, including partial results for random walks on finite groups [ 20 ] , Coxeter graphs [ 8 ] , multipartite graphs [ 12 ] , and certain weighted graphs [ 17 ] , before its full resolution by Caputo, Liggett, and Richthammer [ 10 ] . The spectral theory of Cayley graphs can be distinguished by normality. The Cayley graph \operatorname{Cay}(G,\Sigma) is said to be normal if \Sigma is closed under conjugation in G , that is, if \Sigma is a union of conjugacy classes. Normal Cayley graphs admit a particularly tractable spectral theory: their eigenvalues can be expressed explicitly in terms of the irreducible characters of the underlying group [ 16 , 30 ] . In contrast, the spectral analysis of non-normal Cayley graphs is considerably more intricate. The absence of conjugacy invariance prevents a direct application of character theory, and comparatively few general results are currently available. Variations and generalisations of Aldous’ conjecture continue to attract attention [ 2 , 5 , 11 , 13 , 21 , 23 , 24 , 26 , 27 , 29 ] . Various families of Cayley graphs \operatorname{Cay}(S_{n},\Sigma) have been shown to possess the Aldous property for suitably structured generating sets \Sigma . In the case of normal Cayley graphs, we refer the reader to [ 24 , 29 ] . In the case of non-normal Cayley graphs, the Aldous property has been established when \Sigma consists of reversals [ 13 ] , prefix-reversals [ 11 ] , and certain subsets of cycles [ 27 ] . As we show below (see Section 2.1 ), in this paper, we are concerned with the (non-normal) case where \Sigma consists of (n-2) -reducible permutations. A full flag of [n] is a chain U=(U_{1},\dots,U_{n}) of subsets satisfying |U_{i}|=i and U_{i}\subset U_{i+1} . For integers n and k with 0<k<n , the Johnson graph J(n,k) is the graph whose vertices are the k -subsets of [n] , where two vertices U and V are adjacent whenever |U\cap V|=k-1 . In 2016, Dai [ 14 ] introduced the full-flag Johnson graph {{F\!\!J}}(n,k) , for 0\leq k<n . Its vertex set consists of all full flags of [n] , and two full flags U=(U_{1},\dots,U_{n})\quad\text{and}\quad V=(V_{1},\dots,V_{n}) are adjacent if and only if \bigl|\{\,i\in[n]:U_{i}\neq V_{i}\,\}\bigr|=k . Equivalently, U and V , viewed as collections of subsets of [n] , are adjacent if and only if they have exactly n-k subsets in common; that is, |U\cap V|=n-k . Dai [ 14 ] observed that the permutahedron of order n coincides with {{F\!\!J}}(n,1) , thereby placing {{F\!\!J}}(n,k) as a natural generalisation of permutahedra. In [ 15 ] , Dai calculated all eigenvalues of the quotient graph of {{F\!\!J}}(n,1) with respect to a certain equitable partition, and conjectured that {{F\!\!J}}(n,1) and its quotient graph share the same second-largest eigenvalue. Huang, Huang, and Cioabă [ 24 ] observed that Dai’s conjecture is a special case of Aldous’ conjecture and initiated an analogous study of {{F\!\!J}}(n,2) and implicitly conjectured that {{F\!\!J}}(n,2) has the Aldous property [ 25 , Conjecture 6.9] . Our main theorem resolves this conjecture. Theorem 1.1 . For each n\geq 4 , the full-flag Johnson graph {{F\!\!J}}(n,2) has the Aldous property. The statement of Theorem 1.1 implies that {{F\!\!J}}(n,2) is a Cayley graph on the symmetric group S_{n} , a fact already established by Dai [ 14 ] . However, {{F\!\!J}}(n,2) is a non-normal Cayley graph, and hence character-theoretic methods are not directly applicable for deriving expressions for its eigenvalues [ 27 ] . Our proof of Theorem 1.1 follows an approach suggested by Huang, Huang, and Cioabă, which we outline in Section 2 . To implement this strategy, we establish two conjectures of Huang, Huang, and Cioabă [ 24 , Conjectures 23 and 24] concerning recursive inequalities for the second-largest eigenvalue of quotient matrices arising from the point-stabiliser partition of the vertex set. The proof of these inequalities is primarily inductive and relies on several linear-algebraic arguments, viewed naturally from the perspective of Laplacian operators. The paper is organised as follows. In Section 2 , we present the full-flag Johnson graph {{F\!\!J}}(n,2) as a Cayley graph whose generating set consists of (n-2) -reducible permutations. We then reduce the proof of Theorem 1.1 to establishing certain recursive inequalities (see Theorem 2.4 ). In Section 3 , we prove Theorem 2.4 . 2 Cayley graphs and equitable partitions 2.1 Full-flag Johnson graph as a Cayley graph Let G be a finite group and let \Sigma\subseteq G satisfying 1_{G}\notin\Sigma and g^{-1}\in\Sigma for each g\in\Sigma . The Cayley graph \Gamma=\mathrm{Cay}(G,\Sigma) is the undirected graph whose vertex set is G and two vertices g,h\in G are adjacent whenever h=\sigma g for some \sigma\in\Sigma . The graph \Gamma is clearly |\Sigma| -regular. Furthermore, \Gamma is connected if and only if \Sigma generates G . A permutation \sigma\in S_{n} is called m –reducible if there exists a partition [n]=I_{1}\cup\cdots\cup I_{m} into contiguous intervals with \sigma(I_{j})=I_{j} for all j . Further, we call \sigma maximally m -reducible if m is the largest possible integer such that \sigma is m -reducible. Define \mathcal{R}_{n}(k):=\{\sigma\in S_{n}:\sigma\ \text{is maximally }(n-k)\text{–reducible}\}. Dai [ 14 , Theorem 1] showed that {{F\!\!J}}(n,k)\cong\operatorname{Cay}(S_{n},\,\mathcal{R}_{n}(k)) . The approach we take towards a proof of Theorem 1.1 requires us to consider the subgraph of \operatorname{Cay}\left(S_{n},\mathcal{R}_{n}(2)\right) generated by those (n-2) –reducible permutations that move the symbol 1 , explicitly, \mathcal{R}_{n}^{\prime}(2):=\{(1,2,3),(1,3,2),(1,3),(1,2)(3,4),(1,2)(4,5),\ldots,(1,2)(n-1,n)\}. In fact, in addition to \operatorname{Cay}\left(S_{n},\mathcal{R}_{n}(2)\right) , we will also show that \operatorname{Cay}\left(S_{n},\mathcal{R}^{\prime}_{n}(2)\right) has the Aldous property (see Lemma 2.6 ). 2.2 Schreier graphs and quotient matrices Let \Gamma=(V(\Gamma),E(\Gamma)) be a simple undirected graph on n vertices, and denote its adjacency matrix by A_{\Gamma} . A partition \Pi=\{V_{1},V_{2},\dots,V_{m}\} of the vertex set V(\Gamma) is called an equitable partition if, for every pair i,j\in\{1,\dots,m\} , each vertex in V_{i} has the same number q_{ij} of neighbours in V_{j} . The matrix Q_{\Gamma}(\Pi)=(q_{ij})_{m\times