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
    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
    0 references
    random graph
    0 references
    pseudo-randomness
    0 references
    quasi-randomness
    0 references
    0 references
    0 references