On the spectra of prefix-reversal graphs

Charles Buehrle; Sa\'ul A. Blanco

REVIEW 1 major objections 4 minor 19 references

On the spectra of prefix-reversal graphs

T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For every $m>2$, the undirected prefix-reversal graph $\mathbb{P}_m(n)$ is claimed to contain every even integer in $[0,2n]$ (with one possible exception unless $4\mid m$) in its spectrum, and the directed graph $P(m,n)$ every integer in…

desk verdict Main results look correct; Theorem 4.1 has a fixable mislabeling, and the reader's directed-case counterexample is wrong. read the letter →

arxiv 2506.08345 v1 pith:7CYUVT3X submitted 2025-06-10 math.CO cs.DM

Saúl A. Blanco , Charles Buehrle This is my paper

classification math.COcs.DM MSC 05C5005C2515B05

keywords prefix-reversalgraphsgraphspectraintegereigenvaluescirculantmatricesCayleyspectralgapwreathproductpancake

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims to prove that the prefix-reversal graphs built from colored permutations $C_m\wr S_n$ have long arithmetic progressions of integer eigenvalues: every even integer from $0$ to $2n$ (with one exception, or none when $4\mid m$) appears in the undirected graph $\mathbb{P}_m(n)$, and every integer from $0$ to $n$ (with one exception) appears in the directed graph $P(m,n)$. These graphs generalize the pancake graph ($m=1$) and burnt pancake graph ($m=2$), so the result would extend known spectral facts about sorting networks to all color counts. Such complete eigenvalue sweeps are rare for Cayley graphs, and they would force the spectral gap to be at most $2$ in the undirected case and at most $1$ in the directed case. A small spectral gap is the kind of quantitative control that drives mixing and expansion estimates.

What carries the argument

The load-bearing object is the quotient matrix of the Cayley graph under the regular partition given by the positions of the colored permutation. For the undirected graph this is $M^\pm(m,n)=\sum_{i=1}^n(P(r_i^+)+P(r_i^-))$, written as an $n\times n$ block matrix whose blocks are $m\times m$ circulant matrices $C^\pm(m)$ together with a diagonal term $2(j-1)I_m$; the directed version uses $M^+(m,n)$ with blocks $C^+(m)$ and diagonal $(j-1)I_m$. Because the partition is regular, any eigenvector of the quotient matrix lifts to an eigenvector of the full adjacency matrix, so the proof reduces to exhibiting piecewise-constant block vectors for each claimed integer eigenvalue. For $m\equiv0\pmod4$, the additional determinant argument exploits the fact that $C^\pm(m)$ is singular (its eigenvalues are $2\cos(2\pi\ell/m)$) together with a block-determinant formula to show even the omitted value is an eigenvalue.

What would settle it

Compute $M^\pm(3,3)(-2,1,1)^{\mathsf T}$ and compare with $2(-2,1,1)^{\mathsf T}$: the result is $(0,0,2)^{\mathsf T}$ rather than $2(-2,1,1)^{\mathsf T}$, and the determinant $\det M^+(3,3)$ is nonzero because it equals $\det(2C^+-{C^+}^3)$ for a 3-cycle matrix $C^+$; either calculation alone settles that the written eigenvector certificates fail in this small case.

Watch

Extended reading notes

Core claim

The central claim is that for every $m>2$ the adjacency spectrum of $\mathbb{P}_m(n)$ contains $0,2,4,\dots,2n$ except possibly $2\lfloor n/2\rfloor$, and contains the missing value as well when $4\mid m$; the adjacency spectrum of the directed graph $P(m,n)$ contains $0,1,\dots,n$ except possibly $\lfloor n/2\rfloor$. The proof routes these eigenvalues through a quotient matrix whose blocks are circulant matrices, exhibits explicit block-constant eigenvectors for the quotient, and, in the $4\mid m$ case, uses the singularity of the circulant block $C^\pm(m)$ to force vanishing of the full characteristic polynomial at even integers. If correct, the claims give the first eigenvalue-containment results of this kind for prefix-reversal graphs with more than two colors and imply the stated small spectral gaps.

Load-bearing premise

