Related problems ::.
On this page you can find some problems and theories related to the conjecture. An exciting theory which is not needed for the conjecture, but which is interesting to look at is considering the process of generating a random graph as a process in time. We can look at this process in discrete time, and consider the process Qt where, on a fixed amount of vertices, in every step one random edge is added to the graph. One can wonder about things such as 'what is the expected time at which a random graph is connected?', or something more related to the conjecture 'how much time does it take before a random graph contains a d-cube?'. For those interested in such things, the book 'Random Graphs' by Béla Bollobás contains a lot of information on this. It is a very advanced book though, so some previous study is recommended.
The Evolution of Random Subgraphs of the Cube ::.
Abstract: Let (Qt)0M be a random Qn-process, that is let Q0 be the empty spanning subraph of the cube Qn and, for 1 ≤ t ≤ M = nN/2=n2n-1, let the graph Qt be obtained from Qt-1 by the random addition of an edge of Qn not present in Qt-1. When t is about N/2, a typical Qt undergoes a certain 'phase transition': the component structure changes in a sudden and surprising way. Let t = (1+ε)N/2 where ε is independent of n. Then all the components of a typical Qt have o(N) vertices if ε<0, while if ε>0 then a typical Qt has a 'giant' component with at least α(ε)N vertices, where α(ε)>0. In this note the essentially best possible results are given concerning the emergence of this giant component close to the time of phase transistion.
Some more information on phase transition can also be found in A whirlwind tour of random graphs by Fan Chung.