×

Quasi-randomness of graph balanced cut properties. (English) Zbl 1247.05219

Summary: Quasi-random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, A. Shapira and R. Yuster [ibid. 40, No. 1, 105–131 (2012; Zbl 1241.05105)] proved the following result on quasi-randomness of graphs. Let \(k \geq 2\) be a fixed integer, \(\alpha _{1},\ldots ,\alpha _{k}\) be positive reals satisfying \(\sum_{i}\alpha_{i}=1\) and \((\alpha _{1},\ldots ,\alpha _{k})\neq (1/k,\ldots ,1/k)\), and \(G\) be a graph on \(n\) vertices. If for every partition of the vertices of \(G\) into sets \(V_{1},\ldots,V_{k}\) of size \(\alpha _{1}n,\ldots ,\alpha _{k}n\), the number of complete graphs on \(k\) vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi-random. However, the method of quasi-random hypergraphs they used did not provide enough information to resolve the case \((1/k,\ldots,1/k)\) for graphs.
In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi-random. Janson also posed the same question in his study of quasi-randomness under the framework of graph limits. In this paper, we positively answer their question.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C65 Hypergraphs

Citations:

Zbl 1241.05105
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, The probabilistic method (2000) · doi:10.1002/0471722154
[2] Azuma, Weighted sums of certain dependent random variables, Tôkuku Math J 19 pp 357– (1967) · Zbl 0178.21103 · doi:10.2748/tmj/1178243286
[3] Chung, Quasi-random graphs, Combinatorica 9 pp 345– (1989) · Zbl 0715.05057 · doi:10.1007/BF02125347
[4] Chung, Quasi-random set systems, J Am Math Soc 4 pp 151– (1991) · Zbl 0761.05072 · doi:10.1090/S0894-0347-1991-1077279-1
[5] Chung, Quasi-random tournaments, J Graph Theory 15 pp 173– (1991) · Zbl 0728.05025 · doi:10.1002/jgt.3190150206
[6] Chung, Quasi-random hypergraphs, Random Struct Algorithm 1 pp 105– (1990) · Zbl 0708.05044 · doi:10.1002/rsa.3240010108
[7] F. R. K. Chung R. L. Graham Maximum cuts and quasi-random graphs Random Graphs, Vol. 2 A. Frieze T. Łuczak Wiley New York 1992 23 33
[8] Gottlieb, A class of incidence matrices, Proc Am Math Soc 17 pp 1233– (1966) · Zbl 0146.01302 · doi:10.1090/S0002-9939-1966-0204305-9
[9] Hajnal, Proof of a conjecture of Erdos, in Combinatorial Theory and Its Applications 2 pp 601– (1970)
[10] Hoeffding, Probability inequalities for sums of bounded random variables, J Am Stat Assoc 58 pp 13– (1963) · Zbl 0127.10602 · doi:10.1080/01621459.1963.10500830
[11] Janson, Quasi-random graphs and graph limits, Eur J Combin 32 pp 1054– (2011) · Zbl 1230.05262 · doi:10.1016/j.ejc.2011.03.011
[12] Komlós, Vol. 2, Bolyai Society Mathematical Studies, in: Combinatorics, Paul Erdos is eighty pp 295– (1996)
[13] M. Krivelevich B. Sudakov Pseudo-random graphs, in More Sets, Graphs and Numbers E. Gyori G. O. H. Katona L. Lovász 15 Bolyai society mathematical studies Springer, Berlin 2006 199 262
[14] McDiarmid, In Probabilistic methods for algorithmic discrete mathematics pp 1– (1998)
[15] Shapira, The quasi-randomness of hypergraph cut properties, Random Struct Algorithm · Zbl 1241.05105
[16] Simonovits, Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs, Combinatorica 17 pp 577– (1997) · Zbl 0906.05066 · doi:10.1007/BF01195005
[17] Szemerédi, Volume 260: Colloquium International CNRS pp 399– (1978)
[18] A. Thomason Pseudo-random graphs 1987 307 331
[19] A. Thomason Random graphs, strongly regular graphs and pseudo-random graphs Surveys in Combinatorics, LMS Lecture Note Series 123 In C. Whitehead 1987 173 195 · Zbl 0672.05068
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.