Hamilitonian cycles of middle-levels subgraphs of hypercubes

Prelegent(ci)

Wiktor Zuba

Afiliacja

MIMUW

Termin

5 kwietnia 2018 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

The n-dimension hypercube graph is the graph with vertices represented by sequences of n bits, with edges connecting those vertices,
which representations differ at exactly one position.
We can divide the graph into (n+1) levels, where k-th level contains those vertices, which have exactly k ones.
A middle levels graph is the subgraph of the odd-dimension hypercube graph induced by the two middle levels.
For the hypercube generating a Hamiltonian cycle efficiently is a rather easy problem, but for the middle levels graph even
the existence of such cycles was an open problem for the last three decades.
After the conjecture was confirmed in 2014 new easier proofs and more efficient ways of generating the cycles began to appear.

In my talk I shall present a proof (or at least the most important parts) of the existence of such a cycle for every middle levels graph.
I will also show how the (partially constructive) proof of existence of such a cycle can be converted into amortized constant-time algorithm
for generating the Gray code.

The presentation is based on two papers:
Petr Gregor, Torsten Mütze, Jerri Nummenpalo, "A short proof of the middle levels theorem",
Torsten Mütze, Jerri Nummenpalo, "A constant-time algorithm for middle levels Gray codes".

---