Skip to content
Preprint

The Sparse-Complement Conjecture for Two Distinct Eigenvalues

Nov 2026 · 0 citations · 14 references
Mathematics

Abstract

For a graph $G$, let $q(G)$ be the minimum number of distinct eigenvalues of a real symmetric matrix whose off-diagonal zero--nonzero pattern is $G$. We prove that $q(G)=2$ whenever the complement $H=\overline G$ of a graph of order $n\ge3$ has at most $n-3$ edges, resolving the sparse-complement conjecture of Fallat and Mojallal. If $H$ contains a cycle, the proof constructs a nontrivial orthogonal projector with the strong spectral property and rank at most $|E(F)|-|V(F)|+4$, where $F$ is the union of the cyclic components of $H$. The construction combines faithful stress-free Gram representations, a one-coordinate lift for each excess core edge, exact orthogonal-frame completion, and a Stiefel-manifold pendant-extension argument.

View source

Similar papers

Preprint Oct 2026

A sharp bound for the least signless Laplacian eigenvalue of triangle-free graphs

We prove that every finite simple triangle-free graph $G$ on $n\geq1$ vertices satisfies $q_{\min}(G)\leq7n/50$, where $q_{\min}(G)$ is the least eigenvalue of its signless Laplacian matrix $Q_G=D_G+A_G$, with $D_G$ the diagonal matrix of vertex degrees and $A_G$ the adjacency matrix. The constant is sharp, since the H...

Dong-Xiu Cai, Zheng-Bo Chen, Xiao-Dong Zhang · 0 citations
Preprint Oct 2026

Transposition Cayley Spectra and Subgraph Counts

Let $G$ be a finite simple graph on the vertex set $[n]$, and let $\Gamma(G)$ be the Cayley graph of the symmetric group $S_n$ generated by the transpositions corresponding to the edges of $G$. We study the inverse spectral problem for the assignment $G\mapsto \Gamma(G)$ through the group-algebra operator $A_G=\sum_{\{...

Boris Shapiro · 0 citations
Preprint Oct 2026

The least signless Laplacian eigenvalue of $\{C_3,C_5\}$-free graphs

Brandt [Discrete Math. 183 (1998) 17--25] conjectured that the least signless Laplacian eigenvalue of every regular triangle-free graph of order $n$ is at most $4n/25$. Using flag algebras, Balogh, Clemen, Lidick\'y, Norin and Volec [SIAM J. Discrete Math. 37 (2023) 1173--1179] established the stronger bound $15n/94$ f...

Qi Zhou · 2 citations
Preprint Oct 2026

$D^L$, $D^Q$ Spectrum and Eigenvalue-free Interval of Cayley Graphs over Finite Nilpotent Groups

For a finite group $G$ and a symmetric connection set $S$, we study the distance Laplacian ($D^L$) and distance signless Laplacian ($D^Q$) spectrum of the Cayley graph $\Cay(G,S)$ for $G$ a finite nilpotent group. Using the internal direct product decomposition over Sylow subgroups, we reduce every question to a single...

Pallabi Manna, Santanu Mandal · 0 citations
Preprint Sep 2026

Hoffman-type Results for the Sum of k Largest Eigenvalues of a Graph

Let $S_k(G)$ denote the sum of the $k$ largest eigenvalues of a graph $G$. Motivated by the classical Hoffman program for the spectral radius of a graph, we investigate an additive Hoffman-type problem for $S_k(G)$. For each fixed $k\geq 2$ and sufficiently large order $n$, we characterize all connected graphs satisfyi...

Shao-Wei Sun, Meng-Yao Guo, Hong-Yan Ge et al. · 0 citations
Preprint Oct 2026

Low-rank matrices with three prescribed off-diagonal values over $\mathbb{F}_p$

For every prime $p$ and every three-element set $L\subseteq\mathbb{F}_p$, we prove that, for every integer $n\geq1$, there exists a symmetric $n\times n$ matrix over $\mathbb{F}_p$ with zero diagonal, off-diagonal entries in $L$, and rank $O_{p,L}(n^{1/3})$. This answers a question of Bukh. When $0\notin L$, a standard...

F. Rakhmonov, Chi-Hoi Yip · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.