The proof depends on the unverified claim that the piecewise-constant vectors displayed in the proofs of Theorems 4.1 and 5.1 are eigenvectors of the quotient matrices; a direct check for $m=n=3$ shows the displayed vector for the eigenvalue $2$ of $M^\pm(3,3)$ is not an eigenvector, so the stated eigenvalue list is not yet established by the written verification.

Editorial extensions

If this is right

If Theorem 4.1 holds, $\mathbb{P}_m(n)$ has spectral gap at most $2$, because $2(n-1)$ is an eigenvalue and the graph is $2n$-regular.
If Theorem 5.1 holds, $P(m,n)$ has spectral gap at most $1$, because $n-1$ is an eigenvalue and the graph is $n$-regular.
When $4\mid m$, the undirected spectrum contains all even integers up to $2n$, including the value $2\lfloor n/2\rfloor$ that otherwise lies in the gap.
The eigenvalue containment transfers from the smaller quotient matrix to the full $mn\times mn$ adjacency matrix, so the certificates live in dimension $n$ rather than $mn$.
Combined with the Cheeger inequality, the undirected spectral gap bound gives an explicit upper bound on the edge-expansion ratio that is independent of the number of colors $m$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The explicit verification in the proof is the only certificate for most listed eigenvalues, so a numerical or symbolic check of all small $(m,n)$ pairs is the natural next step; if the displayed vectors fail, the theorem may still be true but needs either corrected vectors or a determinant argument in the spirit of the $4\mid m$ case.
If the spectrum claim survives in the $m\equiv0\pmod4$ case, the block-circulant determinant structure could also yield exact multiplicities, which the paper leaves open.
The singularity of $C^\pm(m)$ appearing exactly when $4\mid m$ suggests a transferable mechanism: whenever a block circulant in such a quotient becomes singular, the quotient spectrum gains entire families of eigenvalues, so analogues may exist for other Cayley graphs with circulant-block adjacency matrices.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the paper is better than the reader's report suggests. I re-checked the main counterexample: for m=n=3, the directed-case vector for λ=0 is an eigenvector of M+(3,3) as defined in the paper, and det M+ is indeed 0 (the relevant determinant is det(2C−C²−C³), which vanishes for the 3-cycle). So Theorem 5.1's proof is fine on that point. The real defect is in Theorem 4.1: for n odd, the final eigenvector family is mislabeled. The displayed vector with claimed eigenvalue 2(ℓ+1−i) actually has eigenvalue 2(ℓ−i), and the index should run 1≤i≤ℓ, not 1≤i≤ℓ+1. After relabeling, these vectors cover exactly the even integers in [0,2n] except 2⌊n/2⌋, which is what the theorem needs. I checked n=3 explicitly: the 'eigenvalue 2' vector gives eigenvalue 0, which is in the required set. This is a localized error in the proof, not a blow to the main claim. What is new: for m>2, the spectral containment statements are new and extend the known m=1,2 results (Dalfó-Fiol, and the authors' own earlier paper). The method is borrowed, but the explicit eigenvectors are concrete and easy to verify. The paper is honest about what is proven and what is conjectural. Soft spots: (1) the mislabeling in Theorem 4.1 must be corrected; as written it is wrong and will mislead. (2) The m≡0 mod4 determinant argument in Section 4 is under-justified. The claim that for λ=2i there is 'one row and one column where each nonzero block is C±(m)' is not demonstrated, and the factorization det = det(C±) det(M) is asserted rather than proven. This part needs a real proof or a clearer determinant computation. (3) The explicit verification is long; a table would help. Bottom line: the central results appear true, the errors are fixable, and the paper is honest progress in a specialized area. This deserves a serious referee, not a desk reject. I would recommend sending it to review, with instructions to check the n odd families and the m≡0 mod4 argument.

Referee Report

1 major / 4 minor

Summary. The paper studies prefix-reversal graphs on the wreath product C_m ≀ S_n for m > 2, considering both the undirected graph P_m(n) generated by flips and flops and the directed graph P(m,n) generated by flips only. The main theorems assert that the undirected spectrum contains every even integer in [0,2n] except possibly 2⌊n/2⌋, with the missing value also present when 4 | m, and that the directed spectrum contains every integer in [0,n] except ⌊n/2⌋. The proofs work with quotient matrices M_±(m,n) and M_+(m,n) obtained via regular partitions, construct explicit eigenvectors for these quotient matrices, and invoke Godsil's theorem to lift the eigenvalues to the full Cayley graphs; the m ≡ 0 (mod 4) case is handled by a block-determinant argument. The paper also derives consequences for the spectral gap and offers several conjectures.

Significance. If the main theorems are correct, they give a sharp spectral-containment statement for a natural family of Cayley graphs and imply that the undirected prefix-reversal graph has spectral gap at most 2 and the directed one has spectral gap at most 1 (for n ≥ 3). The approach is an explicit, parameter-free eigenvector construction combined with the regular-partition method of Godsil and Dalfó–Fiol, which is a strength: the quotient matrices are written down concretely and the eigenvectors can be checked directly. The paper also provides a plausibility argument for the previously open spectral-gap question in the m > 2 regime. However, the manuscript contains a concrete error in the eigenvalue labeling of one eigenvector family in Theorem 4.1, and this currently prevents the proof from being accepted as written.

major comments (1)

[Section 4, proof of Theorem 4.1 (final family for odd n)] The final displayed eigenvector family for odd n = 2ℓ+1 is mislabeled. The vector (0 over m(ℓ−i) entries, −2i over m entries, 1 over 2mi entries, 0 over m(ℓ−i) entries) is an eigenvector of M_±(m,n) with eigenvalue 2(ℓ−i) for 1 ≤ i ≤ ℓ, not with eigenvalue 2(ℓ+1−i) as stated. For i = ℓ+1 the expression is undefined because ℓ−i is negative. Concretely, when m = n = 3 (ℓ = 1, i = 1), the manuscript would predict eigenvalue 2 for v = (−2,1,1), but direct computation gives M_±(3,3)v = 0. The fix is to change the label to 2(ℓ−i) and the range to 1 ≤ i ≤ ℓ; with this correction the family supplies exactly the low even eigenvalues and Theorem 4.1's conclusion follows from the other families.

minor comments (4)

[Section 6.2] The statement that 'Theorem 5.1 shows that sp(P(m,n)) ≤ 1' is only an immediate consequence for n ≥ 3. For n = 2, the guaranteed set [0,2] \ {1} does not contain n−1 = 1, so the claimed implication does not cover n = 2 and should be qualified.
[Lemma 2.1] The formula for the eigenvalues of a circulant matrix uses the symbol i both for the summation index and for the imaginary unit; please disambiguate the notation (for example, use j for the index).
[Section 3, Theorem 3.1 and the surrounding example] The displayed block matrices are very hard to read because the block boundaries are not clearly marked. Adding explicit block separators or using a different typesetting for the m × m blocks would improve verifiability.
[Section 4, verification of the 2(n−i) family] The line 'the entry in M_±(m,n)v_λ in position j is −−−−−−→−2(n−i)^⊤_m' appears to have a typo in the vector notation; the intended meaning is a scalar multiple of the all-ones vector of length m. Please proofread the vector expressions throughout the verification.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the spectral claims are derived from explicit eigenvectors of the quotient matrices, with only external, parameter-free lifting results used.

full rationale

The derivation chain is self-contained for the new results. Theorem 4.1 and Theorem 5.1 are proved by direct constructions of eigenvalue–eigenvector pairs for the quotient matrices M±(m,n) and M+(m,n), obtained from the explicit block forms in Theorem 3.1. The lifting from quotient-matrix eigenvalues to eigenvalues of the full adjacency matrix uses Proposition 2.3, attributed to Dalfó–Fiol and Godsil, which is an external, parameter-free theorem with stated assumptions. The only author self-citations ([2] in §1.1 and §6.2) are contextual statements about the previously known m=2 burnt pancake case and a conjecture about the spectral gap of P(2,n); they are not used to justify the m>2 eigenvalues. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors' own prior work. Possible typographical discrepancies in the displayed eigenvector ranges, such as in the odd-n case of Theorem 4.1, are correctness concerns about the verification rather than circularity; they do not make the claims true by construction. The result is therefore not circular.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No fitted parameters or invented entities are introduced. The derivation relies on standard tools (circulant eigenvalues, block determinant theorem, regular partition lifting) and on the block-circulant structure of the prefix-reversal permutation matrices. The flaw is not in the axioms but in the claimed verification step that supposedly produces explicit eigenvectors.

assumptions (4)

standard math Circulant matrices are diagonalizable by the discrete Fourier basis with eigenvalues given in Lemma 2.1.
Used throughout to derive eigenvalues of C+(m) and C±(m), especially in Lemma 3.2.
standard math Silvester's block determinant theorem: the determinant of a block matrix with commuting square blocks equals the determinant of the block determinant.
Invoked in the m≡0 mod 4 case of Theorem 4.1 to factor the characteristic polynomial.
standard math Godsil's regular partition theorem: eigenvalues of the quotient matrix are eigenvalues of the full adjacency matrix.
The lifting from M±(m,n) and M+(m,n) to the full Cayley graph spectra relies on Proposition 2.3, which is quoted from Dalfo-Fiol and Godsil.
domain assumption The sum of permutation matrices corresponding to prefix reversals equals the block matrices C±(m,n)+D(m,n) and C+(m,n)+ 1/2 D(m,n) as claimed in Theorem 3.1.
This structural decomposition is specific to the prefix-reversal generators and is proven in Section 3; the proof of Theorems 4.1 and 5.1 depends on it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the spectra of prefix-reversal graphs." pith.science (2026). https://pith.science/paper/7CYUVT3X

@misc{pith2026250608345,
  author       = {Pith},
  title        = {Pith review of: On the spectra of prefix-reversal graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7CYUVT3X}},
  note         = {Machine review of arXiv:2506.08345}
}

