Long paths and cycles in subgraphs of the cube
|
Tue, 22/01 14:30 |
Eoin Long (University of London) |
Combinatorial Theory Seminar |
L3 |
Let denote the graph of the -dimensional cube with vertex set
in which two vertices are adjacent if they differ in exactly one coordinate.
Suppose is a subgraph of with average degree at least . How long a
path can we guarantee to find in ?
My aim in this talk is to show that must contain an exponentially long
path. In fact, if has minimum degree at least then must contain a path
of length . Note that this bound is tight, as shown by a -dimensional
subcube of . I hope to give an overview of the proof of this result and to
discuss some generalisations. |
|||

denote the graph of the
-dimensional cube with vertex set
in which two vertices are adjacent if they differ in exactly one coordinate.
Suppose
is a subgraph of
. How long a
path can we guarantee to find in
. Note that this bound is tight, as shown by a
. I hope to give an overview of the proof of this result and to
discuss some generalisations.