Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets (Q532131): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 0804.0753 / rank | |||
Normal rank |
Revision as of 15:51, 18 April 2024
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