Forcing Quasirandomness in a Regular Tournament

Noel, Jonathan A.; Ranganathan, Arjun; Simbaqueba, Lina M.

doi:10.5802/igt.20

Noel, Jonathan A.¹; Ranganathan, Arjun ²; Simbaqueba, Lina M.¹

¹University of Victoria, Department of Mathematics and Statistics, 3800 Finnerty Road., Victoria, B.C., Canada
²University College London, Department of Mathematics, Gower Street, London WC1E 6BT

Innovations in Graph Theory, Volume 3 (2026), pp. 127-169

Abstract

A tournament $H$ is said to force quasirandomness if it has the property that a sequence $(T_n)_{n\in \mathbb{N}}$ of tournaments of increasing orders is quasirandom if and only if the homomorphism density of $H$ in $T_n$ tends to $(1/2)^{\binom{v(H)}{2}}$ as $n\rightarrow \infty $. It was recently shown that there is only one non-transitive tournament with this property. This is in contrast to the analogous problem for graphs, where there are numerous graphs that are known to force quasirandomness and the well known Forcing Conjecture suggests that there are many more. To obtain a richer family of characterizations of quasirandomness in tournaments, we propose a variant in which the tournaments $(T_n)_{n\in \mathbb{N}}$ are assumed to be “nearly regular.” We characterize the tournaments on at most 5 vertices which force quasirandomness under this stronger assumption.

Received: 2025-01-20
Accepted: 2026-01-12
Published online: 2026-04-02

DOI: 10.5802/igt.20

Classification: 05C50, 05C20
Keywords: Quasirandomness, regular tournament, combinatorial limit.

Author's affiliations:

Noel, Jonathan A. ¹ ; Ranganathan, Arjun ² ; Simbaqueba, Lina M. ¹

¹ University of Victoria, Department of Mathematics and Statistics, 3800 Finnerty Road., Victoria, B.C., Canada
² University College London, Department of Mathematics, Gower Street, London WC1E 6BT

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{IGT_2026__3__127_0,
     author = { Noel, Jonathan A. and Ranganathan, Arjun and Simbaqueba, Lina M.},
     title = {Forcing {Quasirandomness} in a {Regular} {Tournament}},
     journal = {Innovations in Graph Theory},
     pages = {127--169},
     year = {2026},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {3},
     doi = {10.5802/igt.20},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.20/}
}

TY  - JOUR
AU  -  Noel, Jonathan A.
AU  - Ranganathan, Arjun
AU  - Simbaqueba, Lina M.
TI  - Forcing Quasirandomness in a Regular Tournament
JO  - Innovations in Graph Theory
PY  - 2026
SP  - 127
EP  - 169
VL  - 3
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.20/
DO  - 10.5802/igt.20
LA  - en
ID  - IGT_2026__3__127_0
ER  -

%0 Journal Article
%A  Noel, Jonathan A.
%A Ranganathan, Arjun
%A Simbaqueba, Lina M.
%T Forcing Quasirandomness in a Regular Tournament
%J Innovations in Graph Theory
%D 2026
%P 127-169
%V 3
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.20/
%R 10.5802/igt.20
%G en
%F IGT_2026__3__127_0

 Noel, Jonathan A.; Ranganathan, Arjun; Simbaqueba, Lina M. Forcing Quasirandomness in a Regular Tournament. Innovations in Graph Theory, Volume 3 (2026), pp. 127-169. doi: 10.5802/igt.20

References
Cited by

[1] Alon, N.; Spencer, J. H. The probabilistic method, Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, 2016 | Zbl | MR

[2] Bucić, M.; Long, E.; Shapira, A.; Sudakov, B. Tournament quasirandomness from local counting, Combinatorica, Volume 41 (2021) no. 2, pp. 175-208 | Zbl | DOI | MR

[3] Burke, D.; Lidický, B.; Pfender, F.; Philips, M. Inducibility of 4-vertex tournaments (2022) | arXiv | Zbl

[4] Chan, T. F. N.; Grzesik, A.; Král’, D.; Noel, J. A. Cycles of length three and four in tournaments, J. Comb. Theory, Ser. A, Volume 175 (2020), Paper no. 105276, 23 pages | DOI | MR | Zbl

[5] Chan, T. F. N.; Král’, D.; Noel, J. A.; Pehova, Y.; Sharifzadeh, M.; Volec, J. Characterization of quasirandom permutations by a pattern sum, Random Struct. Algorithms, Volume 57 (2020) no. 4, pp. 920-939 | DOI | MR | Zbl

