On a Quadratic Relation Between Stanley-Wilf Limits and Füredi-Hajnal Limits
For a permutation matrix $P$, let $s_P$ denote its Stanley-Wilf limit, the exponential growth rate of the number of $n\times n$ permutation matrices avoiding $P$. Let $c_P$ denote its Füredi-Hajnal limit, which is the limit $\displaystyle \lim_{n \to \infty} \text{ex}(n,P)/n$ where $\text{ex}(n,P)$ is the maximum number of ones in an $n\times n$ $0$-$1$ matrix avoiding $P$. Cibulka proved the universal quadratic bound $s_P\leq 2.88\,c_P^2$. In this note we improve the constants in Cibulka's result through a so-called ``block contraction" argument. Defining \[ F(c)=\inf_{t\in\mathbb{N}}…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.17401
curl -X POST /api/v1/records/arxiv/2602.17401/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.17401/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'