The dimension of the feasible region of pattern densities

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00140916" target="_blank" >RIV/00216224:14330/25:00140916 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1017/S0305004124000380" target="_blank" >https://doi.org/10.1017/S0305004124000380</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1017/S0305004124000380" target="_blank" >10.1017/S0305004124000380</a>

Jazyk výsledku

angličtina

Název v původním jazyce

The dimension of the feasible region of pattern densities

Popis výsledku v původním jazyce

A classical result of Erd &amp; odblac;s, Lov &amp; aacute;sz and Spencer from the late 1970s asserts that the dimension of the feasible region of densities of graphs with at most k vertices in large graphs is equal to the number of non-trivial connected graphs with at most k vertices. Indecomposable permutations play the role of connected graphs in the realm of permutations, and Glebov et al. showed that pattern densities of indecomposable permutations are independent, i.e., the dimension of the feasible region of densities of permutation patterns of size at most k is at least the number of non-trivial indecomposable permutations of size at most k. However, this lower bound is not tight already for $k=3$ . We prove that the dimension of the feasible region of densities of permutation patterns of size at most k is equal to the number of non-trivial Lyndon permutations of size at most k. The proof exploits an interplay between algebra and combinatorics inherent to the study of Lyndon words.

Název v anglickém jazyce

The dimension of the feasible region of pattern densities

Popis výsledku anglicky

A classical result of Erd &amp; odblac;s, Lov &amp; aacute;sz and Spencer from the late 1970s asserts that the dimension of the feasible region of densities of graphs with at most k vertices in large graphs is equal to the number of non-trivial connected graphs with at most k vertices. Indecomposable permutations play the role of connected graphs in the realm of permutations, and Glebov et al. showed that pattern densities of indecomposable permutations are independent, i.e., the dimension of the feasible region of densities of permutation patterns of size at most k is at least the number of non-trivial indecomposable permutations of size at most k. However, this lower bound is not tight already for $k=3$ . We prove that the dimension of the feasible region of densities of permutation patterns of size at most k is equal to the number of non-trivial Lyndon permutations of size at most k. The proof exploits an interplay between algebra and combinatorics inherent to the study of Lyndon words.

Druh

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

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

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

Mathematical Proceedings of the Cambridge Philosophical Society

ISSN

0305-0041

e-ISSN

1469-8064

Svazek periodika

178

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

14

Strana od-do

1-14

Kód UT WoS článku

001392537600001

EID výsledku v databázi Scopus

2-s2.0-105003497147