[6] Chung, F. From quasirandom graphs to graph limits and graphlets, Adv. Appl. Math., Volume 56 (2014), pp. 135-174 | Zbl | MR | DOI

[7] Chung, F. R. K.; Graham, R. L. Quasi-random hypergraphs, Random Struct. Algorithms, Volume 1 (1990) no. 1, pp. 105-124 | DOI | Zbl | MR

[8] Chung, F. R. K.; Graham, R. L. Quasi-random set systems, J. Am. Math. Soc., Volume 4 (1991) no. 1, pp. 151-196 | DOI | Zbl | MR

[9] Chung, F. R. K.; Graham, R. L. Quasi-random tournaments, J. Graph Theory, Volume 15 (1991) no. 2, pp. 173-198 | DOI | Zbl | MR

[10] Chung, F. R. K.; Graham, R. L.; Wilson, R. M. Quasi-random graphs, Combinatorica, Volume 9 (1989) no. 4, pp. 345-362 | DOI | Zbl | MR

[11] Conlon, D.; Fox, J.; Sudakov, B. An approximate version of Sidorenko’s conjecture, Geom. Funct. Anal., Volume 20 (2010) no. 6, pp. 1354-1366 | DOI | Zbl | MR

[12] Conlon, D.; Fox, J.; Sudakov, B. Hereditary quasirandomness without regularity, Math. Proc. Camb. Philos. Soc., Volume 164 (2018) no. 3, pp. 385-399 | DOI | MR | Zbl

[13] Conlon, D.; Hàn, H.; Person, Y.; Schacht, M. Weak quasi-randomness for uniform hypergraphs, Random Struct. Algorithms, Volume 40 (2012) no. 1, pp. 1-38 | DOI | Zbl | MR

[14] Cooper, J. N. Quasirandom permutations, J. Comb. Theory, Ser. A, Volume 106 (2004) no. 1, pp. 123-143 | DOI | Zbl | MR

[15] Cooper, J. W.; Král’, D.; Lamaison, A.; Mohr, S. Quasirandom Latin squares, Random Struct. Algorithms, Volume 61 (2022) no. 2, pp. 298-308 | DOI | MR | Zbl

[16] Coregliano, L. N.; Parente, R F.; Sato, C M. On the maximum density of fixed strongly connected subtournaments, Electron. J. Comb., Volume 26 (2019) no. 1, Paper no. 1.44, 48 pages | DOI | MR | Zbl

[17] Coregliano, L. N.; Razborov, A. A. On the density of transitive tournaments, J. Graph Theory, Volume 85 (2017) no. 1, pp. 12-21 | DOI | MR | Zbl

[18] Coregliano, L. N.; Razborov, A. A. Natural quasirandomness properties, Random Struct. Algorithms, Volume 63 (2023) no. 3, pp. 624-688 | DOI | MR | Zbl

[19] Crudele, G.; Dukes, P.; Noel, J. A. Six Permutation Patterns Force Quasirandomness (2023) (to appear in Discrete Anal.) | arXiv

[20] Dellamonica, D. Jr.; Rödl, V. Hereditary quasirandom properties of hypergraphs, Combinatorica, Volume 31 (2011) no. 2, pp. 165-182 | DOI | MR | Zbl

[21] Gowers, W. T. Quasirandomness, counting and regularity for 3-uniform hypergraphs, Comb. Probab. Comput., Volume 15 (2006) no. 1-2, pp. 143-184 | DOI | MR | Zbl

[22] Gowers, W. T. Quasirandom groups, Comb. Probab. Comput., Volume 17 (2008) no. 3, pp. 363-387 | DOI | MR | Zbl

[23] Griffiths, S. Quasi-random oriented graphs, J. Graph Theory, Volume 74 (2013) no. 2, pp. 198-209 | DOI | MR | Zbl

[24] Grzesik, A.; Il’kovič, D.; Kielak, B.; Král’, D. Quasirandom-forcing orientations of cycles, SIAM J. Discrete Math., Volume 37 (2023) no. 4, pp. 2689-2716 | MR | DOI | Zbl

[25] Grzesik, A.; Král’, D.; Lovász, L.; Volec, J. Cycles of a given length in tournaments, J. Comb. Theory, Ser. B, Volume 158 (2023), pp. 117-145 | DOI | MR | Zbl

[26] Grzesik, A.; Král’, D.; Pikhurko, O. Forcing generalised quasirandom graphs efficiently, Comb. Probab. Comput., Volume 33 (2024) no. 1, pp. 16-31 | DOI | MR | Zbl

