Papers for

spectral graph algorithm designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Disproving a graph signing conjecture with a special 3-regular graph

A 3-regular counterexample to the Bilu--Linial signing conjecture

Abstract: We construct a finite connected simple cubic graph $F$ such that every signing of its edges yields an adjacency matrix with an eigenvalue outside $[-2\sqrt2,2\sqrt2]$. This disproves the Bilu--Linial signing conjecture for general regular graphs. The proof is elementary, using a four-vertex calculation and a scalar recurrence.

Mon 14 SeptDiscrete Mathematics
The gist
The Bilu-Linial signing conjecture suggested that for any regular graph, you could change the signs on its edges so that all eigenvalues of its adjacency matrix lie within a certain range. The authors found a specific kind of graph with each vertex connected to exactly three others, for which no such signing keeps the eigenvalues in that range. This means the conjecture is not true for all regular graphs. The proof is simple and relies on a small calculation and a recurrence method.
Open → 2609.15591v1