The dimension of the feasible region of pattern densities

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

The dimension of the feasible region of pattern densities

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10200 - Computer and information sciences

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2025

Confidentiality

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

Name of the periodical

Mathematical Proceedings of the Cambridge Philosophical Society

ISSN

0305-0041

e-ISSN

1469-8064

Volume of the periodical

178

Issue of the periodical within the volume

1

Country of publishing house

US - UNITED STATES

Number of pages

14

Pages from-to

1-14

UT code for WoS article

001392537600001

EID of the result in the Scopus database

2-s2.0-105003497147