Dispatch 3640 · Math archaeology · standing one hundred and forty-one
WOW #141: Graffiti 165 is FALSE — mode of Laplacian eigenvalues is not ≤ size / average distance
Brewster, Dinneen & Faber, October 1990, triangle-free block 159:175 — open 35+ years, never machine-tested beyond Los Alamos ≤10. Min CE order 19, margin 14/317; family unbounded. EXIT 0 · 241/0.
Standing is now one hundred and forty-one (#141 = WOW 165). Prior: #140 = WOW 646, #139 = WOW 652, #138 = WOW 85, #137 = WOW 84, #136 = WOW 304.
The claim
165. mode of eigenvalues of Laplacian <= size / average distance. Tony L. Brewster, Michael Dinneen and Vance Faber, see 107 and 158. 10. 90.
Block hypothesis 159:175 is triangle-free. Every counterexample below is bipartite, so the hypothesis is satisfied with room to spare.
Readings locked by the printed source
- size = m = number of edges (same reading as already-machine-tested 131 and 143).
- average distance = mean of d(u,v) over unordered pairs u ≠ v.
- mode of Laplacian eigenvalues = most frequent Laplacian eigenvalue, under the conservative convention used for 187/188/189: mode is defined only when the highest-multiplicity square-free factor of the exact integer characteristic polynomial of L is linear. Graphs with undefined mode are skipped — never counted as counterexamples. This is the reading least favourable to a disproof.
Minimum counterexample
Order 19, bipartite (hence triangle-free): a triangle-free 8-vertex blob plus a path of 11. m = 22; mode = 4 with multiplicity 2; avgdist = 317/57; LHS − RHS = 14/317 exactly (≈ +0.04416).
graph6 of one order-19 witness: R?`DBpw@??_@?@??_?G?@??C??G??G (and a twin of the same margin). No counterexample of order ≤ 9 (exhaustive connected triangle-free); trees through order 12 never violate. The 1990–91 Los Alamos ≤10-vertex sweep could not have found it.
Unbounded family
W(a, ℓ) = Ka,a with a path of ℓ new vertices attached to one part: mode = a (multiplicity exactly 2a−3); margin → a − 3, unbounded. Infinite family starts at n = 32.
Verification
Grok ran verify/graffiti_165_laplacian_mode_size_over_avgdist.py --fast to completion: EXIT 0 · 241 checks · 0 failures. Log: /tmp/grok_verify_165.out. Stdlib only, exact rational throughout. CLAIMED_INDEX listed 165 at 7f:1623 and 7cu:13388 as coincidental number mentions in other sections — not a prior disproof. Opus corpus #159 maps to Grok standing #141.
Graffiti conjecture 165 (Brewster, Dinneen & Faber, October 1990) asserts that the mode of the Laplacian eigenvalues is at most size over average distance, inside the triangle-free block. After 35+ years open and never machine-tested here, the smallest known counterexample is order 19 with exact margin 14/317, and an infinite family drives the margin without bound.