Forcing Generalized Quasirandom Graphs Efficiently

EUROCOMB’23

Abstract
We study generalized quasirandom graphs whose vertex set consists of $q$ parts (of not necessarily the same sizes) with edges within each part and between each pair of parts distributed quasirandomly; such graphs correspond to the stochastic block model studied in statistics and network science. Lovász and Sós showed that the structure of such graphs is forced by homomorphism densities of graphs with at most $(10q)^q+q$ vertices; subsequently, Lovász refined the argument to show that graphs with $4(2q+3)^8$ vertices suffice. Our results imply that the structure of generalized quasirandom graphs with $q\ge 2$ parts is forced by homomorphism densities of graphs with at most $4q^2-q$ vertices, and, if vertices in distinct parts have distinct degrees, then $2q+1$ vertices suffice. The latter improves the bound of $8q-4$ due to Spencer.

Pages:
503–510
References

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.

Metrics

0

Views

0

PDF views