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}}=\limsup_{n\to\infty}u(n)/n$. In 1998, Lu, Wang and Wong proved that $19/50\le c_{\mathrm{claw}}\le11/23$, and these have remained the best bounds known. We improve them to $2/5\le c_{\mathrm{claw}}\le10/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\le1/5$, our two bounds being the images of the endpoints under $\alpha\mapsto\frac12-\frac{\alpha}{2}$, and $\sigma=\theta$ would force $\lim u(n)/n$ to exist.