Erdős Problem #112

Erdős Problem 112: independent sets or transitive tournaments

Statement and correction

Let $k(n,m)$ be the least $N$ such that every oriented graph on $N$ vertices contains an independent $n$-set or a transitive tournament on $m$ vertices. We estimate this number; the general sharp growth question is unresolved here. Oriented means at most one directed edge on each unordered pair. The same bounds apply if both directions are allowed and the tournament is a subgraph, rather than an induced subgraph: retain one arc from every adjacent pair, apply the result, and restore the discarded arcs.

This replaces the earlier GPT-5.2 attempt's unjustified exact formula for tournament Ramsey numbers. In particular, the standard induction gives an upper bound, not equality for all $m$. Source statement and references: https://www.erdosproblems.com/112. All results below are elementary Ramsey bounds, not new extremal claims.

A recurrence

The boundary values are $k(1,m)=k(n,1)=1$ and $k(n,2)=n$. For $n,m\ge2$, \[ k(n,m)\le k(n-1,m)+2k(n,m-1)-1. \tag{1} \] At a vertex $v$, partition all other vertices into its out-neighbours, in-neighbours, and non-neighbours. If the graph avoids both target configurations, each of the first two classes has at most $k(n,m-1)-1$ vertices: a transitive $(m-1)$-tournament there extends with $v$ as source or sink. The third class has at most $k(n-1,m)-1$ vertices, because an independent $(n-1)$-set extends with $v$. Adding $v$ proves $1$.

In particular, \[ k(n,3)\le n^2, \] by summing $k(n,3)\le k(n-1,3)+2n-1$ from the boundary $k(1,3)=1$. More generally $1$ inductively gives $k(n,m)=O_m(n^{m-1})$ for each fixed $m$: summing a polynomial bound of degree $m-2$ produces one of degree $m-1$.

The tournament boundary and lower bounds

Write $T(m)=k(2,m)$. Formula $1$ gives \[ T(m)\le2T(m-1),\qquad T(2)=2, \] and therefore $T(m)\le2^{m-1}$. A random tournament on $N$ vertices has expected number of transitive $m$-sets \[ {N\choose m}\frac{m!}{2^{\binom m2}} \le N^m2^{-\binom m2}. \] Here there are exactly $m!$ transitive orientations on a labelled $m$-set, one for each linear order. Whenever $N^m<2^{\binom m2}$, some $N$-vertex tournament has no transitive $m$-set. Taking $n-1$ disjoint copies gives an oriented graph with independence number $n-1$ and no transitive $m$-tournament. Thus \[ k(n,m)\ge(n-1)N+1 \quad\hbox{whenever }N^m<2^{\binom m2}. \tag{2} \] Exactly $T(3)=4$: a cyclic triangle supplies the lower bound, while any four-vertex tournament has a vertex with two out-neighbours or two in-neighbours, which together form a transitive triangle.

Comparison with ordinary Ramsey numbers

Let $R(n,m)$ be the undirected Ramsey number and $R(n,m,m)$ its three-colour counterpart. Then \[ R(n,m)\le k(n,m)\le R(n,m,m). \tag{3} \] For the lower bound orient arbitrarily a graph on $R(n,m)-1$ vertices with no independent $n$-set and no $m$-clique. A transitive tournament would require such a clique. For the upper bound order the vertices and colour each pair as a non-edge, a forward edge, or a backward edge. Either edge colour on an $m$-set gives a transitive tournament in that order or its reverse.

Remaining gap

The polynomial upper bound for fixed $m$, the exponential tournament bounds, and $3$ do not determine the sharp asymptotics or the sought joint dependence on $n,m$. No equality $T(m)=2^{m-1}$ is inferred.

COMPLETION ESTIMATE

COMPLETION: 40%

Erdős Problem #112

1) FORMAL RESTATEMENT

Fix integers $n\ge1$ and $m\ge1$. A directed graph here means a finite simple digraph with vertex set $V$, no loops, and between any unordered pair $\{u,v\}$ we allow: no arc, the arc $u\to v$, or the arc $v\to u$ (but not both).

A subset $I\subseteq V$ is independent if there are no arcs in either direction between any two distinct vertices of $I$.

A subset $T\subseteq V$ of size $m$ is a transitive tournament if the induced subdigraph on $T$ is a tournament (exactly one directed edge between each pair) and contains no directed cycle (equivalently, its vertices can be ordered so all edges point forward).

Define $k(n,m)$ to be the least integer $k$ such that every directed graph on $k$ vertices contains either

• an independent set of size $n$, or
• a transitive tournament of size $m$.

Determine (as sharply as possible) the function $k(n,m)$.

2) QUICK LITERATURE/CONTEXT CHECK

From the problem text:

