asymptotic_approximations [Tradejack]

- Asymptotic Approximations

Asymptotic Approximations

As $n \rightarrow \infty$ , baby.

Exp simplifications

$(1 + \frac1q)^m \le exp(\fracmq)$

Binomial coefficients

$\left(\frac{n}{k}\right)^k \leq {n \choose k} \leq \frac{n^k}{k!} \leq \left(\frac{n e}{k}\right)^k$

Random graphs

Let G be a graph with v vertices and e edges. In $\mbox{\mathbb{G}}(n,p)$ we expect to see $\mbox{\Theta}(n^v p^e)$ instances of G.

Random regular graphs

Let G be a graph with v vertices and e edges. A similar result similar to that for random graphs applies: in any regular (multi)graph we expect to see G approximately $\mbox{O}(n^{v-e})$ times.

Number of labelled d-regular graphs: $\sqrt{2} e^{-(d^2-1)/4} (r^{r/2} e^{-r/2} / r!)^n n^{rn/2}$