A Conjecture on Spanning Cubes in Random Graphs ::.

[ Home] [History] [Background] [Special cases] [ Related problems]

About this webpage ::.

The goal of this page is to analyse an open problem in graph theory. It is part of a course of the Radboud University in Nijmegen, the Netherlands. The idea is to create a collection of useful references that will help to understand the problem. I will try to summarize the information in these references on this page. The problem I will deal with is a conjecture proposed by Paul Erdös and Béla Bollobás.

The conjecture::.

A random graph on n = 2d vertices with edge density ½ contains a d-cube.

For information on the history of random graphs and the persons behind the conjecture, as well as some background theory and definitions needed to understand the conjecture, a page on special cases of the conjecture which have been proved and a few links to related problems, click on the buttons on the top right of this page.