## Abstract

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, α _{1},...,α _{k} be positive reals satisfying ∑ _{i}α _{i} = 1 and (α _{1},...,α _{k})≠(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 α _{1}n,...,α _{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,...,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.

Original language | English (US) |
---|---|

Pages (from-to) | 124-145 |

Number of pages | 22 |

Journal | Random Structures and Algorithms |

Volume | 41 |

Issue number | 1 |

DOIs | |

State | Published - Aug 1 2012 |

## Keywords

- Cut properties
- Pseudo-random graphs
- Quasi-random graphs