didericis
984655fd3d
Backward bridge-switch search (sharded over valid parity partitions) found an Even Level Graph witness for each of the four previously-open duals: dual 0: partition 12, witness orbit 9458 dual 3: partition 9, witness orbit 388 dual 4: partition 23, witness orbit 3842 dual 5: partition 12, witness orbit 165668 So all four are bridge-derived level graphs, hence valid derived level graphs. Combined with the two duals that are Even Level Graphs outright, the disjunction is now confirmed for ALL SIX critical iso classes at n=21 -- the first nontrivial test of the conjecture passes. Why it worked where exhaustion failed: a witness, when it exists, tends to sit in a SMALL orbit (here a few hundred to ~1.7e5 states) reachable quickly, while other parity partitions of the same triangulation have orbits >1e6. We only need one good partition. The bridge restriction both shrinks orbits ~100x and guarantees validity, so any ELG found in a backward orbit is an immediate witness. - Update paper n=21 subsection to report the resolution. - Add shard_hunt.py (partition-sharded parallel witness hunt). Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
60 lines
2.3 KiB
Python
60 lines
2.3 KiB
Python
"""Witness-hunt for one dual, sharded across processes: shard k of m scans
|
|
valid parity partitions [k::m]. First witness found anywhere proves the
|
|
dual is bridge-derived. Run several shards in parallel."""
|
|
import sys
|
|
import os
|
|
import time
|
|
sys.path.insert(0, '/Users/didericis/Code/math-research/papers/'
|
|
'level_resolutions_of_maximal_planar_graphs/experiments')
|
|
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
|
|
from load_holton_mckay import parse_planar_code
|
|
from tutte_dual_treecolor import dual_triangulation
|
|
from exhaustive_bridge import valid_parity_partitions
|
|
from fast_bridge import EdgeCode
|
|
from fast_decide import expand_and_check
|
|
|
|
|
|
def run(i, shard, nshards, cap):
|
|
graphs = parse_planar_code('experiments/nonham38m4.pc')
|
|
G, _ = dual_triangulation(graphs[i][0])
|
|
n = G.number_of_nodes()
|
|
code = EdgeCode(G.nodes())
|
|
code.state0 = code.state_of(G)
|
|
parts = list(valid_parity_partitions(G))
|
|
mine = list(range(shard, len(parts), nshards))
|
|
print(f'dual {i} shard {shard}/{nshards}: {len(mine)} partitions', flush=True)
|
|
t0 = time.time()
|
|
for j in mine:
|
|
labels = parts[j]
|
|
seen = {code.state0}
|
|
frontier = [code.state0]
|
|
found = False
|
|
while frontier and len(seen) < cap:
|
|
new = []
|
|
for st in frontier:
|
|
wit, neigh = expand_and_check(st, code, labels, n)
|
|
if wit:
|
|
found = True
|
|
break
|
|
for ns in neigh:
|
|
if ns not in seen:
|
|
seen.add(ns)
|
|
new.append(ns)
|
|
if found:
|
|
break
|
|
frontier = new
|
|
if found:
|
|
print(f'dual {i} shard {shard}: WITNESS at partition {j} '
|
|
f'(orbit>={len(seen)}, {time.time()-t0:.0f}s) -> BRIDGE-DERIVED',
|
|
flush=True)
|
|
return
|
|
print(f' shard {shard} part {j}: no witness (orbit {len(seen)}, '
|
|
f'{time.time()-t0:.0f}s)', flush=True)
|
|
print(f'dual {i} shard {shard}: done, no witness in my partitions', flush=True)
|
|
|
|
|
|
if __name__ == '__main__':
|
|
i = int(sys.argv[1]); shard = int(sys.argv[2]); nshards = int(sys.argv[3])
|
|
cap = int(sys.argv[4]) if len(sys.argv) > 4 else 300000
|
|
run(i, shard, nshards, cap)
|