abstract

In this paper, we study spectral properties of prefix-reversal graphs. These graphs are obtained by connecting two elements of $C_m\wr S_n$ via prefix reversals. If $m=1,2$, the corresponding prefix-reversal graphs are the classic pancake and burnt pancake graphs. If $m>2$, then one can consider the directed and undirected versions of these graphs. We prove that the spectrum of the undirected prefix-reversal graph $\mathbb{P}_m(n)$ contains all even integers in the interval $[0,2n]\setminus\{2\lfloor n/2\rfloor\}$ and if $m\equiv0\pmod4$, we then show that the spectrum contains all even integers in $[0,2n]$. In the directed case, we show that the spectrum of the directed prefix-reversal graph $P(m,n)$ contains all integers in the interval $[0,n]\setminus\{\lfloor n/2\rfloor\}$. As a consequence, we show that in either case, the prefix-reversal graphs have a small spectral gap.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

A., and Buehrle, C

Blanco, S. A., and Buehrle, C. Lengths of cycles in generalized pancake graphs. Discrete Mathematics 346, 12 (2023), 113624

work page 2023
[2]

A., and Buehrle, C

Blanco, S. A., and Buehrle, C. Some integer values in the spectra of burnt pancake graphs.Linear Algebra Appl. 703(2024), 163–172

