Short cycles in random regular graphs (Q1773189): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q175582 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Ralph J. Faudree / rank | |||
Normal rank |
Revision as of 05:06, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Short cycles in random regular graphs |
scientific article |
Statements
Short cycles in random regular graphs (English)
0 references
25 April 2005
0 references
Consider random regular graphs of order \(n\) and degree \(d = d(n)\) with \(g = g(n)\) such that \((d - 1)^{2g-1} = o(n)\). It is shown that the number of cycles of lengths up to \(g\) has a distribution similar to independent Poisson variables. More specifically, let \(\{c_1, c_2, \dots, c_t\}\) be a subset of \(\{3, 4, \dots, g\}\) and define \( \mu_i = (d-1)^{c_i}/(2c_i)\) for \(3 \leq i \leq g\). It is shown that the probabilty that a random \(d\)-regular graph of order \(n\) has no cycles of length \(c_i\) for \(1 \leq i \leq t\) is \[ \exp\left(-\sum^t_{i=1} \mu_i + o(1) \right) \] as \(n \rightarrow \infty\).
0 references