Quasirandom-Forcing Orientations of Cycles

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

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

Year of publication 2023
Type Article in Periodical
Magazine / Source SIAM JOURNAL ON DISCRETE MATHEMATICS
MU Faculty or unit

Faculty of Informatics

Citation
Web https://epubs.siam.org/doi/full/10.1137/23M1548700
Doi http://dx.doi.org/10.1137/23M1548700
Keywords quasirandomness; tournaments; cycles; quasirandom graphs; combinatorial limits
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info