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

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Import240304020342 (talk | contribs)
Set profile property.
 
(3 intermediate revisions by 2 users not shown)
Property / reviewed by
 
Property / reviewed by: Ralph J. Faudree / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Ralph J. Faudree / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 04:37, 5 March 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