Random subgraphs of the hypercube

Hypercubes are arguably one of the most fundamental and most studied objects in Combinatorics. They have many nice properties which are very useful in several applications in Computer Science, one these properties being Hamiltonian - a graph is said to be Hamiltonian if it contains a cycle which goes through every vertex exactly once. Let $G$ be a graph satisfying a \textit{monotone} increasing property, it is then natural to ask how \textit{robust} this property is and one way to measure that is to determine whether almost all subgraphs of $G$ have the property according to some natural distribution. 
In this talk, we will be concerned with random binomial distributed subgraphs of the $n$-dimensional hypercube. Let $0\leq p\leq 1$, we denote by  $\mathcal{Q}^{p}_n$ a spanning random subgraph of a $d$-dimensional hypercube $\mathcal{Q}_n$, where each edge is included independently with probability $p$. Answering an old Conjecture of Bollob\'as, we show that $1/2$ is a \textit{sharp threshold} for Hamiltonicity i.e. provided $p>1/2$, with high probability as $n\rightarrow \infty$, $Q^{p}_n$ is Hamiltonian whereas if $p<1/2$ then with high probability $Q^{p}_n$ is not Hamiltonian. This talk will be based on joint work with Condon, Espuny Díaz, Kühn and, Osthus. 

Date and Venue

Start Date
FC1 030
End Date


António Girão

Speaker's Institution

University of Oxford



Algebra, Combinatorics and Number Theory