work page 2024
[3]

A., Buehrle, C., and Patidar, A

Blanco, S. A., Buehrle, C., and Patidar, A. Cycles in the burnt pancake graph. Discrete Appl. Math. 271(2019), 1–14

work page 2019
[4]

A., Buehrle, C., and Patidar, A

Blanco, S. A., Buehrle, C., and Patidar, A. Onthenumberofpancakestacks requiring four flips to be sorted. Discrete Mathematics & Theoretical Computer Science Vol. 21 no. 2, Permutation Patterns 2018(Nov. 2019)

work page 2018
[5]

Pancake flipping is hard.J

Bulteau, L., Fertin, G., and Rusu, I. Pancake flipping is hard.J. Comput. System Sci. 81, 8 (2015), 1556–1574

work page 2015
[6]

Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap.Electronic Journal of Combinatorics 16(04 2009)

Cesi, F. Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap.Electronic Journal of Combinatorics 16(04 2009)

work page 2009
[7]

The spectral gap of graphs arising from substring reversals

Chung, F., and Tobin, J. The spectral gap of graphs arising from substring reversals. Electron. J. Combin. 24(07 2017), 1–18. 17

work page 2017
[8]

Spectra and eigenspaces from regular partitions of cayley (di)graphs of permutation groups.Linear Algebra and its Applications 597 (2020), 94–112

Dalfó, C., and Fiol, M. Spectra and eigenspaces from regular partitions of cayley (di)graphs of permutation groups.Linear Algebra and its Applications 597 (2020), 94–112

