Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets (Q532131)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets |
scientific article |
Statements
Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets (English)
0 references
26 April 2011
0 references
A graph \(G(n)\) is \(p\)-quasi-random if it behaves like the random graph \(G(n,p)\) for sufficiently large \(n\) and any \(0<p<1\). It is proved that \(G(n)\) is \(p\)-quasi-random if, for every fixed graph \(H\) and every fixed proportion \(0<w<1\), the subgraph of \(G(n)\) induced by any vertex subset of size \(wn\) contains as many copies of \(H\) as would be expected in \(G(n,p)\).
0 references
random graph
0 references
pseudo-randomness
0 references
quasi-randomness
0 references
0 references