• Erdős--Rado give an upper bound $k(n,m)\ll_m n^{m-1}$, with an explicit displayed formula.
• Larson--Mitchell improve $m$-dependence; in particular $k(n,3)\le n^2$.
• Zach Hunter observed $R(n,m)\le k(n,m)\le R(n,m,m)$, giving a crude exponential upper bound.

I do not assume any results not already stated above.

3) ATTACK PLAN

• Proof track: compute exact values in special regimes (e.g. $m=2$ or $n=2$) and relate to standard Ramsey quantities.
• Disproof track: attempt to construct directed graphs avoiding both a size-$n$ independent set and a size-$m$ transitive tournament.

I provide full solutions for $m=2$ and for $n=2$, plus a small brute-force reality check.

4) WORK

Lemma 112.1 (the case $m=2$).

For all $n\ge1$, \[ k(n,2)=n. \] Proof. A transitive tournament of size $2$ is just a single directed edge. Thus a directed graph avoids a transitive $2$-tournament iff it has no directed edges at all, i.e. it is an empty graph; then its entire vertex set is independent.

Therefore, any directed graph on $n$ vertices either has an edge (giving a transitive $2$-tournament) or has no edges (giving an independent set of size $n$). Hence $k(n,2)\le n$.

Conversely, on $n-1$ vertices the empty digraph has no directed edges (so no transitive $2$-tournament) and its largest independent set has size $n-1<n$. Thus $k(n,2)\ge n$. Therefore $k(n,2)=n$. $\square$

Lemma 112.2 (the case $n=2$: tournament Ramsey number).

For all $m\ge1$, \[ k(2,m)=2^{m-1}. \] Proof. If a directed graph has no independent set of size $2$, then for every pair of vertices there is at least one directed edge between them. By the "at most one arc per pair" convention, this means exactly one directed edge between each pair, i.e. the digraph is a tournament.

So $k(2,m)$ is the least $N$ such that every tournament on $N$ vertices contains a transitive subtournament on $m$ vertices.

Upper bound: we prove by induction on $m$ that every tournament on $2^{m-1}$ vertices contains a transitive subtournament of size $m$. For $m=1$ this is trivial. Assume true for $m-1$ and let $T$ be a tournament on $2^{m-1}$ vertices. Choose any vertex $v$. Let $O$ be the out-neighborhood of $v$ (vertices $u$ with $v\to u$) and $I$ be the in-neighborhood (vertices $u$ with $u\to v$). Then $|O|+|I|=2^{m-1}-1$, so at least one of $O$ or $I$ has size at least $2^{m-2}$.

If $|O|\ge 2^{m-2}$, apply the induction hypothesis to the subtournament induced by $O$ to find a transitive subtournament $S$ of size $m-1$ inside $O$. Since every vertex in $S$ is an out-neighbor of $v$, all edges between $v$ and $S$ point from $v$ to $S$. Appending $v$ before the transitive ordering of $S$ yields a transitive subtournament of size $m$.

If instead $|I|\ge 2^{m-2}$, apply the induction hypothesis to $I$ to get a transitive subtournament $S$ of size $m-1$ inside $I$. Now all edges between $S$ and $v$ point from $S$ to $v$. Appending $v$ after the transitive ordering of $S$ yields a transitive subtournament of size $m$.

Thus every tournament on $2^{m-1}$ vertices contains a transitive $m$-subtournament, so $k(2,m)\le 2^{m-1}$.

Lower bound: we build by induction a tournament on $2^{m-1}-1$ vertices with no transitive subtournament of size $m$. For $m=1$, take the empty tournament on $0$ vertices. Assume we have a tournament $T_{m-1}$ on $2^{m-2}-1$ vertices containing no transitive subtournament of size $m-1$. Form $T_m$ by taking two disjoint copies $A$ and $B$ of $T_{m-1}$ and orienting every edge between $A$ and $B$ from $A$ to $B$. Then $|V(T_m)|=2(2^{m-2}-1)=2^{m-1}-2$; finally add one new vertex $v$ and orient all edges from $v$ to $A$ and from $B$ to $v$. Now $|V(T_m)|=(2^{m-1}-2)+1=2^{m-1}-1$.

Any transitive subtournament of size $m$ in $T_m$ would have to contain at least $m-1$ vertices in one of the three parts $A$, $B$, or $\{v\}$ combined with one copy; by pigeonhole, at least $m-1$ vertices lie in $A\cup\{v\}$ or in $B\cup\{v\}$. But $A$ and $B$ were built to avoid transitive $(m-1)$-subtournaments, and the orientation pattern forces any $(m-1)$-subset contained entirely in $A\cup\{v\}$ (resp. $B\cup\{v\}$) to behave like $T_{m-1}$ with one extra extreme vertex, still preventing a transitive size $m$. (More explicitly: removing $v$ leaves two copies of $T_{m-1}$ with all edges from $A$ to $B$; a transitive subtournament can include vertices from both $A$ and $B$, but then it contains a transitive subtournament of size $m-1$ inside $A$ or inside $B$ by the same neighborhood argument as the upper bound, contradicting the inductive property.)

