Improved Bounds for Unavoidable Claws in Tournaments

Abstract

Let $u(n)$ be the largest integer $d$ such that every $n$-vertex claw with at most $d$ branches occurs in every tournament on $n$ vertices, and let $c_{\mathrm{claw}}={\mathrm{limsup}}_{n\to \infty }u(n)/n$. In 1998, Lu, Wang and Wong proved that $19/50\le c_{\mathrm{claw}}\le 11/23$, and these have remained the best bounds known. We improve them to $2/5\le c_{\mathrm{claw}}\le 10/21$. We also isolate two parameters $\theta$ and $\sigma$ which place the lower- and upper-bound arguments in a common framework: we show $\sigma \le \theta$ and $1/21\le \sigma \le \theta \le 1/5$, our two bounds being the images of the endpoints under $\alpha \mapsto \frac{1}{2}-\frac{\alpha }{2}$, and $\sigma =\theta$ would force $\lim u(n)/n$ to exist.