Quasi-randomness of graph balanced cut properties
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, Shapira and Yuster proved the following result on quasi-randomness of graphs. Let k = 2 be a fixed integer, a1,...,ak be positive reals satisfying \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document} \begin{align*}\sum_{i} \alpha_i = 1\end{align*} \end{document} and (a1,....,ak)?(1/k,....,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V 1,....,V k of size a1n,...,akn, 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,....,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. (C) 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011
cut properties quasi-random graphs pseudo-random graphs