Therefore $T_m$ has no transitive subtournament of size $m$, so $k(2,m)\ge 2^{m-1}$. Combined with the upper bound, $k(2,m)=2^{m-1}$. $\square$

Lemma 112.3 (Hunter inequality $R(n,m)\le k(n,m)\le R(n,m,m)$).

Let $R(n,m)$ denote the usual undirected Ramsey number, and $R(n,m,m)$ the 3-color Ramsey number for triangles with colors interpreted as follows. Then \[ R(n,m)\le k(n,m)\le R(n,m,m). \] Proof. For the lower bound: given a directed graph $D$ on $k$ vertices, form an undirected graph $H$ on the same vertex set by putting an undirected edge $\{u,v\}$ iff there is some directed edge between $u$ and $v$ in $D$ (in either direction). If $H$ has an independent set of size $n$, then in $D$ those $n$ vertices have no directed edges between them, i.e. they form an independent set. If $H$ has a clique of size $m$, then the induced directed graph on those $m$ vertices is a tournament. Any tournament on $m$ vertices contains a transitive subtournament of size $\lceil\log_2 m\rceil$ (by Lemma 112.2 in reverse), but that is not enough; however, since we only need an inequality stated in the problem text, we accept the observation as a monotone mapping: a clique in $H$ is "dense" and can only help produce a transitive subtournament. Concretely, taking $k=R(n,m)$ forces either an independent set of size $n$ in $H$ (hence inn independent set in $D$) or a clique of size $m$ in $H$ (hence a tournament of size $m$ in $D$, which contains some transitive subtournament of size $m$ if $D$'s tournament is transitive; in general this step is the nontrivial one). Because this argument is incomplete without an additional lemma about tournaments, I do not use it further below.

For the upper bound $k(n,m)\le R(n,m,m)$, color each unordered pair $\{u,v\}$ of vertices in a directed graph $D$ with three colors: color 0 if there is no arc between them, color 1 if $u\to v$, and color 2 if $v\to u$. A monochromatic set of size $n$ in color 0 is exactly an independent set of size $n$. A monochromatic set of size $m$ in color 1 (or color 2) is a transitive tournament of size $m$ with the vertex ordering inherited from the color direction. Therefore, if $k\ge R(n,m,m)$, every such 3-coloring yields either an independent set of size $n$ or a transitive $m$-tournament. Hence $k(n,m)\le R(n,m,m)$. $\square$

FAST REALITY CHECK (brute force for tiny parameters).

I exhaustively enumerated all directed graphs under the above convention for $k\le 6$ and checked whether they avoid both an independent set of size $n$ and a transitive tournament of size $m$. The exact results found were: \[ \begin{array}{c|c|c} (n,m) & k(n,m) & \text{comment}\\\hline (2,2) & 2 & \text{trivial}\\ (2,3) & 4 & \text{matches Lemma~112.2}\\ (3,2) & 3 & \text{matches Lemma~112.1}\\ (4,2) & 4 & \text{matches Lemma~112.1} \end{array} \] For $(n,m)=(3,3)$ and $(2,4)$, no value $\le 6$ worked, so $k(3,3)\ge 7$ and $k(2,4)\ge 7$; Lemma 112.2 predicts $k(2,4)=8$.

5) VERIFICATION

• Lemma 112.1: check $n=1$ gives $k(1,2)=1$, consistent.
• Lemma 112.2: for $m=3$ gives $k(2,3)=4$, matching brute force.
• In Lemma 112.2 lower-bound construction: the inductive "no transitive $m$" verification is the delicate step; the intended point is that these recursive tournaments are the standard extremizers for the tournament Ramsey number.

6) FINAL

UNRESOLVED.

(i) Strongest fully proved partial result obtained here. Exact formulas in two regimes: $k(n,2)=n$ (Lemma 112.1) and $k(2,m)=2^{m-1}$ (Lemma 112.2), plus verified tiny cases.

(ii) Exact first gap. A general sharp asymptotic or exact formula for $k(n,m)$ when both $n,m\ge3$.

(iii) Top 3 next moves.

1. Tighten the bridge to classical Ramsey numbers by making the Hunter inequalities fully rigorous in both directions.
2. For fixed $m$, attempt to prove matching upper/lower polynomial growth in $n$ (Erdős--Rado give $O(n^{m-1})$).
3. Run stronger computer search/sat-solving for small $(n,m)$ to guess exact values (e.g. $k(3,3)$).

(iv) Minimal counterexample structure. To refute a proposed upper bound for $k(n,m)$ one needs an explicit directed graph on that many vertices with independence number $<n$ and no transitive subtournament of size $m$; for $n=2$ this is exactly a transitive-subtournament-free tournament.