Long paths and cycles in subgraphs of the cube

Long paths and cycles in subgraphs of the cube

Tue, 22/01
14:30 		Eoin Long (University of London) Combinatorial Theory Seminar Add to calendar L3
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.