CS Paper Radar

On the Laplacian spectral gap of generalized pancake graphs

Saúl A. Blanco

cs.DM math.CO ·submitted 2026-08-15 20:05 UTC · v2

Abstract

The generalized pancake graph $P(m,n)$ is the Cayley graph of the group of colored permutations $\mathbb{Z}_m\wr S_n=(\mathbb{Z}_m)^n\rtimes S_n$ generated by generalized prefix reversals. In this paper, we establish that, for all $m,n\geq2$, the spectral gap $γ(P(m,n))$ of the normalized Laplacian satisfies $α_m/n\leqγ(P(m,n))\leq1/n$, where $α_m$ is a positive constant that depends only on $m$. As a consequence, for every fixed $m\geq2$, $γ(P(m,n))$ is $Θ_m(1/n)$ as $n\to\infty$. 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\geq2$, we also establish that $γ(P(m,n))$ is $Θ_n(m^{-2})$ as $m\to\infty$. 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.

Comment
Fixed typos, included a new conjecture

Closest papers

Nearest neighbours by meaning across the whole index.

Integrality Gap Bounds for the Goemans-Linial SDP on Finite Abelian Cayley Graphs

cs.DM math.COcs.DS ·2026-09-04 ·Georgios Stamoulis
similarity 0.65
Abstract · 21 pages

In the uniform sparsest cut problem we are asked to find a vertex set that cuts few edges relative to the number of vertex pairs it separates. The Goemans-Linial SDP coupled with the Arora-Rao-Vazirani rounding gives an $\mathcal{O}(\sqrt{\log n})$ approximation on arbitrary graphs on $n$ vertices. We study this relaxation on finite Abelian Cayley graphs. First we show that when the second normalized Laplacian eigenvalue of $G= \mathrm{Cayley}(Γ, S)$ is realized by a Fourier character with image size at most four then $λ_2(G)=\mathrm{SDP}_{\mathrm{GL}}(G)=ψ(G)$. Geometrically, a character maps the vertices onto a regular polygon where the squared chord distance satisfies the triangle inequalities exactly when the polygon has at most four vertices. Grouping equal character fibers gives a cyclic quotient where the optimal cut can be found exactly and so the relaxation is exact on finite Abelian Cayley graphs on groups of exponent at most four. Second, we replace each generator $s$ of $S$ by a uniformly random element of its cyclic subgroup (including identity). If $r_s$ is the order of $s$, we let $α(r_s)$ to be the average number of $\pm s$ steps needed to simulate such a move, and let $ρ(S)=\max_{s\in S}α(r_s)$ be its worst case. Full cyclic averaging eliminates character phases and choosing a nontrivial character $χ^*$ minimizing the auxiliary eigenvalue and taking $K=\mathrm{ker}χ^*$ gives \[ ψ(G)\leqψ_G(K)\leq\frac{q^*}{q^*-1} \cdotρ(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G)\leq 2ρ(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G), \] where $q^*=|χ^*(Γ)|$. If all generator orders are at most $R$, this is an $R/2$ approximation. Finally, we construct an infinite family of finite Abelian Cayley graphs with Goemans-Linial integrality gap exactly $16/15$.

0.27

A sharp higher-order Cheeger inequality

cs.DS math.COmath.SP ·2026-09-28 ·Yunpeng Li
theory similarity 0.62
Abstract

Let $λ_k(G)$ be the $k$th eigenvalue of the normalized Laplacian of a finite undirected weighted graph $G$ with positive degrees, where $k$ is an integer satisfying $1\le k\le |V(G)|$. Let $\varphi_k(G)$ be the minimum possible maximum conductance of $k$ disjoint nonempty vertex sets. We prove $\varphi_k(G)\le C\sqrt{λ_k(G)\log(k+1)}$ for an absolute constant $C$. The number of sets and the spectral index are both $k$, and conductance is measured in the original graph. The logarithmic dependence is optimal up to an absolute constant. The proof combines geometric partitioning of the spectral embedding with minimum-cut improvement and adaptive projections in coefficient space. A single conductance threshold is used throughout the construction. The resulting maps have disjoint supports, and the sum of their Gram matrices is bounded below by an absolute positive multiple of the identity. A dyadic maximal estimate bounds the sum of their internal energies uniformly over unit coefficient vectors. A dimension argument using local eigenvalues then yields exactly $k$ disjoint sparse cuts.

0.05

A Cheeger Inequality for Hypergraphs and Its Applications

cs.DS math.CO ·2026-09-14 ·Raj Kamal, Amitabha Bagchi
similarity 0.59
Abstract

