Short cycles in random regular graphs (Q1773189): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: reviewed by (P1447): Item:Q175582
RedirectionBot (talk | contribs)
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
    0 references
    0 references
    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

    Identifiers