A logical limit law for $231$-avoiding permutations
We prove that the class of 231-avoiding permutations satisfies a logical limit law, i.e. that for any first-order sentence $\Psi$, in the language of two total orders, the probability $p_{n,\Psi}$ that a uniform random 231-avoiding permutation of size $n$ satisfies $\Psi$ admits a limit as $n$ is la...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2024-04-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/11751/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850056410703855616 |
|---|---|
| author | Michael Albert Mathilde Bouvel Valentin Féray Marc Noy |
| author_facet | Michael Albert Mathilde Bouvel Valentin Féray Marc Noy |
| author_sort | Michael Albert |
| collection | DOAJ |
| description | We prove that the class of 231-avoiding permutations satisfies a logical limit law, i.e. that for any first-order sentence $\Psi$, in the language of two total orders, the probability $p_{n,\Psi}$ that a uniform random 231-avoiding permutation of size $n$ satisfies $\Psi$ admits a limit as $n$ is large. Moreover, we establish two further results about the behavior and value of $p_{n,\Psi}$: (i) it is either bounded away from $0$, or decays exponentially fast; (ii) the set of possible limits is dense in $[0,1]$. Our tools come mainly from analytic combinatorics and singularity analysis. |
| format | Article |
| id | doaj-art-c09d86b2f6804c109f24bfcaf7ad2df1 |
| institution | DOAJ |
| issn | 1365-8050 |
| language | English |
| publishDate | 2024-04-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-c09d86b2f6804c109f24bfcaf7ad2df12025-08-20T02:51:42ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502024-04-01vol. 26:1, Permutation...Special issues10.46298/dmtcs.1175111751A logical limit law for $231$-avoiding permutationsMichael AlbertMathilde BouvelValentin FérayMarc NoyWe prove that the class of 231-avoiding permutations satisfies a logical limit law, i.e. that for any first-order sentence $\Psi$, in the language of two total orders, the probability $p_{n,\Psi}$ that a uniform random 231-avoiding permutation of size $n$ satisfies $\Psi$ admits a limit as $n$ is large. Moreover, we establish two further results about the behavior and value of $p_{n,\Psi}$: (i) it is either bounded away from $0$, or decays exponentially fast; (ii) the set of possible limits is dense in $[0,1]$. Our tools come mainly from analytic combinatorics and singularity analysis.http://dmtcs.episciences.org/11751/pdfmathematics - combinatoricsmathematics - probability05a16, 60c05 (primary), 03c13 (secondary) |
| spellingShingle | Michael Albert Mathilde Bouvel Valentin Féray Marc Noy A logical limit law for $231$-avoiding permutations Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics mathematics - probability 05a16, 60c05 (primary), 03c13 (secondary) |
| title | A logical limit law for $231$-avoiding permutations |
| title_full | A logical limit law for $231$-avoiding permutations |
| title_fullStr | A logical limit law for $231$-avoiding permutations |
| title_full_unstemmed | A logical limit law for $231$-avoiding permutations |
| title_short | A logical limit law for $231$-avoiding permutations |
| title_sort | logical limit law for 231 avoiding permutations |
| topic | mathematics - combinatorics mathematics - probability 05a16, 60c05 (primary), 03c13 (secondary) |
| url | http://dmtcs.episciences.org/11751/pdf |
| work_keys_str_mv | AT michaelalbert alogicallimitlawfor231avoidingpermutations AT mathildebouvel alogicallimitlawfor231avoidingpermutations AT valentinferay alogicallimitlawfor231avoidingpermutations AT marcnoy alogicallimitlawfor231avoidingpermutations AT michaelalbert logicallimitlawfor231avoidingpermutations AT mathildebouvel logicallimitlawfor231avoidingpermutations AT valentinferay logicallimitlawfor231avoidingpermutations AT marcnoy logicallimitlawfor231avoidingpermutations |