The dimension of the feasible region of pattern densities

D 2023

The dimension of the feasible region of pattern densities

GARBE, Frederik, Daniel KRÁĽ, Alexandru MALEKSHAHIAN a Raul PENAGUIAO

Základní údaje

Originální název

The dimension of the feasible region of pattern densities

Autoři

GARBE, Frederik (276 Německo, domácí), Daniel KRÁĽ (203 Česká republika, garant, domácí), Alexandru MALEKSHAHIAN a Raul PENAGUIAO

Vydání

Brno, European Conference on Combinatorics, Graph Theory and Applications, od s. 471-477, 7 s. 2023

Nakladatel

MUNI Press

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/23:00133883

Organizační jednotka

Fakulta informatiky

ISSN

DOI

http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-065

Klíčová slova anglicky

permutations; permutation limits; patterns

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 22. 3. 2024 22:32, prof. RNDr. Daniel Kráľ, Ph.D., DSc.

Anotace

V originále

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.

Návaznosti

MUNI/I/1677/2018, interní kód MU

Název: MUNI AWARD in Science and Humanitites 1 (Akronym: MASH 1)

Investor: Masarykova univerzita, MUNI AWARD in Science and Humanitites 1, MASH - MUNI Award in Science and Humanities

Citovat

GARBE, Frederik, Daniel KRÁĽ, Alexandru MALEKSHAHIAN a 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, s. 471-477. ISSN 2788-3116. Dostupné z: https://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-065.

@inproceedings{2386887,
   author = {Garbe, Frederik and Kráľ, Daniel and Malekshahian, Alexandru and Penaguiao, Raul},
   address = {Brno},
   booktitle = {European Conference on Combinatorics, Graph Theory and Applications},
   doi = {http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-065},
   keywords = {permutations; permutation limits; patterns},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Brno},
   pages = {471-477},
   publisher = {MUNI Press},
   title = {The dimension of the feasible region of pattern densities},
   url = {https://journals.muni.cz/eurocomb/article/view/35599},
   year = {2023}
}

TY  - CONF
ID  - 2386887
AU  - Garbe, Frederik - Kráľ, Daniel - Malekshahian, Alexandru - Penaguiao, Raul
PY  - 2023
TI  - The dimension of the feasible region of pattern densities
PB  - MUNI Press
CY  - Brno
KW  - permutations
KW  - permutation limits
KW  - patterns
UR  - https://journals.muni.cz/eurocomb/article/view/35599
N2  - 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.
ER  -

GARBE, Frederik, Daniel KRÁĽ, Alexandru MALEKSHAHIAN a Raul PENAGUIAO. The dimension of the feasible region of pattern densities. Online. In \textit{European Conference on Combinatorics, Graph Theory and Applications}. Brno: MUNI Press, 2023, s.~471-477. ISSN~2788-3116. Dostupné z: https://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-065.

Podrobný výpis o publikaci