Asymptotic Tightness of the Pigeonhole Bound for Large-Order Davenport-Schinzel Sequences
We prove that the pigeonhole upper bound $λ(s,m) \leq \binom{m}{2}(s+1)$ is asymptotically tight whenever $s/\!\sqrt{m} \to \infty$. In particular, $λ(s,m) \sim \binom{m}{2}\,s$ in this regime. As corollaries: $λ(n,n)/n^3 \to \frac{1}{2}$, resolving the leading constant from the previously known interval $[\frac{1}{3}, \frac{1}{2}]$; and more generally $λ(an,bn) \sim \frac{ab^2}{2}\,n^3$ for any constants $a,b > 0$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.15375
curl -X POST /api/v1/records/arxiv/2602.15375/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.15375/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'