Hypergraphs provide a natural framework for modeling higher-order relationships, but the development of spectral techniques with provable guarantees for general non-uniform hypergraphs remains challenging. Building on Banerjee's normalized adjacency matrix and Spiro's averaging-based diffusion framework, we develop a spectral framework for non-uniform hypergraphs and establish Cheeger's inequality for their conductance. A fundamental result in the spectral theory of hypergraphs asserts that, for every non-covering hypergraph, the second-smallest eigenvalue of its normalized Laplacian is at most one. This spectral characterization yields an improved Cheeger's inequality for non-covering hypergraphs, and we show that the resulting inequality is tight on both sides using cycle and cube hypergraphs. Our framework further yields higher-order Cheeger inequalities and provides theoretical guarantees for Fiedler's spectral partitioning algorithm, all in the setting of hypergraphs. Finally and most notably, we construct a new family of optimal hypergraph expanders that is tight for the Alon-Boppana bound.

0.24

Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials

cs.DM math.CO ·2026-09-14 ·Fangfang Lin, Hong Zhou
theory similarity 0.57
Abstract · 25 pages, slightly improved bound for graphs of girth at least 5, include some recent progress

Bilu and Linial conjectured that every finite $d$-regular graph with $d \geq 2$ admits an edge signing $σ$ whose signed adjacency matrix $A_σ$ has spectral radius at most $2\sqrt{d-1}$. We prove that every signing meeting the mixed-root condition $r_{A_σ}\leq\sqrt{2(d-1)}$ satisfies \[ ρ(A_σ) < \frac{3+\sqrt5}{2}\sqrt{d-1}, \] where $r_{A_σ}$ is the largest root of the mixed determinantal polynomial $χ[A_σ,-A_σ]$. The interlacing theorem of Ravichandran and Srivastava guarantees a signing satisfying the mixed-root condition, so our result improves the coefficient $2\sqrt2$ in their two-sided spectral bound. In the proof, we construct a positive matrix-valued probability measure supported on the roots of $χ[A_σ,-A_σ]$. The second moment gives a simple matrix inequality $A_σ^2 + dI \preceq 4r_{A_σ}^2I$, which yields a preliminary coefficient $\sqrt{7}$. Estimates for the fourth moment use information about short walks to obtain the coefficient $(3+\sqrt{5})/2$. For triangle-free graphs, the coefficient improves to $\sqrt6$, and for graphs with girth at least five, it improves to $\sqrt{35/6}$. As a result of independent interest, we extend the construction to $χ[A_1,\ldots,A_k]$ for Hermitian matrices $A_1,\ldots,A_k$ with zero diagonal, and compute the first two moments explicitly. Finally, an explicit signing of $K_8$ shows that the mixed-root condition alone cannot guarantee a coefficient below $(4+\sqrt5)/\sqrt6$.

0.55

On Eigenvalue Bounds for Bounded Genus Graphs and Minor-Free Graphs

cs.DM math.COmath.SP ·2026-08-27 ·Benedikt Kolbe, Jack Spalding-Jamieson
similarity 0.57
Abstract

In this paper, we resolve a 30-year-old conjecture of Spielman and Teng concerning the performance of the spectral partitioning method on graphs embeddable on an orientable surface of genus $g\ge 1$. In particular, for such a graph $G$ with $n$ vertices and maximum degree $Δ$, we show that the second-smallest eigenvalue of its Laplacian matrix satisfies $λ_2(L_G)\lesssimΔ\frac g n$. We also obtain an improved eigenvalue bound for $K_h$-minor-free graphs of $λ_2(L_G)\lesssimΔ\frac{h^2(\log h)^2}n$. In fact, our results directly prove much stronger results for reweighted eigenvalues, including higher reweighted eigenvalues. As a consequence, we obtain bounds not just on Laplacian eigenvalues, but also on normalized Laplacian eigenvalues and Steklov eigenvalues. Our results for genus-$g$ graphs are optimal for all of these kinds of eigenvalues, while our results for $K_h$-minor-free graphs are optimal up to $\log(h)$ factors. Our techniques for genus-$g$ graphs bootstrap bounded-degree bounds of normalized eigenvalues for entire classes to bounds for reweighted eigenvalues for the same classes without the bounded-degree limitation, while our techniques for $K_h$-minor-free graphs generalize an argument of Korhonen and Lokshtanov, making use of the Lovász local lemma.

0.44

Strong Edge Colouring of Disk Graphs: A 6-Approximation and an Improved Unit-Disk Bound

cs.DM math.CO ·2026-09-27 ·Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Sangita Saha, Saumya Sen
theory similarity 0.56
Abstract · 14 pages, 2 figures

