The dimension of the feasible region of pattern densities

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

GARBE Frederik KRÁĽ Daniel MALEKSHAHIAN Alexandru PENAGUIAO Raul

Rok publikování 2023
Druh Článek ve sborníku
Konference European Conference on Combinatorics, Graph Theory and Applications
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www https://journals.muni.cz/eurocomb/article/view/35599
Doi http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-065
Klíčová slova permutations; permutation limits; patterns
Popis A classical result of Erdős, Lovász and Spencer from the late 1970s asserts that the dimension of the feasible region of homomorphic densities of graphs with at most k vertices in large graphs is equal to the number of connected graphs with at most k vertices. Glebov et al. showed that pattern densities of indecomposable permutations are independent, i.e., the dimension of the feasible region of densities of k-patterns is at least the number of non-trivial indecomposable permutations of size at most k. We identify a larger set of permutations, which are called Lyndon permutations, whose pattern densities are independent, and show that the dimension of the feasible region of densities of k-patterns is equal to the number of non-trivial Lyndon permutations of size at most k.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.