"""INDEPENDENT REIMPLEMENTATION (Battery 4) for the Graffiti 284 refutation and the Graffiti 290 proof. Written from the frozen statements only; no code shared with the primary verifiers (different construction of HS, different gravity accumulation, different eigensolver path, different graph generators). 284: If girth >= 5 then min dual degree <= - smallest eigenvalue of distance matrix. Claim: Hoffman-Singleton violates it (7 > 4). 290: If girth >= 5 then -(second smallest adjacency eigenvalue) <= size/meangravity. Claim: theorem. Spot-check on many graphs incl. large random girth>=5 and cages. """ import math, random import numpy as np import networkx as nx # ---------- Hoffman-Singleton from the standard pentagon/pentagram construction ---------- def hoffman_singleton(): G = nx.Graph() # pentagons P_h (h=0..4): vertices ('p',h,i); pentagrams Q_h: ('q',h,i) for h in range(5): for i in range(5): G.add_edge(('p', h, i), ('p', h, (i + 1) % 5)) # C5 G.add_edge(('q', h, i), ('q', h, (i + 2) % 5)) # pentagram for h in range(5): for k in range(5): for i in range(5): G.add_edge(('p', h, i), ('q', k, (h * k + i) % 5)) # joins return G G = hoffman_singleton() assert G.number_of_nodes() == 50 and G.number_of_edges() == 175 assert min(d for _, d in G.degree()) == max(d for _, d in G.degree()) == 7 assert nx.is_connected(G) # girth 5: no triangles/C4 -> check via A^2 and A*A common-neighbor counts nodes = sorted(G.nodes()) A = nx.to_numpy_array(G, nodelist=nodes, dtype=np.int64) A2 = A @ A assert np.trace(A @ A2) == 0, "triangle found" # tr A^3 = 6*#K3 common = A2 - np.diag(np.diag(A2)) assert common[A.astype(bool)].max() == 0, "adjacent pair with common neighbor (C3)" assert common[(~A.astype(bool)) & (~np.eye(50, dtype=bool))].max() <= 1, "C4 found" # there IS a 5-cycle (pentagon) so girth is exactly 5 print("[284] independent HS construction: n=50 m=175 7-regular girth 5 OK") # distance matrix by matrix powers: dist 1 where A=1; dist 2 where A2>0 & A=0 D = np.where(A > 0, 1, np.where((A2 > 0) & (np.eye(50) == 0), 2, 0)) assert (D + np.eye(50, dtype=np.int64) > 0).all(), "diameter > 2?" eigD = np.linalg.eigvalsh(D.astype(float)) lam_min = eigD.min() min_dual = 7.0 # regular print(f"[284] lambda_min(D) = {lam_min:.9f}; min dual degree = {min_dual}") assert abs(lam_min + 4) < 1e-9 assert min_dual > -lam_min + 2.9, "margin should be ~3" print(f"[284] 7 <= 4 FALSE, margin {min_dual + lam_min:.9f} -> REFUTED [INDEPENDENT PASS]") print() # ---------- 290 spot checks ---------- def mean_gravity(G): nodes = list(G.nodes()) n = len(nodes) idx = {v: k for k, v in enumerate(nodes)} deg = np.array([G.degree(v) for v in nodes], dtype=float) tot = 0.0 for u, dists in nx.all_pairs_shortest_path_length(G): iu = idx[u] for v, d in dists.items(): if v != u: tot += deg[iu] * deg[idx[v]] / d return tot / ((len(nodes) - 1) * n * n) def check290(G, name): n = G.number_of_nodes(); m = G.number_of_edges() A = nx.to_numpy_array(G, dtype=float) ev = np.sort(np.linalg.eigvalsh(A)) lhs = -ev[1] rhs = m / mean_gravity(G) ok = lhs <= rhs + 1e-9 print(f"[290] {name:<28} n={n:<4} m={m:<4} -lam2min={lhs:>8.4f} m/meanG={rhs:>11.3f} {'OK' if ok else 'VIOLATION!'}") assert ok, name return rhs - lhs margins = [] margins.append(check290(hoffman_singleton(), "HoffmanSingleton")) margins.append(check290(nx.petersen_graph(), "Petersen")) margins.append(check290(nx.heawood_graph(), "Heawood(6-cage)")) margins.append(check290(nx.cycle_graph(5), "C5")) margins.append(check290(nx.path_graph(2), "K2/P2")) margins.append(check290(nx.star_graph(20), "Star K1,20")) # McGee 7-cage from LCF notation [12,7,-7]^8 margins.append(check290(nx.LCF_graph(24, [12, 7, -7], 8), "McGee(7-cage)")) # Tutte-Coxeter 8-cage LCF [-13,-9,7,-7,9,13]^5 margins.append(check290(nx.LCF_graph(30, [-13, -9, 7, -7, 9, 13], 5), "TutteCoxeter(8-cage)")) # random trees and random girth>=5 subgraphs rng = random.Random(7) for k in range(60): n = rng.randint(2, 60) T = nx.random_labeled_tree(n, seed=rng.randint(0, 10**9)) margins.append(check290(T, f"randomTree(n={n})#{k}") if k < 3 else None) if False else None # quiet check A = nx.to_numpy_array(T, dtype=float) ev = np.sort(np.linalg.eigvalsh(A)) lhs = -ev[1] if n >= 2 else 0.0 rhs = T.number_of_edges() / mean_gravity(T) assert lhs <= rhs + 1e-9, f"tree violation n={n}" print(f"[290] 60 random trees (2<=n<=60) pass quietly") # random girth>=5: start from random regular, delete an edge from every short cycle cnt = 0 for k in range(40): n = rng.choice([20, 30, 40, 50]); d = rng.choice([3, 4]) if n * d % 2: continue H = nx.random_regular_graph(d, n, seed=rng.randint(0, 10**9)) changed = True while changed: changed = False try: g = nx.girth(H) except Exception: break if g < 5: cyc = nx.find_cycle(H) # some cycle; remove one edge of a shortest one # find an actual short cycle via BFS from each node done = False for src in H.nodes(): if done: break for u, v in list(H.edges()): pass # simpler: remove edges from any 3- or 4-cycle found by common neighbors A = nx.to_numpy_array(H, dtype=np.int64) nl = list(H.nodes()); ix = {v: i for i, v in enumerate(nl)} A2 = A @ A for u, v in list(H.edges()): if A2[ix[u], ix[v]] > 0: # triangle edge H.remove_edge(u, v); changed = True; done = True; break if not done: NA = (A2 > 1) & (A == 0) & (~np.eye(len(nl), dtype=bool)) w = np.argwhere(NA) if len(w): a, b = w[0] # two common neighbors -> C4 cn = [x for x in H.nodes() if H.has_edge(nl[a], x) and H.has_edge(x, nl[b])] H.remove_edge(nl[a], cn[0]); changed = True if not nx.is_connected(H): H = H.subgraph(max(nx.connected_components(H), key=len)).copy() try: if nx.girth(H) < 5: continue except Exception: pass if H.number_of_nodes() < 3: continue A = nx.to_numpy_array(H, dtype=float) ev = np.sort(np.linalg.eigvalsh(A)) lhs = -ev[1] rhs = H.number_of_edges() / mean_gravity(H) assert lhs <= rhs + 1e-9, "random girth>=5 violation" cnt += 1 print(f"[290] {cnt} random girth>=5 pruned graphs pass quietly") print() print("BATTERY 4 (independent reimplementation): ALL PASS for 284-refutation and 290-theorem.")