A strong edge colouring of a graph $G$ is an edge colouring in which every colour class is an induced matching. The minimum number of colours is the strong chromatic index $χ'_s(G)$. If each edge $e$ is assigned a list $L'(e)$ and its colour must belong to $L'(e)$, the corresponding parameter is the strong list chromatic index $χ'_{s,\ell}(G)$. From the definitions, $χ'_s(G)\leχ'_{s,\ell}(G)$. Barrett et al. gave an $8$-approximation for strong edge colouring on unit disk graphs and Grelier et al. improved the approximation factor to $6$. Our first result extends this factor-$6$ guarantee from unit disk graphs to the strictly larger class of disk graphs. In another direction, Erdős and Nešetřil conjectured that the strong chromatic index of a graph of maximum degree $Δ$ is asymptotically at most $1.25Δ^2$. The best published general asymptotic upper bound has leading coefficient $1.772$, due to Hurley et al. For unit disk graphs, Dębski et al. proved that $χ'_s(G) \leq 1.625 Δ^2$. Our second result improves this leading coefficient to $225/142 \approx 1.5845$. In fact, the proof establishes a stronger bound $χ'_{s,\ell}(G)\le\frac{225}{142} Δ^2+O(Δ)$ for unit disk graphs.

0.22

The Cayley Completion of a Graph

cs.DM cs.DSmath.CO ·2026-08-31 ·Rigobert Fokam Souop, Laurent Bitjoka
theory similarity 0.55
Abstract

A finite connected graph is rarely a Cayley graph. We measure how far it is from being one: given $G$ with $n$ vertices and $m$ edges, how few edges must be added, or added and deleted, before the result is a Cayley graph of an abelian group of order $n$ on the same vertex set? This defines two invariants, the completion number $γ^{+}$ (additions only) and the Cayley edit distance $γ_{\triangle}$ (both), each normalized by $m$. We show that deciding the edit version is NP-complete already for a fixed cyclic host, by a reduction from Hamiltonian Cycle in which the edit cost of a labeling is $n+m-2k$ when it realizes a longest path with $k$ edges; the optimal cost is $m-n+2pp(G)$, bounded in polynomial time by the matching number. We prove that irregularity alone forces $γ^{+}(G)\ge nΔ^{*}/(2m)-1$, where $Δ^{*}$ is the least $d\geΔ$ with $nd$ even, computable in linear time from the degree sequence; we characterize equality exactly. It is attained on the star, where $γ^{+}(K_{1,q})=(q-1)/2$ and the star maximizes $γ^{+}$, while $γ_{\triangle}$ stays bounded by an absolute constant. We determine paths and grids exactly, $γ^{+}(P_n)=γ^{+}(P_n\,\square\,P_n)=1/(n-1)$, and show $γ_{\triangle}(K_{1,q})\to 2$, not the $3/2$ suggested by the additive case. We report an exhaustive certified census of all $995$ connected graphs on at most seven vertices. The degree bound is attained on $89.4\%$ and the two invariants separate strictly on $84.7\%$, though both rates vary sharply with order: attainment $100\%,100\%,84.8\%,89.7\%$ and separation $0\%,61.9\%,73.2\%,87.7\%$ for $n=4,5,6,7$, dominated by the $853$ graphs on seven vertices. The star uniquely maximizes both. Edit count and the bi-Lipschitz distortion of the completed host are independent, moving oppositely on stars and paths.Data and certificates at doi:10.5281/zenodo.21852006.

0.48

Integral saturation of adjacency-degree lattices

cs.DM math.CO ·2026-11-01 ·Zhipeng Lu
theory similarity 0.55
Abstract

Let $A$ be the adjacency matrix of $G\sim G(n,1/2)$, let $D=\operatorname{diag}(A\mathbf{1})$, and let $Λ_G=\mathbb{Z}\langle A,D\rangle\mathbf{1}$. We prove $\Pr[Λ_G\ne\mathbb{Z}^n]\le n^{-3/20+o(1)}$. Thus two dependent graph operators generate the entire vertex lattice from the constant vector, simultaneously over every prime field. Adjacency alone has a modulo-two rank obstruction for every simple graph of order greater than one, even though its rational word span is typically full. The proof first constructs words containing at most two adjacency operations whose integer span contains $Δ_G^3\mathbb{Z}^n$, where $Δ_G$ is the product of the pairwise differences between distinct degree values. This confines all possible arithmetic obstructions to a finite prime range on a single event. We then remove the remaining obstructions using conditional alternating forms, symmetric random-matrix code estimates, and uniform counts of degree-graded invariant subspaces. We connect the integer lattice to graph reconstruction through pointed moments. Saturation forces every pointed orthogonal AD intertwiner to be a vertex permutation. The short-word construction also shows that a fixed polynomial-size family of ordinary caterpillars, of diameter at most seven and order $O(\sqrt{n\log n})$, identifies almost every graph among all finite simple graphs. For nonsaturated full-rank lattices, we give an exact description of the moment fibre by admissible unimodular overlattices; at index two, the only possible ambiguity is a specified four-vertex Godsil--McKay switch.

0.28