Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets

2008/04/04 by Raphael Yuster, Yuster, Raphael
Computer Science · Mathematics · #05C80 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.0804.0753

openalex publication_date 2008/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For every fixed graph H and every fixed 0 < α< 1, we show that if a graph G has the property that all subsets of size αn contain the ``correct'' number of copies of H one would expect to find in the random graph G(n,p) then G behaves like the random graph G(n,p); that is, it is p-quasi-random in the sense of Chung, Graham, and Wilson. This solves a conjecture raised by Shapira and solves in a strong sense an open problem of Simonovits and Sós.

Related

• The Effect of Induced Subgraphs on Quasi-Randomness
• Quasi-randomness of graph balanced cut properties
• More on quasi-random graphs, subgraph counts and graph limits
• Quasi-random oriented graphs
• The Quasi-Randomness of Hypergraph Cut Properties