Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets (Q532131): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
| Property / review text | |||
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)\). | |||
| Property / review text: 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)\). / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 05C80 / rank | |||
Normal rank | |||
| Property / zbMATH DE Number | |||
| Property / zbMATH DE Number: 5881227 / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
random graph | |||
| Property / zbMATH Keywords: random graph / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
pseudo-randomness | |||
| Property / zbMATH Keywords: pseudo-randomness / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
quasi-randomness | |||
| Property / zbMATH Keywords: quasi-randomness / rank | |||
Normal rank | |||
Revision as of 09:06, 1 July 2023
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