[27] Hancock, R.; Kabela, A.; Král’, D.; Martins, T.; Parente, R.; Skerman, F.; Volec, J. No additional tournaments are quasirandom-forcing, Eur. J. Comb., Volume 108 (2023), Paper no. 103632, 10 pages | MR | DOI

[28] Kalyanasundaram, S.; Shapira, A. A note on even cycles and quasirandom tournaments, J. Graph Theory, Volume 73 (2013) no. 3, pp. 260-266 | DOI | MR | Zbl

[29] Kendall, M. G.; Babington Smith, B. On the method of paired comparisons, Biometrika, Volume 31 (1940), pp. 324-345 | DOI | MR | Zbl

[30] Kohayakawa, Y.; Rödl, V.; Skokan, J. Hypergraphs, quasi-randomness, and conditions for regularity, J. Comb. Theory, Ser. A, Volume 97 (2002) no. 2, pp. 307-352 | DOI | MR | Zbl

[31] Král’, D.; Lee, J.-B.; Noel, J. A. Forcing quasirandomness with 4-point permutations (2024) | arXiv | Zbl

[32] Král’, D.; Pikhurko, O. Quasirandom permutations are characterized by 4-point densities, Geom. Funct. Anal., Volume 23 (2013) no. 2, pp. 570-579 | DOI | MR | Zbl

[33] Kurečka, M. Lower bound on the size of a quasirandom forcing set of permutations, Comb. Probab. Comput., Volume 31 (2022) no. 2, pp. 304-319 | DOI | MR | Zbl

[34] Linial, N.; Morgenstern, A. On the number of 4-cycles in a tournament, J. Graph Theory, Volume 83 (2016) no. 3, pp. 266-276 | DOI | MR | Zbl

[35] Lovász, L. Combinatorial problems and exercises, North-Holland, 1979, 551 pages | MR | Zbl

[36] Lovász, L. Large networks and graph limits, Colloquium Publications, 60, American Mathematical Society, 2012 | MR | Zbl | DOI

[37] Lovász, L.; Sós, V. T. Generalized quasirandom graphs, J. Comb. Theory, Ser. B, Volume 98 (2008) no. 1, pp. 146-163 | DOI | MR | Zbl

[38] Lovász, L.; Szegedy, B. Limits of dense graph sequences, J. Comb. Theory, Ser. B, Volume 96 (2006) no. 6, pp. 933-957 | DOI | MR | Zbl

[39] Ma, J.; Tang, T. Minimizing cycles in tournaments and normalized $q$ -norms, Comb. Theory, Volume 2 (2022) no. 3, Paper no. 6, 19 pages | DOI | MR | Zbl

[40] Moss, E.; Noel, J. A. Off-Diagonal Ramsey Multiplicity (2023) | arXiv

[41] Razborov, A. A. Flag algebras, J. Symb. Log., Volume 72 (2007) no. 4, pp. 1239-1282 | DOI | MR | Zbl

[42] Rödl, V. On universality of graphs with uniformly distributed edges, Discrete Math., Volume 59 (1986) no. 1-2, pp. 125-134 | DOI | MR | Zbl

[43] Sah, A.; Sawhney, M. The intransitive dice kernel: $\frac{1_{x \geq y} - 1_{x \leq y}}{4} - \frac{3 (x - y) (1 + x y)}{8}$ (2023) | arXiv | Zbl

[44] Skokan, J.; Thoma, L. Bipartite subgraphs and quasi-randomness, Graphs Comb., Volume 20 (2004) no. 2, pp. 255-262 | DOI | MR | Zbl

[45] Thomason, A. Pseudorandom graphs, Random graphs ’85 (Poznań, 1985) (North-Holland Mathematics Studies), Volume 144, North-Holland, 1987, pp. 307-331 | Zbl | MR

[46] Thomason, A. Random graphs, strongly regular graphs and pseudorandom graphs, Surveys in combinatorics 1987 (New Cross, 1987) (London Mathematical Society Lecture Note Series), Volume 123, Cambridge University Press, 1987, pp. 173-195 | MR | Zbl

[47] Thörnblad, E. Decomposition of tournament limits, Eur. J. Comb., Volume 67 (2018), pp. 96-125 | DOI | MR | Zbl

[48] Zhao, Y.; Zhou, Y. Impartial digraphs, Combinatorica, Volume 40 (2020) no. 6, pp. 875-896 | Zbl | DOI | MR

Cited by Sources: