On the maximum density of a matrix and a transcendental Turán-type density
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914269451255808 |
|---|---|
| author | Yuster, Raphael |
| author_facet | Yuster, Raphael |
| contents | We prove that the inducibility of $P_4$ in ordered monotone balanced bipartite graphs is $2/e^2$, establishing the smallest known graph with transcendental Turán-type density. Moreover, the limit object is a binary graphon, so it generates a deterministic model. This is a special case of a more general framework addressed here -- the asymptotic maximum density of a constant matrix over an arbitrary symbol set, in a large, possibly monotone, matrix. We solve all $2 \times 2$ monotone cases (one of which corresponds to the aforementioned $P_4$) and all but one of the $2 \times 2$ unrestricted cases.
While $(h!/h^h)^2$ is a lower bound for the asymptotic maximum density of an $h \times h$ matrix, we explicitly construct, for all $h \ge 1$, an $h \times h$ minimizer, i.e., a matrix for which this bound is attained. We also sketch how known results on the inducibility of graphs can be modified to show that, as $h$ grows, almost all $h \times h$ $0/1$ matrices are minimizers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_14904 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the maximum density of a matrix and a transcendental Turán-type density Yuster, Raphael Combinatorics 05C35 We prove that the inducibility of $P_4$ in ordered monotone balanced bipartite graphs is $2/e^2$, establishing the smallest known graph with transcendental Turán-type density. Moreover, the limit object is a binary graphon, so it generates a deterministic model. This is a special case of a more general framework addressed here -- the asymptotic maximum density of a constant matrix over an arbitrary symbol set, in a large, possibly monotone, matrix. We solve all $2 \times 2$ monotone cases (one of which corresponds to the aforementioned $P_4$) and all but one of the $2 \times 2$ unrestricted cases. While $(h!/h^h)^2$ is a lower bound for the asymptotic maximum density of an $h \times h$ matrix, we explicitly construct, for all $h \ge 1$, an $h \times h$ minimizer, i.e., a matrix for which this bound is attained. We also sketch how known results on the inducibility of graphs can be modified to show that, as $h$ grows, almost all $h \times h$ $0/1$ matrices are minimizers. |
| title | On the maximum density of a matrix and a transcendental Turán-type density |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2601.14904 |