Density maximizers of layered permutations

J 2022

Density maximizers of layered permutations

KABELA, Adam, Daniel KRÁĽ, Jon Andrew NOEL a Théo PIERRON

Základní údaje

Originální název

Density maximizers of layered permutations

Autoři

KABELA, Adam, Daniel KRÁĽ (203 Česká republika, garant, domácí), Jon Andrew NOEL a Théo PIERRON (250 Francie, domácí)

Vydání

Electronic Journal of Combinatorics, 2022, 1077-8926

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Austrálie

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.700

Kód RIV

RIV/00216224:14330/22:00127928

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.37236/10781

UT WoS

000913376700001

Klíčová slova anglicky

permutations; layered permutations

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 5. 4. 2023 03:32, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

A permutation is layered if it contains neither 231 nor 312 as a pattern. It is known that, if σ is a layered permutation, then the density of σ in a permutation of order n is maximized by a layered permutation. Albert, Atkinson, Handley, Holton and Stromquist [Electron. J. Combin. 9 (2002), #R5] claimed that the density of a layered permutation with layers of sizes (a, 1, b) where a, b > 2 is asymptotically maximized by layered permutations with a bounded number of layers, and conjectured that the same holds if a layered permutation has no consecutive layers of size one and its first and last layers are of size at least two. We show that, if σ is a layered permutation whose first layer is sufficiently large and second layer is of size one, then the number of layers tends to infinity in every sequence of layered permutations asymptotically maximizing the density of σ. This disproves the conjecture and the claim of Albert et al. We complement this result by giving sufficient conditions on a layered permutation to have asymptotic or exact maximizers with a bounded number of layers.

Návaznosti

MUNI/I/1677/2018, interní kód MU

Název: MUNI AWARD in Science and Humanitites 1 (Akronym: MASH 1)

Investor: Masarykova univerzita, MUNI AWARD in Science and Humanitites 1, MASH - MUNI Award in Science and Humanities

Citovat

KABELA, Adam, Daniel KRÁĽ, Jon Andrew NOEL a Théo PIERRON. Density maximizers of layered permutations. Electronic Journal of Combinatorics. 2022, roč. 29, č. 3, s. 1-21. ISSN 1077-8926. Dostupné z: https://dx.doi.org/10.37236/10781.

@article{2245922,
   author = {Kabela, Adam and Kráľ, Daniel and Noel, Jon Andrew and Pierron, Théo},
   article_number = {3},
   doi = {http://dx.doi.org/10.37236/10781},
   keywords = {permutations; layered permutations},
   language = {eng},
   issn = {1077-8926},
   journal = {Electronic Journal of Combinatorics},
   title = {Density maximizers of layered permutations},
   url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v29i3p56},
   volume = {29},
   year = {2022}
}

TY  - JOUR
ID  - 2245922
AU  - Kabela, Adam - Kráľ, Daniel - Noel, Jon Andrew - Pierron, Théo
PY  - 2022
TI  - Density maximizers of layered permutations
JF  - Electronic Journal of Combinatorics
VL  - 29
IS  - 3
SP  - 1-21
EP  - 1-21
SN  - 10778926
KW  - permutations
KW  - layered permutations
UR  - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v29i3p56
N2  - A permutation is layered if it contains neither 231 nor 312 as a pattern. It is known that, if σ is a layered permutation, then the density of σ in a permutation of order n is maximized by a layered permutation. Albert, Atkinson, Handley, Holton and Stromquist [Electron. J. Combin. 9 (2002), #R5] claimed that the density of a layered permutation with layers of sizes (a, 1, b) where a, b > 2 is asymptotically maximized by layered permutations with a bounded number of layers, and conjectured that the same holds if a layered permutation has no consecutive layers of size one and its first and last layers are of size at least two. We show that, if σ is a layered permutation whose first layer is sufficiently large and second layer is of size one, then the number of layers tends to infinity in every sequence of layered permutations asymptotically maximizing the density of σ. This disproves the conjecture and the claim of Albert et al. We complement this result by giving sufficient conditions on a layered permutation to have asymptotic or exact maximizers with a bounded number of layers.
ER  -

KABELA, Adam, Daniel KRÁĽ, Jon Andrew NOEL a Théo PIERRON. Density maximizers of layered permutations. \textit{Electronic Journal of Combinatorics}. 2022, roč.~29, č.~3, s.~1-21. ISSN~1077-8926. Dostupné z: https://dx.doi.org/10.37236/10781.

Podrobný výpis o publikaci