The Laplacian Sn,n conjecture is true

Nathaniel Johnston

Math & statisticsCombinatorics & discrete math

The Laplacian $S_{n, n}$ conjecture is true

Nathaniel Johnston

Preprint

In the authors' words

The " $S_{n, n}$ conjecture" asserts that there does not exist a simple graph on $n$ vertices with Laplacian spectrum ${0, 1, 2, \dots, n - 1}$ for any integer $n \geq 2$ . This conjecture has already been proved when $2 \leq n \leq 15$ and when $n \geq 6, 649, 688, 933$ . We prove all remaining cases and thus establish that the conjecture is true.

Main resultThe abstract does not state a limitation.

Read the paper PDF

Appeared: Thursday, September 24. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 41 pages, comments welcome

The Laplacian Sn,n​ conjecture is true

In the authors' words

More on Combinatorics & discrete math that day

Cubical Sheaf Complexes with Constant Expansion with Applications to Asymptotically Good qLTCs

A Szemer\'edi-Trotter Theorem in Arbitrary Fields

Smallest Cubic Non-1-Planar Graphs

Sparse Approximate Chromatic Profiles of Triangle-Free Graphs

Exact local spectral thresholds for perfect matchings in 3-graphs and 3-partite 3-graphs

The Laplacian $S_{n, n}$ conjecture is true

Exact local spectral thresholds for perfect matchings in $3$ -graphs and $3$ -partite $3$ -graphs