A Conjecture on Spanning Cubes in Random Graphs ::.

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

The conjecture ::.

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

Background theory and definitions ::.

Here you will find some basic theory on random graphs and spanning cubes which you might need for understanding the conjecture and the work that has been done around it.

On random graphs::.

Definition of a random graph:
There are two ways to define a random graph. It was introduced by Erdös and Rényi in the following form:

Definition 1: A random graph G(n, M) is a graph chosen uniformly at random from the collection of all graphs which have n nodes and M edges.

Another way to define a random graph is as follows:

Definition 2: A random graph G(n, p) is a graph constructed by connecting the n nodes randomly. Each edge is included in the graph with probability p (also called: the edge density), with the presence or absence of any two distinct edges in the graph being independent.

Note: consequently a graph with n vertices and M edges is chosen with probability:

The conjecture I am discussing, deals with the second definition.
(Definitions from: Wikipedia on the Erdös-Rényi model)

Useful links:
"On Random Graphs" by Paul Erdös and Alfréd Rényi
Random graphs were first defined by Paul Erdös and Alfréd Rényi in their 1959 paper "On Random Graphs".

A whirlwind tour on random graphs
A very well readable introduction on random graph theory and its history by Fan Chung, written in 2008.

A small example of what can be done with random graphs, as discussed in the above article, is that we can calculate the probability that a random graph in G(n,m) contains a fixed triangle. We use Laplace's rule that

P[G contains the triangle] = #(G which contain the triangle) / #(G ∈ G(n,m)).

Which in our case results in:

P[G contains the triangle] =

Since there are possible edges in total, the number of possible graphs with m edges is . Since for the graph with the triangle, 3 edges are fixed, there are only edges to choose freely, of which we have to choose m-3 edges, which results in that there are possible graphs containing the fixed triangle.
Note: This is far more complicated than when we use the G(n,p) model for random graphs. Here the probability that a random graph G ∈ G(n,p), where p = ½, contains a fixed triangle is simpy 1/8.

"On the evolution of random graphs", by Paul Erdös and Alfréd Rényi
A book on the evolution of random graphs by Paul Erdös and Alfréd Rényi, which was published two years after their first publication on random graphs.

Wikipedia on the Erdös-Rényi model
Here the two ways to model a random graph are discussed, you can find their definitions and a comparison here.

I think it is important to note, as explained in the above link "A whirlwind tour on random graphs", that the G(n,p) model is easier to work with than the G(n,M) model. This is mainly because of the independence of the edges in the G(n,p) model compaired to the dependence of the edges in the G(n,M) model.
The two models do behave similarly in certain cases, as is described on wikipedia:
The expected number of edges in G(n,p) is p, and by the law of large numbers any graph in G(n,p) will almost surely have approximately this many edges (provided the expected number of edges tends to infinity). Therefore a rough heuristic is that if pn2 tends to infinity, then G(n,p) should behave similarly to G(n,M) with M = p as n increases.

WolframMathworld on random graphs
Here you will find a list of references to books and introductions on random graphs.

Random graphs with igraph
A link to the page on random graphs on a website about igraph. Igraph is a free software package for creating and manipulating undirected and directed graphs. Here you will again find the definition of a random graph in two ways and a way of creating random graphs with igraph among more information on random graphs.
If you are interested in igraph you can download it here: download igraph

On d-cubes::.

Definition of a d-cube:
The d-cube is a graph whose vertex set can be labelled with the set of all binary d-tuples, so that its edge set consists of all pairs of vertices which differ in exactly one coordinate.
It is clear that the d-cube has 2d vertices, d⋅2d-1 edges, and is d-regular and bipartite.
(Definition from: Cube Factorizations of Complete graphs, by Peter Adams, Darryn bryant and Barbara Maenhaut)

A 4-cube

Useful links:
Wikipedia on d-cubes
Apparently a d-cube is also named a hypercube. On wikipedia you can find some properties, problems and examples of hypercubes.
WolframMathWorld on d-cubes
Some more properties and examples of hypercubes on WolframMathWorld. Here you will also find a lot of references.