|
For some constant ''c'', almost every labelled graph with ''n'' vertices and at least ''cn''log(''n'') edges is [[Hamiltonian cycle|Hamiltonian]]. With the probability tending to 1, the particular edge that increases the minimum degree to 2 makes the graph Hamiltonian.
== Triangles in Random Graphs ==
Given a random graph ''G(n,p<sub>n</sub>)''. If <math>p_{n}</math> ≪ <math>1/n</math>, then almost every ''G(n,p<sub>n</sub>)'' dose not contain a triangle. If <math>p_{n}</math> ≫ <math>1/n</math>, then almost every ''G(n,p<sub>n</sub>)'' contains a triangle.
We called ''r(n)=1/n'' the threshold function of the property that ''G(n,p<sub>n</sub>)'' contains a triangle.
===The proof===
Let ''X(G)'' be the number of triangles in ''G''. Let the set <math>{T_{1}, {T_{2}}, ..., {T_{{n \choose 3}}}}</math> be all possible triangles in G and let <math>X_{i}(G)</math> be a random variable such that <math>X_{i}(G)</math>=1 if ''G'' contains the triangle <math>T_{i}</math>, or <math>X_{i}(G)</math>=0 otherwise.
Note that
:#<math>X = \sum_{i} X_{i}</math>
:#<math>X_{i}</math> and <math>X_{j}</math> are independent if <math>\left |VT_{i} \cap VT_{j}\right |</math> ≤ 1.
When <math>p_{n}</math> ≪ <math>1/n</math>, then
:<math>Pr(X \ge 1) \le E(X) = {n \choose 3}p_{n}^{3} \le (\frac{p_{n}}{1/n})^{3} \to 0</math>, as <math>n \to \infty</math>.
When <math>p_{n}</math> ≫ <math>1/n</math>, then
:<math>\begin{align}
Pr(X=0) &\le Pr(|X-E(X)| \ge E(X)) \\
&\le \frac{Var(X)}{E(X)^2} \ \ (by\ Chebyshev's\ inequality) \\
&= \left [ \sum_{i}Var(X_{i}) + \sum_{|VT_{j} \cap VT_{k}|=2}Cov(X_{j},X_{k}) \right ] / E(X)^2 \\
&\le \left [ \sum_{i}E(X_{i}) + \sum_{|VT_{j} \cap VT_{k}|=2}E(X_{j}X_{k}) \right ] / EX(X)^2 \\
&= \frac{{n \choose 3}p_{n}^3 + 2{n \choose 4}{4 \choose 2}p_{n}^5}{{n \choose 3}^{2}p_{n}^6} \\
&\le \left (\frac{1/n}{p_{n}}\right )^3 + 18\left (\frac{1/n}{p_n}\right )\left (\frac{n-3}{(n-1)(n-2)}\right ) \\
&\to 0, \ as \ n \to \infty
\end{align}</math>
== Coloring of Random Graphs ==
| 