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

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\).