Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 8 min ago
PreprintCC BY-NC-SA 4.0arXiv

On the Laplacian spectral gap of generalized pancake graphs

  • Saúl A. Blanco
Open at sourcePDFDOICite

Abstract

The generalized pancake graph P(m,n) is the Cayley graph of the group of colored permutations ℤmwr Sn=(ℤm)nrtimes Sn generated by generalized prefix reversals. In this paper, we establish that, for all m,n≥2, the spectral gap $γ(P(m,n))$ of the normalized Laplacian satisfies αm/n≤γ(P(m,n))≤1/n, where αm is a positive constant that depends only on m. As a consequence, for every fixed m≥2, $γ(P(m,n))$ is Θm(1/n) as n→∞. The proof combines Cesi's semi-recursive spectral-gap inequality with a Fourier decomposition of the appropriate operators associated with a coset Schreier graph of color-position pairs. For fixed n≥2, we also establish that $γ(P(m,n))$ is Θn(m−2) as m→∞. This disproves a conjecture of Blanco and Buehrle asserting that, for fixed n, the corresponding undirected generalized pancake graphs form an expander family. Additionally, we present a counterexample to a recent conjecture of Greaves and Zhu concerning equality between the spectral gaps of the full Cayley graph and the associated coset Schreier graph.

Related

  1. Characterization of graphs attaining the maximum signless Laplacian spectral radius under forbidden cycles and theta graphs
    Mainak Basunia, Pratima Panigrahi
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The Algebraic Connectivity and Laplacian Spectral Radius of Token Graphs
    Xiaodi Song, Cristina Dalfó, Miquel Àngel Fiol +1
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. A solution to a conjecture on the signless Laplacian spectral radius for t-color-critical graphs
    Ming-Zhu Chen, Ya-Lei Jin, Peng-Li Zhang +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Signless Laplacian spectral conditions for rainbow matchings in a collection of bipartite graphs
    Zhiwei Guo, Nanxi Pan, Li Li +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Connected graphs having maximum signless Laplacian spectral radius
    Di-Jian Wang, Hong-Yan Ge, Shi-Cai Gong +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{blanco2026laplacian,
  title = {{On the Laplacian spectral gap of generalized pancake graphs}},
  author = {Saúl A. Blanco},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.15398},
  eprint = {2608.15398},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.15398},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - On the Laplacian spectral gap of generalized pancake graphs
AU  - Saúl A. Blanco
PY  - 2026
DA  - 2026/09/03
PB  - arXiv
DO  - 10.48550/arxiv.2608.15398
UR  - https://arxiv.org/abs/2608.15398
AB  - The generalized pancake graph P(m,n) is the Cayley graph of the group of colored permutations ℤ_mwr S_n=(ℤ_m)^nrtimes S_n generated by generalized prefix reversals. In this paper, we establish that, for all m,n≥2, the spectral gap $γ(P(m,n))$ of the normalized Laplacian satisfies α_m/n≤γ(P(m,n))≤1/n, where α_m is a positive constant that depends only on m. As a consequence, for every fixed m≥2, $γ(P(m,n))$ is Θ_m(1/n) as n→∞. The proof combines Cesi's semi-recursive spectral-gap inequality with a Fourier decomposition of the appropriate operators associated with a coset Schreier graph of color-position pairs. For fixed n≥2, we also establish that $γ(P(m,n))$ is Θ_n(m^−2) as m→∞. This disproves a conjecture of Blanco and Buehrle asserting that, for fixed n, the corresponding undirected generalized pancake graphs form an expander family. Additionally, we present a counterexample to a recent conjecture of Greaves and Zhu concerning equality between the spectral gaps of the full Cayley graph and the associated coset Schreier graph.
ER  -