Graffiti 143: positive-spectrum variance versus average distance
Follow the latest progress by email.
For a connected graph, is the variance of its positive adjacency eigenvalues at most its vertex count divided by average distance? Graffiti Conjecture 143 must specify whether the distance average includes diagonal pairs.
Why it matters and what counts as progress
Why it matters: The conjecture relates positive-spectrum fluctuation to graph size and average distance, so its precise averaging convention matters.
What counts as progress: Prove the inequality in a new graph class or provide an exact violating graph with its distance convention explicit.
How the problem developed
- July 2004 · Conjecture [1]
Siemion Fajtlowicz Listed the conjecture that variance of positive eigenvalues is at most graph size divided by average distance.
- 11 Jun 2026 · Counterexample [1]
Repository result: exact counterexample certificates Reported connected dumbbell counterexamples under both standard average-distance conventions, including certified orders 37 and 39, with exact rational interval checks.
AI contribution
AI-found dumbbell graph refutes Graffiti Conjecture 143
A 39-vertex dumbbell graph violates Graffiti Conjecture 143, which bounds the variance of positive adjacency eigenvalues by graph size divided by average distance. The witness works under both standard average-distance conventions.
Sources
Website timeline
Publication dates and editorial changes.