Forcing Generalized Quasirandom Graphs Efficiently
EUROCOMB’23
503–510
C. Borgs, J. Chayes and L. Lovász: Moments of two-variable functions and the uniqueness of graph limits, Geom. Funct. Anal. 19 (2010), 1597-1619.
https://doi.org/10.1007/s00039-010-0044-0
C. Borgs, J. T. Chayes, H. Cohn and S. Ganguly: Consistent nonparametric estimation for heavy-tailed sparse graphs, Ann. Statist. 49 (2021), 1904-1930.
https://doi.org/10.1214/20-AOS1985
M. Bucić, E. Long, A. Shapira and B. Sudakov: Tournament quasirandomness from local counting, Combinatorica 41 (2021), 175-208.
https://doi.org/10.1007/s00493-020-4371-y
T. Chan, D. Král', J. A. Noel, Y. Pehova, M. Sharifzadeh and J. Volec: Characterization of quasirandom permutations by a pattern sum, Random Structures & Algorithms 57 (2020), 920-939.
https://doi.org/10.1002/rsa.20956
F. R. K. Chung and R. L. Graham: Quasi-random hypergraphs, Random Structures & Algorithms 1 (1990), 105-124.
https://doi.org/10.1002/rsa.3240010108
F. R. K. Chung and R. L. Graham: Quasi-random set systems, Journal of the American Mathematical Society 4 (1991), 151-196.
https://doi.org/10.1090/S0894-0347-1991-1077279-1
F. R. K. Chung and R. L. Graham: Quasi-random tournaments, Journal of Graph Theory 15 (1991), 173-198.
https://doi.org/10.1002/jgt.3190150206
F. R. K. Chung and R. L. Graham: Quasi-random subsets of Zn, Journal of Combinatorial Theory, Series A 61 (1992), 64-86.
https://doi.org/10.1016/0097-3165(92)90053-W
F. R. K. Chung, R. L. Graham and R. M. Wilson: Quasi-random graphs, Combinatorica 9 (1989), 345-362.
https://doi.org/10.1007/BF02125347
J. N. Cooper: Quasirandom permutations, Journal of Combinatorial Theory, Series A 106 (2004), 123-143.
https://doi.org/10.1016/j.jcta.2004.01.006
J. W. Cooper, D. Král', A. Lamaison and S. Mohr: Quasirandom Latin squares, Random Structures & Algorithms 61 (2022), 298-308.
https://doi.org/10.1002/rsa.21060
J. W. Cooper, D. Král' and T. Martins: Finitely forcible graph limits are universal, Adv. Math. 340 (2018), 819-854
https://doi.org/10.1016/j.aim.2018.10.019
L. N. Coregliano, R. F. Parente and C. M. Sato: On the maximum density of fixed strongly connected subtournaments, The Electronic Journal of Combinatorics 26 (2019), P1.44.
https://doi.org/10.37236/6557
L. N. Coregliano and A. A. Razborov: On the density of transitive tournaments, Journal of Graph Theory 85 (2017), 12-21.
https://doi.org/10.1002/jgt.22044
L. N. Coregliano and A. A. Razborov: Natural quasirandomness properties, preprint arXiv:2012.11773 (2020).
P. Diaconis and S. Janson: Graph limits and exchangeable random graphs, Rend. Mat. Appl. 28 (2008), 33-61.
S. Eberhard, F. Manners and R. Mrazović: Transversals in quasirandom Latin squares, preprint arXiv:2209.02180 (2022).
https://doi.org/10.1112/plms.12538
P. Erdős, L. Lovász and J. Spencer: Strong independence of graphcopy functions, Graph theory and related topics (1979), 165-172.
C. Gao, Y. Lu and H. H. Zhou: Rate-optimal graphon estimation, Ann. Statist. 43 (2015), 2624-2652.
https://doi.org/10.1214/15-AOS1354
F. Garbe, R. Hancock, J. Hladký and M. Sharifzadeh: Limits of Latin squares, preprint arXiv:2010.07854 (2020).
R. Glebov, A. Grzesik, T. Klimošová and D. Král': Finitely forcible graphons and permutons, J. Combin. Theory Ser. B 110 (2015), 112-135.
https://doi.org/10.1016/j.jctb.2014.07.007
W. T. Gowers: Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combinatorics, Probability and Computing 15 (2006), 143-184.
https://doi.org/10.1017/S0963548305007236
W. T. Gowers: Hypergraph regularity and the multidimensional Szemerédi theorem, Annals of Mathematics, Second Series 166 (2007), 897-946.
https://doi.org/10.4007/annals.2007.166.897
W. T. Gowers: Quasirandom groups, Combinatorics, Probability and Computing 17(2008), 363-387.
https://doi.org/10.1017/S0963548307008826
W. T. Gowers and J. Long: Partial associativity and rough approximate groups, Geometric and Functional Analysis 30 (2020), 1-65.
https://doi.org/10.1007/s00039-020-00553-1
A. Grzesik, D. Il'kovič, B. Kielak and D. Král': Quasirandom forcing orientations of cycles, preprint arXiv:2212.09343 (2022).
R. Hancock, A. Kabela, D. Král', T. Martins, R. Parente, F. Skerman and J. Volec: No additional tournaments are quasirandom-forcing, European Journal of Combinatorics 108 (2023), 103632.
https://doi.org/10.1016/j.ejc.2022.103632
J. Haviland and A. Thomason: Pseudo-random hypergraphs, Discrete Math. 75 (1989), 255-278.
https://doi.org/10.1016/0012-365X(89)90093-9
O. Klopp, A. B. Tsybakov and N. Verzelen: Oracle inequalities for network models and sparse graphon estimation, Ann. Statist. 45 (2017), 316-354.
https://doi.org/10.1214/16-AOS1454
O. Klopp and N. Verzelen: Optimal graphon estimation in cut distance, Probab. Theory Related Fields 174 (2019), 1033-1090.
https://doi.org/10.1007/s00440-018-0878-1
Y. Kohayakawa, V. Rödl and J. Skokan: Hypergraphs, quasi-randomness, and conditions for regularity, Journal of Combinatorial Theory, Series A 97 (2002), 307-352.
https://doi.org/10.1006/jcta.2001.3217
D. Král' and O. Pikhurko: Quasirandom permutations are characterized by 4-point densities, Geometric and Functional Analysis 23 (2013), 570-579.
https://doi.org/10.1007/s00039-013-0216-9
M. Kurečka: Lower bound on the size of a quasirandom forcing set of permutations, Combinatorics, Probability and Computing 31 (2022), 304-319.
https://doi.org/10.1017/S0963548321000298
L. Lovász: Large Networks and Graph Limits, Colloquium Publications, volume 60, 2012.
https://doi.org/10.1090/coll/060
L. Lovász and V. Sós: Generalized quasirandom graphs, J. Combin. Theory Ser. B 98 (2008), 146-163.
https://doi.org/10.1016/j.jctb.2007.06.005
L. Lovász and B. Szegedy: Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), 933-957.
https://doi.org/10.1016/j.jctb.2006.05.002
B. Nagle, V. Rödl and M. Schaht: The counting lemma for regular k-uniform hypergraphs, Random Structures & Algorithms 28 (2006), 113-179.
https://doi.org/10.1002/rsa.20117
V. Rödl: On universality of graphs with uniformly distributed edges, Discrete Mathematics 59 (1986), 125-134.
https://doi.org/10.1016/0012-365X(86)90076-2
V. Rödl and J. Skokan: Regularity lemma fork-uniform hypergraphs, Random Structures & Algorithms 25 (2004), 1-42.
https://doi.org/10.1002/rsa.20017
M. Simonovits and V. T. Sós: Szemerédi's partition and quasirandomness, Random Structures & Algorithms 2 (1991), 1-10.
https://doi.org/10.1002/rsa.3240020102
J. Spencer: Quasirandom multitype graphs, in: An irregular mind, Bolyai Soc. Math. Stud., volume 21 (2010), 607-617.
https://doi.org/10.1007/978-3-642-14444-8_18
A. Thomason: Pseudo-random graphs, Annals of Discrete Mathematics 144 (1987), 307-331.
https://doi.org/10.1016/S0304-0208(08)73063-9
A. Thomason: Random graphs, strongly regular graphs and pseudo-random graphs, in: Surveys in Combinatorics, London Mathematical Society Lecture Note Series, volume 123 (1987), 173-196.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Andrzej Grzesik, Daniel Kráľ, Oleg Pikhurko