Quasirandom-Forcing Orientations of Cycles

J 2023

Quasirandom-Forcing Orientations of Cycles

GRZESIK, Andrzej; Daniel IĽKOVIČ; Bartłomiej KIELAK a Daniel KRÁĽ

Základní údaje

Originální název

Quasirandom-Forcing Orientations of Cycles

Autoři

GRZESIK, Andrzej; Daniel IĽKOVIČ; Bartłomiej KIELAK a Daniel KRÁĽ

Vydání

SIAM JOURNAL ON DISCRETE MATHEMATICS, UNITED STATES, SIAM PUBLICATIONS, 2023, 0895-4801

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Spojené státy

Utajení

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

Odkazy

URL

Impakt faktor

Impact factor: 0.900

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/23:00132240

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

quasirandomness; tournaments; cycles; quasirandom graphs; combinatorial limits

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 8. 4. 2024 16:25, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

An oriented graph H is quasirandom-forcing if the limit (homomorphism) density of H in a sequence of tournaments is 2|H| if and only if the sequence is quasirandom. We study generalizations of the following result: the cyclic orientation of a cycle of length l is quasirandom-forcing if and only if l ≡ 2 mod 4. We show that no orientation of an odd cycle is quasirandom-forcing. In the case of even cycles, we find sufficient conditions on an orientation to be quasirandom-forcing, which we complement by identifying necessary conditions. Using our general results and spectral techniques used to obtain them, we classify which orientations of cycles of length up to 10 are quasirandom-forcing.

Návaznosti

MUNI/A/1081/2022, interní kód MU

Název: Modelování, analýza a verifikace (2023)

Investor: Masarykova univerzita, Modelování, analýza a verifikace (2023)

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

GRZESIK, Andrzej; Daniel IĽKOVIČ; Bartłomiej KIELAK a Daniel KRÁĽ. Quasirandom-Forcing Orientations of Cycles. SIAM JOURNAL ON DISCRETE MATHEMATICS. UNITED STATES: SIAM PUBLICATIONS, 2023, roč. 37, č. 4, s. 2689-2716. ISSN 0895-4801. Dostupné z: https://doi.org/10.1137/23M1548700.

@article{2339297,
   author = {Grzesik, Andrzej and Iľkovič, Daniel and Kielak, Bartłomiej and Kráľ, Daniel},
   article_location = {UNITED STATES},
   article_number = {4},
   doi = {https://doi.org/10.1137/23M1548700},
   keywords = {quasirandomness; tournaments; cycles; quasirandom graphs; combinatorial limits},
   language = {eng},
   issn = {0895-4801},
   journal = {SIAM JOURNAL ON DISCRETE MATHEMATICS},
   title = {Quasirandom-Forcing Orientations of Cycles},
   url = {https://epubs.siam.org/doi/full/10.1137/23M1548700},
   volume = {37},
   year = {2023}
}

TY  - JOUR
ID  - 2339297
AU  - Grzesik, Andrzej - Iľkovič, Daniel - Kielak, Bartłomiej - Kráľ, Daniel
PY  - 2023
TI  - Quasirandom-Forcing Orientations of Cycles
JF  - SIAM JOURNAL ON DISCRETE MATHEMATICS
VL  - 37
IS  - 4
SP  - 2689-2716
EP  - 2689-2716
PB  - SIAM PUBLICATIONS
SN  - 08954801
KW  - quasirandomness
KW  - tournaments
KW  - cycles
KW  - quasirandom graphs
KW  - combinatorial limits
UR  - https://epubs.siam.org/doi/full/10.1137/23M1548700
N2  - An oriented graph H is quasirandom-forcing if the limit (homomorphism) density of H in a sequence of tournaments is 2|H| if and only if the sequence is quasirandom. We study generalizations of the following result: the cyclic orientation of a cycle of length l is quasirandom-forcing if and only if l ≡ 2 mod 4. We show that no orientation of an odd cycle is quasirandom-forcing. In the case of even cycles, we find sufficient conditions on an orientation to be quasirandom-forcing, which we complement by identifying necessary conditions. Using our general results and spectral techniques used to obtain them, we classify which orientations of cycles of length up to 10 are quasirandom-forcing.
ER  -

GRZESIK, Andrzej; Daniel IĽKOVIČ; Bartłomiej KIELAK a Daniel KRÁĽ. Quasirandom-Forcing Orientations of Cycles. \textit{SIAM JOURNAL ON DISCRETE MATHEMATICS}. UNITED STATES: SIAM PUBLICATIONS, 2023, roč.~37, č.~4, s.~2689-2716. ISSN~0895-4801. Dostupné z: https://doi.org/10.1137/23M1548700.

Přehled o publikaci