Splittability and 1-amalgamability of permutation classes

Kód výsledku v IS VaVaI

RIV/00216208:11320/17:10366863 - isvavai.cz

Výsledek na webu

https://dmtcs.episciences.org/4125

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Splittability and 1-amalgamability of permutation classes

Popis výsledku v původním jazyce

A permutation class CC is splittable if it is contained in a merge of two of its proper subclasses, and it is 1-amalgamable if given two permutations σ and τ in C, each with a marked element, we can find a permutation π in C containing both σ and τ such that the two marked elements coincide. It was previously shown that unsplittability implies 1-amalgamability. We prove that unsplittability and 1-amalgamability are not equivalent properties of permutation classes by showing that the class Av(1423,1342) . Av(1423,1342) is both splittable and 1-amalgamable. Our construction is based on the concept of LR-inflations, which we introduce here and which may be of independent interest.

Název v anglickém jazyce

Splittability and 1-amalgamability of permutation classes

Popis výsledku anglicky

A permutation class CC is splittable if it is contained in a merge of two of its proper subclasses, and it is 1-amalgamable if given two permutations σ and τ in C, each with a marked element, we can find a permutation π in C containing both σ and τ such that the two marked elements coincide. It was previously shown that unsplittability implies 1-amalgamability. We prove that unsplittability and 1-amalgamability are not equivalent properties of permutation classes by showing that the class Av(1423,1342) . Av(1423,1342) is both splittable and 1-amalgamable. Our construction is based on the concept of LR-inflations, which we introduce here and which may be of independent interest.

Druh

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

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

GJ16-01602Y: Topologické a geometrické přístupy k permutačním třídám a grafovým vlastnostem

Návaznosti

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

Rok uplatnění

2017

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

Discrete Mathematics and Theoretical Computer Science [online]

ISSN

1365-8050

e-ISSN

—

Svazek periodika

19

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

14

Strana od-do

—

Kód UT WoS článku

000423285900003

EID výsledku v databázi Scopus

2-s2.0-85040456225