Quasirandom-Forcing Orientations of Cycles

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

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

Rok publikování 2023
Druh Článek v odborném periodiku
Časopis / Zdroj SIAM JOURNAL ON DISCRETE MATHEMATICS
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www https://epubs.siam.org/doi/full/10.1137/23M1548700
Doi http://dx.doi.org/10.1137/23M1548700
Klíčová slova quasirandomness; tournaments; cycles; quasirandom graphs; combinatorial limits
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info