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%2F23%3A00133883" target="_blank" >RIV/00216224:14330/23:00133883 - isvavai.cz</a>
Result on the web
<a href="https://journals.muni.cz/eurocomb/article/view/35599" target="_blank" >https://journals.muni.cz/eurocomb/article/view/35599</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-065" target="_blank" >10.5817/CZ.MUNI.EUROCOMB23-065</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ő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.
Czech name
—
Czech description
—

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

Article name in the collection
European Conference on Combinatorics, Graph Theory and Applications
ISBN
—
ISSN
2788-3116
e-ISSN
—
Number of pages
7
Pages from-to
471-477
Publisher name
MUNI Press
Place of publication
Brno
Event location
Praha
Event date
Jan 1, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)