First-order convergence for $321$-avoiding permutations
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917351936491520 |
|---|---|
| author | Özdemir, Alperen |
| author_facet | Özdemir, Alperen |
| contents | We say that a convergence law holds for a sequence of random combinatorial objects if, for any first-order sentence $φ$, the proportion of objects satisfying $φ$ converges to a limiting value as the size of the objects tends to infinity. In this paper, we show that the convergence law holds for random $321$-avoiding permutations, settling an open problem posed in Albert, Bouvel, Féray, and Noy (2024). Our proof relies on an infinite-dimensional version of the Perron-Frobenius theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_01749 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | First-order convergence for $321$-avoiding permutations Özdemir, Alperen Probability 60C05, 60G07, 03C13 We say that a convergence law holds for a sequence of random combinatorial objects if, for any first-order sentence $φ$, the proportion of objects satisfying $φ$ converges to a limiting value as the size of the objects tends to infinity. In this paper, we show that the convergence law holds for random $321$-avoiding permutations, settling an open problem posed in Albert, Bouvel, Féray, and Noy (2024). Our proof relies on an infinite-dimensional version of the Perron-Frobenius theorem. |
| title | First-order convergence for $321$-avoiding permutations |
| topic | Probability 60C05, 60G07, 03C13 |
| url | https://arxiv.org/abs/2312.01749 |