On a Quadratic Relation Between Stanley-Wilf Limits and Füredi-Hajnal Limits
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914338940387328 |
|---|---|
| author | Omar, Mohamed |
| author_facet | Omar, Mohamed |
| contents | 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}} \frac{(t!)^{1/t}\,15^{\,c/t}}{c}, \] for $c>0$, this leads us to the revised inequality $s_P\leq F(c_P)\,c_P^2$. In particular, $F(c)=\log 15+o(1) \approx 2.70805\ldots +o(1)$ as $c\to\infty$, and the constant improves $2.88$ once $c_P \geq 17$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_17401 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On a Quadratic Relation Between Stanley-Wilf Limits and Füredi-Hajnal Limits Omar, Mohamed Combinatorics 05A05, 05D05 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}} \frac{(t!)^{1/t}\,15^{\,c/t}}{c}, \] for $c>0$, this leads us to the revised inequality $s_P\leq F(c_P)\,c_P^2$. In particular, $F(c)=\log 15+o(1) \approx 2.70805\ldots +o(1)$ as $c\to\infty$, and the constant improves $2.88$ once $c_P \geq 17$. |
| title | On a Quadratic Relation Between Stanley-Wilf Limits and Füredi-Hajnal Limits |
| topic | Combinatorics 05A05, 05D05 |
| url | https://arxiv.org/abs/2602.17401 |