×

Quasirandomness in hypergraphs. (English) Zbl 1395.05182

Summary: An \(n\)-vertex graph \(G\) of edge density \(p\) is considered to be quasirandom if it shares several important properties with the random graph \(G(n,p)\). A well-known theorem of F. R. K. Chung et al. [Combinatorica 9, No. 4, 345–362 (1989; Zbl 0715.05057)] states that many such ‘typical’ properties are asymptotically equivalent and, thus, a graph \(G\) possessing one such property automatically satisfies the others.
In recent years, work in this area has focused on uncovering more quasirandom graph properties and on extending the known resulty to other discrete structures. In the context of hypergraphs, however, one may consider several different notions of quasirandomness. A complete description of these notions has been provided recently by H. Towsner [Random Struct. Algorithms 50, No. 1, 114–139 (2017; Zbl 1352.05168)], who proved several central equivalences using an analytic framework. We give short and purely combinatorial proofs of the main equivalences in Towsner’s result [loc. cit.].

MSC:

05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
05C65 Hypergraphs
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] Alon, N., Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1984. · Zbl 0661.05053
[2] Alon, N. and Chung, F. R. K., Explicit construction of linear sized tolerant networks, Discrete Math., Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), 72(1-3):15–19,1988.
[3] Chung, F. R. K., Quasi-random classes of hypergraphs, Random Structures & Algorithms, 1(4):363–382, 1990. · Zbl 0739.05066
[4] Chung, F. R. K., Quasi-random hypergraphs, Random Structures & Algorithms, 1(4): 363–382, 1990. · Zbl 0739.05066
[5] Chung, F. R. K., Regularity lemmas for hypergraphs and quasi-randomness, Random Structures & Algorithms, 2(2):241–252,1991. · Zbl 0756.05081
[6] Chung, F. R. K. and Graham, R. L., Quasi-random hypergraphs, Random Structures & Algorithms, 1(1):105–124, 1990. · Zbl 0708.05044
[7] Chung, F. R. K. and Graham, R. L., Quasi-random set systems, J. Amer. Math. Soc., 1: 151–196, 1991. · Zbl 0761.05072
[8] Chung, F. R. K. and Graham, R. L., Quasi-random tournaments, J. Graph Theory, 15(2):173–198, 1991. · Zbl 0728.05025
[9] Chung, F. R. K. and Graham, R. L., Quasi-random subsets of Zn, J. Combin. Theory Ser. A, 61(1):64–86, 1992. · Zbl 0779.05046
[10] Chung, F. R. K. and Graham, R. L. and Wilson, R. M., Quasi-random graphs, Combinatorica, 9(4):345–362, 1989. · Zbl 0715.05057
[11] Conlon, D. and H‘an, H. and Person, Y. and, Schacht, M., Weak quasi-randomness for uniform hypergraphs, Random Structures & Algorithms, 40(1):1–38, 2012. · Zbl 1236.05137
[12] D. Conlon and J. Lee, Finite reflection groups and graph norms, Adv. Math., 315:130– 165, 2017. · Zbl 1366.05107
[13] Frankl, P. and R¨odl, V. and Wilson, R. M., The number of submatrices of a given type in a Hadamard matrix and related results, J. Combin. Theory Ser. B, 44(3):317328,1988. · Zbl 0658.05015
[14] Frankl, P. and R¨odl, V. The uniformity lemma for hypergraphs, Graphs Combin., 8(4): 309–312, 1992. · Zbl 0777.05084
[15] Gowers, W. T., Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combin. Probab. Comput., 15(1–2): 143–184, 2006. · Zbl 1082.05081
[16] Gowers, W. T., Quasirandom groups, Combin. Probab. Comput., 17(3):363-387, 2008. · Zbl 1191.20016
[17] Haviland, J. and Thomason, A., Pseudo-random hypergraphs, Discrete Math., 75(1-3):255-278, 1989. the electronic journal of combinatorics 25(3) (2018), #P3.3420 · Zbl 0800.05009
[18] Huang, H. and Lee, C., Quasi-randomness of graph balanced cut properties, Random Structures & Algorithms, 41(1):124–145, 2012. · Zbl 1247.05219
[19] Janson, S., Quasi-random graphs and graph limits, European J. Combin., 32(7):1054– 1083, 2011. · Zbl 1230.05262
[20] Janson, S. and Luczak, T. and Ruci´nski, A., Random graphs, Wiley-Interscience, New York, xii+333, 2000.
[21] Kohayakawa, Y. and R¨odl, V. and Skokan, J., Quasi-randomness, hypergraphs, and conditions for regularity, J. Combin. Theory Ser. A, 97(2):307–352, 2002. · Zbl 0990.05111
[22] Kohayakawa, Y. and Nagle, B. and R¨odl, V. and Schacht, M., Weak hypergraph regularity and linear hypergraphs, J. Combin. Theory Ser. B, 100(2):151–160, 2010. · Zbl 1216.05094
[23] Koml´os, J. and Shokoufandeh, A. and Simonovits, M. and Szemer´edi, E., The regularity lemma and its applications in graph theory, Theoretical aspects of computer science (Tehran, 2000), Lecture Notes in Comput. Sci., 2292:84–112, Springer, 2002.
[24] Krivelevich, M. and Sudakov, B., Pseudo-random graphs, More sets, graphs and numbers, Bolyai Soc. Math. Stud., 15: 199–262, Springer, 2006. · Zbl 1098.05075
[25] Lenz, J. and Mubayi, D., Eigenvalues and linear quasirandom hypergraphs, Forum Math. Sigma, 3:e2, 26 pp., 2015. · Zbl 1306.05144
[26] Lenz, J. and Mubayi, D., The poset of hypergraph quasirandomness, Random Structures & Algorithms, 46(4):762–800, 2015. · Zbl 1328.05172
[27] Lenz, J. and Mubayi, D., Eigenvalues of Non-Regular Linear-Quasirandom Hypergraphs, Discrete Math., 340(2):145–153, 2017. · Zbl 1351.05143
[28] Lov´asz, L. and S´os, V. T., Generalized quasirandom graphs, J. Combin. Theory Ser. B, 98(1):146–163, 2008.
[29] Nagle, B. and Poerschke, A. and R¨odl, V. and Schacht, M., Hypergraph regularity and quasi-randomness, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (C. Mathieu, ed.), ACM, pp. 227–235, 2009.
[30] Reiher, C. and Schacht, M., Forcing quasirandomness with triangles, submitted.
[31] R¨odl, V., On universality of graphs with uniformly distributed edges, Discrete Math., 59(1-2):125–134, 1986. · Zbl 0619.05035
[32] Shapira, A., Quasi-randomness and the distribution of copies of a fixed graph, Combinatorica, 28(6):735–745, 2008. · Zbl 1196.05090
[33] Shapira, A. and Yuster, R., The effect of induced subgraphs on quasi-randomness, Random Structures & Algorithms, 36(1):90–109, 2010. · Zbl 1209.05230
[34] Simonovits, M. and S´os, V. T., Szemer´edi’s partition and quasirandomness, Random Structures & Algorithms, 2(1):1–10, 1991.
[35] Simonovits, M. and S´os, V. T., Hereditarily Extended Properties, Quasi-Random Graphs and Induced Subgraphs, Combin. Probab. Comput., 12(3):319–344, 2003. the electronic journal of combinatorics 25(3) (2018), #P3.3421 · Zbl 1043.05107
[36] Skokan, J. and Thoma, L., Bipartite Subgraphs and Quasi-Randomness, Graphs Combin., 20(2):255–262, 2004. · Zbl 1054.05091
[37] Steger, A., Die Kleitman–Rothschild Methode, Ph.D. thesis, 1990, Forschungsinstitut f¨ur Diskrete Mathematik, Rheinische Friedrich–Wilhelms–Universit¨at Bonn.
[38] Thomason, A., Random graphs, strongly regular graphs and pseudorandom graphs, Surveys in combinatorics 1987 (New Cross, 1987), London Math. Soc. Lecture Note Ser., 123:173–195, Cambridge Univ. Press, 1987.
[39] Thomason, A., Pseudorandom graphs, Random graphs ’85 (Pozna´n, 1985), 144:307– 331, North-Holland Math. Stud., 1987.
[40] Towsner, H., σ-algebras for quasirandom hypergraphs, Random Structures Algorithms, 50(1):114–139, 2017. · Zbl 1352.05168
[41] Vadhan, S. P., Pseudorandomness, Found. Trends Theor. Comput. Sci., World Scientific, Singapore; Now Publishers, Delft, 7(1-3):1–338,2011. · Zbl 1308.68011
[42] Yuster, R., Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets, Combinatorica, 30(2):239–246, 2010. · Zbl 1224.05476
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.