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 \underset{n\to \mathrm{\infty }}{\lim }\text{ex}(n,P)\mathrm{/}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\le 2.88c_P^2$. In this note we improve the constants in Cibulka’s result through a so-called ``block contraction" argument. Defining $$F(c)=\underset{t\in \mathbb{N}}{\inf }\frac{(t!{)}^{1\mathrm{/}t}{15}^{c\mathrm{/}t}}{c},$$ for $c>0$, this leads us to the revised inequality $s_P\le F(c_P)c_P^2$. In particular, $F(c)=\log 15+o(1)\approx 2.70805\dots +o(1)$ as $c\to \mathrm{\infty }$, and the constant improves $2.88$ once $c_P\ge 17$.