TOPICS
Search

Quasirandom Graph


A quasirandom graph sequence is a sequence of finite simple graphs whose asymptotic subgraph counts have the values predicted by a random graph. More precisely, (G_n) with v_n=|V(G_n)|->infty is p-quasirandom if, for every fixed finite simple graph F with m vertices and e edges, the number of labeled injective copies of F is p^ev_n^m+o(v_n^m). The copies need not be induced subgraphs. Here 0<p<=1 is fixed, and o denotes little-O notation.

The Janson-Sós conjecture characterizes this property using a single graph F and counts restricted to balanced disjoint vertex classes (Wang et al. 2026).


See also

Janson-Sós Conjecture, Random Graph

Explore with Wolfram|Alpha

References

Chung, F. R. K.; Graham, R. L.; and Wilson, R. M. "Quasi-Random Graphs." Combinatorica 9, 345-362, 1989. https://doi.org/10.1007/BF02125347.Wang, G.; Wang, L.; and Yue, J. "Balanced Subgraph Counts and Quasirandomness: A Proof of the Janson-Sós Conjecture." 20 Oct 2026. https://arxiv.org/abs/2610.28124.

Cite this as:

Weisstein, Eric W. "Quasirandom Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/QuasirandomGraph.html

Subject classifications