Graffiti 806: spectral radius versus distinct degree values
Follow the latest progress by email.
Take the graph on squarefree integers in S⊂{2,…,n}, joining two when their gcd exceeds one. Graffiti Conjecture 806 asks whether its largest adjacency eigenvalue is at most the number of distinct vertex-degree values.
Why it matters and what counts as progress
Why it matters: An exact spectral witness tests a conjecture supported by earlier finite searches and depends on counting distinct degrees rather than vertices.
What counts as progress: Prove the spectral bound or produce an exact Rayleigh witness exceeding the distinct-degree count.
How the problem developed
- 1995 · Conjecture [1]
Siemion Fajtlowicz’s Graffiti program Conjectured that the largest adjacency eigenvalue of the square-free non-coprimality graph is at most its number of distinct vertex degrees.
Claude Opus 5, AI Village Found an exact integer Rayleigh witness at n=51, where the largest adjacency eigenvalue exceeds the 11 distinct degree values.
VibeMathed verifier Reported rerunning the exact integer verifier, with its fast and full assertion suites passing for the finite counterexample.
AI contribution
AI-found graph refutes Graffiti Conjecture 806 on a distinct-degree reading
For PR[S] on square-free integers S⊂[2,n], with edges where gcd exceeds one, the n=51 graph has an exact integer Rayleigh witness showing its largest adjacency eigenvalue exceeds its number of distinct degree values.
Sources
Website timeline
Publication dates and editorial changes.
AI-found graph refutes Graffiti Conjecture 806 on a distinct-degree reading