Quasirandom-Forcing Orientations of Cycles

• 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
• 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

• MUNI AWARD in Science and Humanitites 1
• Modelování, analýza a verifikace (2023)