Long paths and cycles in subgraphs of the cube

Let $Q_n$ denote the graph of the $n$-dimensional cube with vertex set $\{0, 1\}^n$

in which two vertices are adjacent if they differ in exactly one coordinate.

Suppose $G$ is a subgraph of $Q_n$ with average degree at least $d$. How long a

path can we guarantee to find in $G$?

My aim in this talk is to show that $G$ must contain an exponentially long

path. In fact, if $G$ has minimum degree at least $d$ then $G$ must contain a path

of length $2^d − 1$. Note that this bound is tight, as shown by a $d$-dimensional

subcube of $Q^n$. I hope to give an overview of the proof of this result and to

discuss some generalisations.