The dimension of the feasible region of pattern densities

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

GARBE Frederik KRÁĽ Daniel MALEKSHAHIAN Alexandru PENAGUIAO Raul

Year of publication 2023
Type Article in Proceedings
Conference European Conference on Combinatorics, Graph Theory and Applications
MU Faculty or unit

Faculty of Informatics

Citation
Web https://journals.muni.cz/eurocomb/article/view/35599
Doi http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-065
Keywords permutations; permutation limits; patterns
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.