work page 2020

Show all 19 references

[9]

H., and Papadimitriou, C

Gates, W. H., and Papadimitriou, C. H. Bounds for sorting by prefix reversal. Discrete Math. 27, 1 (1979), 47–57

1979
[10]

Algebraic Combinatorics, 1st ed

Godsil, C. Algebraic Combinatorics, 1st ed. Routledge, 1993

1993
[11]

Expander graphs and their appli- cations

Hoory, S., Linial, N., and Wigderson, A. Expander graphs and their appli- cations. Bull. Amer. Math. Soc. 43, 04 (Aug. 2006), 439–562

2006
[12]

On the embedding of cycles in pancake graphs

Kanevsky, A., and Feng, C. On the embedding of cycles in pancake graphs. Parallel Computing 21, 6 (1995), 923 – 936

1995
[13]

J., Kramer, E., Conw ay, J

Kleitman, D. J., Kramer, E., Conw ay, J. H., Bell, S., and Dweighter, H. Problems and Solutions: Elementary Problems: E2564-E2569. Amer. Math. Monthly 82, 10 (1975), 1009–1010

1975
[14]

32, 5 (2016), 1965– 1978

Konstantinov a, E., and Medvedev, A.Independent even cycles in the pancake graph and greedy prefix-reversal Gray codes.Graphs Combin. 32, 5 (2016), 1965– 1978

2016
[15]

Kra, I., and Simanca, S. R. On circulant matrices.Notices Amer. Math. Soc. 59, 3 (2012), 368–377

2012
[16]

Sil vester, J. R. Determinants of Block Matrices.Mathematical Gazette 84, 501 (2000), 460–467

2000
[17]

Permutation statistics of indexed permutations

Steingrímsson, E. Permutation statistics of indexed permutations. European Journal of Combinatorics 15, 2 (1994), 187–205

1994
[18]

Eigenvalues of circulant matrices

V arga, R. Eigenvalues of circulant matrices. Pacific Journal of Mathematics 4 (03 1954)

1954
[19]

Cayley graphs of finite groups.Journal of Algebra 118, 2 (1988), 447–454

Zieschang, P.-H. Cayley graphs of finite groups.Journal of Algebra 118, 2 (1988), 447–454. 18

1988

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

A., and Buehrle, C

Blanco, S. A., and Buehrle, C. Lengths of cycles in generalized pancake graphs. Discrete Mathematics 346, 12 (2023), 113624

work page 2023

[2] [2]

A., and Buehrle, C

Blanco, S. A., and Buehrle, C. Some integer values in the spectra of burnt pancake graphs.Linear Algebra Appl. 703(2024), 163–172

work page 2024

[3] [3]

A., Buehrle, C., and Patidar, A

Blanco, S. A., Buehrle, C., and Patidar, A. Cycles in the burnt pancake graph. Discrete Appl. Math. 271(2019), 1–14

work page 2019

[4] [4]

A., Buehrle, C., and Patidar, A

Blanco, S. A., Buehrle, C., and Patidar, A. Onthenumberofpancakestacks requiring four flips to be sorted. Discrete Mathematics & Theoretical Computer Science Vol. 21 no. 2, Permutation Patterns 2018(Nov. 2019)

work page 2018

[5] [5]

Pancake flipping is hard.J

Bulteau, L., Fertin, G., and Rusu, I. Pancake flipping is hard.J. Comput. System Sci. 81, 8 (2015), 1556–1574

work page 2015

[6] [6]

Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap.Electronic Journal of Combinatorics 16(04 2009)

Cesi, F. Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap.Electronic Journal of Combinatorics 16(04 2009)

work page 2009

[7] [7]

The spectral gap of graphs arising from substring reversals

Chung, F., and Tobin, J. The spectral gap of graphs arising from substring reversals. Electron. J. Combin. 24(07 2017), 1–18. 17

work page 2017

[8] [8]

Spectra and eigenspaces from regular partitions of cayley (di)graphs of permutation groups.Linear Algebra and its Applications 597 (2020), 94–112

Dalfó, C., and Fiol, M. Spectra and eigenspaces from regular partitions of cayley (di)graphs of permutation groups.Linear Algebra and its Applications 597 (2020), 94–112

work page 2020