Density maximizers of layered permutations

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F22%3A43966287" target="_blank" >RIV/49777513:23520/22:43966287 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216224:14330/22:00127928

Výsledek na webu

<a href="https://doi.org/10.37236/10781" target="_blank" >https://doi.org/10.37236/10781</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.37236/10781" target="_blank" >10.37236/10781</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Density maximizers of layered permutations

Popis výsledku v původním jazyce

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, Holtonand 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 &gt; 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ázev v anglickém jazyce

Density maximizers of layered permutations

Popis výsledku anglicky

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, Holtonand 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 &gt; 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA20-09525S" target="_blank" >GA20-09525S: Strukturální vlastnosti tříd grafů charakterizovaných zakázanými podgrafy</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ELECTRONIC JOURNAL OF COMBINATORICS

ISSN

1077-8926

e-ISSN

1077-8926

Svazek periodika

29

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

23

Strana od-do

nestrankovano

Kód UT WoS článku

000913376700001

EID výsledku v databázi Scopus

2-s2.0-85137349290