Random graphs contain cubes
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
A conjecture on a spanning cube in a random graph
(proposed by
Erdös and Bollobás)
A random graph on \(n = 2^d\) vertices with edge density \(\frac{1}{2}\) contains an \(d\)-cube. }
A random graph on \(n = 2^d\) vertices with edge density \(\frac{1}{2}\) contains an \(d\)-cube. }
Alon and Füredi \( ^{[1]}\) showed that this conjecture is true if the random graph has edge density \( p > \frac{1}{2}\) for \( n\) large enough (as a function of \( p\)).
In 2000, Riordin proved the conjecture \( ^{[3]}\), showing that it holds whenever \( p>\frac14\). Furthermore, he shows that the number of \( d\)-cubes in \( G(n,M)\) is asymptotically normally distributed for \( M\) in a certain range. The proof uses the second moment method, and much of the work is in estimating the various terms in the resulting sum.
Bibliography | |
---|---|
1 | N. Alon and Z. Füredi, Spanning subgraphs of random graphs, Graphs and Combinatorics 8 (1992), 91-94. |
2 | P. Erdös, Some recent combinatorial problems, Technical Report, University of Bielefeld, Nov. 1990. |
3 | O Riordan. Spanning subgraphs of random graphs. Combin. Probab. Comput. 9 (2000), no. 2, 125-148. |