The size Ramsey number of a directed path

NEW

Problem: In Ben-Eliezer–Krivelevich–Sudakov’s terminology, a directed graph $G=(V,E)$ is $k$-pseudorandom if for every two disjoint sets $A,B\subseteq V$ with $|A|,|B|\ge k$, there is an edge directed from $A$ to $B$. The literal question asks whether some absolute $c>0$ guarantees that every red-blue coloring of every $k$-pseudorandom directed graph on $n$ vertices has a monochromatic directed path of length at least $c n/\sqrt{k}$. There is a possible stronger “tournament” interpretation, but the paper’s Definition 4.1 allows missing edges, so I resolve that literal formulation.

Result: The literal statement is false.

For large $k$, set

$$s=\lfloor k/2\rfloor,\qquad r=\lfloor 2^{k/16}\rfloor,\qquad n=rs.$$

Partition $V$ into $r$ parts $V_1,\dots,V_r$, each of size $s$. Put no edges inside parts. Between every two vertices in different parts, orient the edge independently uniformly at random.

For fixed disjoint $A,B$ of size $k$, write $a_i=|A\cap V_i|$, $b_i=|B\cap V_i|$. The number $m$ of cross-part pairs in $A\times B$ is

$$m=k^2-\sum_i a_i b_i.$$

Since $a_i+b_i\le s$,

$$a_i b_i\le \frac{s}{4}(a_i+b_i),$$

so

$$\sum_i a_i b_i\le \frac{s}{4}\sum_i(a_i+b_i)=\frac{sk}{2}\le \frac{k^2}{4}.$$

Thus $m\ge 3k^2/4$. Hence the probability that there is no edge from $A$ to $B$ is at most $2^{-3k^2/4}$. Union-bounding over at most $\binom nk^2\le (en/k)^{2k}$ ordered pairs gives probability at most

$$(en/k)^{2k}2^{-3k^2/4} \le (e2^{k/16})^{2k}2^{-3k^2/4}<1$$

for all sufficiently large $k$. Therefore some such oriented graph is $k$-pseudorandom.

Now color every edge from $V_i$ to $V_j$ red if $i<j$, and blue if $i>j$. Along a red directed path the part index strictly increases; along a blue directed path it strictly decreases. Therefore every monochromatic directed path has length at most $r-1$. But

$$\frac{r}{n/\sqrt{k}}=\frac{\sqrt{k}}{s}\to 0.$$

So these colorings have no monochromatic directed path of length $\Omega(n/\sqrt{k})$.

The failure comes from the absence of a tournament/completeness assumption: independent parts of size $<k$ are invisible to the $k$-pseudorandomness condition.

Citation: Definition and problem: Ido Ben-Eliezer, Michael Krivelevich, Benny Sudakov, “The size Ramsey number of a directed path,” arXiv:1005.5171, Definition 4.1 and Section 5. No resolving citation used; the counterexample above is given here.