Determine the digraph Ramsey function $k(n,m)$: independent set vs transitive tournament (Erdős #112)
Statement
Let $k=k(n,m)$ be the least integer such that every directed graph on $k$ vertices contains either an independent set of size $n$ (a set of $n$ vertices spanning no directed edge) or a transitive tournament of size $m$ (a set of $m$ vertices whose induced subdigraph is a transitive tournament, i.e. admits a linear ordering $v_1,\dots,v_m$ with an arc from $v_i$ to $v_j$ exactly when $i<j$). Determine $k(n,m)$, exactly or asymptotically in $n$ and $m$.
Acceptance. FULLY RESOLVES: a proof determining $k(n,m)$ — either a closed form, or matching upper and lower bounds pinning its asymptotic order in $n$ and $m$ — machine-checkable (Lean/Coq) preferred, otherwise a complete written proof with every step. ADVANCES, each a checkable milestone: (a) an upper bound on $k(n,m)$ strictly better than the best bound stated in the background (the Erdős–Rado $\frac{2^{m-1}(n-1)^m+n-2}{2n-3}$ and Larson–Mitchell $k(n,3)\le n^2$ bounds), with a complete proof; (b) a lower bound strictly exceeding the trivial $k(n,m)\ge R(n,m)$, with a construction; (c) an exact value $k(n,m)$ for a specific small $(n,m)$ established by a verified exhaustive digraph search together with a machine-checkable exhaustiveness certificate. Deliver the proof file, or the search program plus the exact value and its exhaustiveness certificate.
Background
Posed by Erdős and Rado [ErRa67], who proved $k(n,m)\ll_m n^{m-1}$, and more precisely $k(n,m)\le \frac{2^{m-1}(n-1)^m+n-2}{2n-3}$. Larson and Mitchell [LaMi97] improved the dependence on $m$, in particular establishing $k(n,3)\le n^2$. Zach Hunter observed that $k(n,m)$ is sandwiched between ordinary Ramsey numbers, $R(n,m)\le k(n,m)\le R(n,m,m)$, which in particular yields the upper bound $k(n,m)\le 3^{n+2m}$. A word of caution for solvers: a superficially similar variant (the one used in the UCSD 'graphs problem collection') replaces 'transitive tournament of size $m$' by 'directed path on $m$ vertices'; for that variant Hunter and Steiner have a short argument giving the exact answer $k(n,m)=(n-1)(m-1)$. The transitive-tournament version stated here is the open problem and is not settled by that argument. Listed as open on erdosproblems.com/112 (fetched 2026-07-13, status 'open'), tagged graph theory | ramsey theory; no prize is attached. Attacker's tool: exhaustive or SAT-based enumeration of small directed graphs to pin exact values $k(n,m)$ (e.g. the first open cases of $k(n,3)$) and to test candidate extremal digraphs, combined with the Ramsey-number sandwich to bound the general growth.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #112 (T. F. Bloom) | website |
| REF-02 | Directed paths — UCSD graphs problem collection (variant with directed paths) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.