GARBE, Frederik, Daniel KRÁĽ, Alexandru MALEKSHAHIAN and Raul PENAGUIAO. The dimension of the feasible region of pattern densities. Online. In European Conference on Combinatorics, Graph Theory and Applications. Brno: MUNI Press, 2023, p. 471-477. ISSN 2788-3116. Available from: https://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-065.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name The dimension of the feasible region of pattern densities
Authors GARBE, Frederik (276 Germany, belonging to the institution), Daniel KRÁĽ (203 Czech Republic, guarantor, belonging to the institution), Alexandru MALEKSHAHIAN and Raul PENAGUIAO.
Edition Brno, European Conference on Combinatorics, Graph Theory and Applications, p. 471-477, 7 pp. 2023.
Publisher MUNI Press
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10101 Pure mathematics
Country of publisher Czech Republic
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW URL
RIV identification code RIV/00216224:14330/23:00133883
Organization unit Faculty of Informatics
ISSN 2788-3116
Doi http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-065
Keywords in English permutations; permutation limits; patterns
Tags International impact, Reviewed
Changed by Changed by: prof. RNDr. Daniel Kráľ, Ph.D., DSc., učo 44742. Changed: 22/3/2024 22:32.
Abstract
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.
Links
MUNI/I/1677/2018, interní kód MUName: MUNI AWARD in Science and Humanitites 1 (Acronym: MASH 1)
Investor: Masaryk University, MASH - MUNI Award in Science and Humanities
PrintDisplayed: 19/7/2024 01:42