Improved Bounds for Unavoidable Claws in Tournaments
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 $θ$ and $σ$ which place the lower- and upper-bound arguments in a common framework: we show $σ\leθ$ and $1/21\leσ\leθ\le1/5$, our two bounds being the images of the endpoints under…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.06073
curl -X POST /api/v1/records/arxiv/2608.06073/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.06073/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'