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.

History ::.

Here you will find some articles related to the history on:

Paul Erdös ::.

Wikipedia on Paul Erdös
Paul Erdös (1913-1996) was an Hungarian mathematician. His field of study was very broad. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory and probability theory. Apparently he was a very eccentric person. You can read about his extraordinary life and achievements on wikipedia.

The Solipsys limited website
A website by Colin Wright. One of the goals is to promote an interest in mathematics. You can find a collection of interesting facts here, including a page on Paul Erdös.

Béla Bollobás ::.

Wikipedia on Béla Bollobás
Béla Bollobás (1943 - present) is a Hungarian-born British mathematician. His fields of interest include functional analysis, combinatorics, graph theory and percolation.

The Solipsys limited website
A website by Colin Wright. One of the goals is to promote an interest in mathematics. You can find a collection of interesting facts here, including a page on Béla Bollobás.

Béla Bollobás' webpage at the University of Memphis
In 1996 Béla Bollobás was appointed to the Jabie Hardin Chair of Excellence at the University of Memphis. This is his page at the University of Memphis.

Béla Bollobás' webpage at Trinity College
Béla Bollobás has been a Fellow of Trinity College, Cambridge since 1970, in 2005 he was awarded a Senior Research Fellowship at Trinity College. This is the website of Trinity College.

Random graphs ::.

"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.

An application in sociology
By now, random graphs have all kinds of applications, for example in sociology. This is an article on random graph models of social networks.

Secret sharing schemes on graphs
A book on another application of random graphs: secret sharing.

d-Cubes ::.

I cannot find much on the history of cube graphs. I did find an interesting fact, namely that cube graphs, or hypercubes, are used for parallel computing.