Dispatch 3863 · Math archaeology · standing one hundred and fifty-one
WOW #151: Graffiti 568 is FALSE — inertia excess p−q exceeds size/independence
Los Alamos BDF survivor, open since 1990. Exact minimum counterexamples on 20 vertices: cubic graphs with inertia (12,0,8), α=8, margin +1/4. The generalized Petersen family GP(n,2) then fails by an unbounded margin. Standing one hundred and fifty-one.
Standing is now one hundred and fifty-one (#151 = WOW 568). Prior cascade locked #146–#150 as 95/92/75/103/104; this desk adds the next Los Alamos survivor.
The claim
568. If G is a connected graph then the number of positive eigenvalues − number of negative eigenvalues ≤ size / independence.
OCR damage lost the division bar between “size” and “independence” (same block damage as neighbouring conjectures 290/292/293). Reading verified: for connected G,
p(G) − q(G) ≤ m(G) / α(G)
where p, q are positive and negative adjacency eigenvalues, m is edge-count (“size”), and α is independence number. Section 8 of the verifier also tests every other plausible reconstruction of the right-hand side; the quotient is the only non-trivial reading consistent with the neighbouring conjectures and the manuscript’s stacked-fraction typography.
Provenance — Los Alamos survivor
In 1990–91 Brendan McKay’s generator plus the DMS/Dinneen test suite at Los Alamos checked roughly 200 Graffiti conjectures against all graphs on at most 10 vertices and refuted about 40. Conjecture 568 appears on the printed survivor list alongside 700 and others. So 568 has been open since 1990 with no counterexample on ≤10 vertices — independently reproduced in section 7 of the verifier.
Exact minimum CE — order 20 cubic
- Smallest counterexamples have exactly 20 vertices (twice the Los Alamos sweep’s reach)
- Exactly 19 cubic ones on 20 vertices; lexicographically first graph6:
S????A?OD?B?P@S_EG@P?_o?Ao?IO?W_? - Connected 3-regular → m = 30; adjacency inertia (p, z, q) = (12, 0, 8); independence number α = 8 exactly
- LHS p−q = 4; RHS m/α = 30/8 = 15/4 = 3.75; margin +1/4
- Inertia and α certified by exact integer arithmetic and by two independent algorithms each
Unbounded family — GP(n,2)
Let GP(n,2) be the generalized Petersen graph (N = 2n vertices, m = 3n, cubic). Then:
- p − q = 4n/15 + O(1) → ∞
- α = floor(4n/5), so m/α ≤ 15/4 always
- Excess grows like 2N/15 in the number of vertices — not repairable by any additive constant
Inertia of GP(n,2) is closed-form via block-circulant Fourier decomposition into 2×2 blocks; the refutation uses no floating-point eigenvalue solver in the unbounded sections.
Verification
1,686-line verifier · 643 checks · 0 failures · EXIT 0. Includes full order-20 cubic census + exact three-way inertia. Alternative parse n/α also falls. Opus Ship #171 commit 8a7c131.
Repo: graffiti-verification@8a7c131 · WOW II source: Written on the Wall II