#
Monday Lecture and Colloquium

**Monday, December 8, 2008 **

Freie Universität Berlin

Institut für Informatik

Takustr. 9,

room 005

** Lecture - 14:15**

###
Gill Barequet - Dept. of Computer Science, Technicon (Haifa)

### Counting Polycubes

*Abstract:*

A $d$-dimensional polycube of size $n$ is a $(d-1)$-face-connected
set of $n$ cubes in $d$ dimensions. Among many interesting questions
related to polycubes, one can ask how we can count them efficiently
(say, for specific values of $n$ and $d$), and, for a fixed dimension
$d$, what the asymptotic growth rate of $d$-dimensional polycubes is.
In the past 50 years there have been two (sometimes parallel) research
tracks of these questions: one in the mathematical literature and one
in the statistical-physics literature. In this talk I will attempt to
provide an overview of both tracks.

**Colloquium - 16:00**

###
Darko Dimitrov - FU Berlin

### Gray Codes Avoiding or Containing Given Matchings

*Abstract:*

A (cyclic) $n$-bit Gray code is a (cyclic) ordering of all $2^n$ binary strings of length $n$ such that consecutive strings differ in a single bit. Alternatively, an $n$-bit Gray code can be viewed as a Hamiltonian path of the $n$-dimensional hypercube $Q_n$, and a cyclic Gray code as a Hamiltonian cycle of $Q_n$. Applications of hypercubes in parallel computing inspired the investigation of Hamiltonian paths and cycles in hypercubes that avoid a given set of faulty edges, or contain a set of prescribed edges.
In this talk, we sketch the proofs of two recent results in this area.

First, we consider (cyclic) Gray codes avoiding a given set of faulty edges of $Q_n$ that form a matching. Given a matching $M$ and two vertices $u, v$ of $Q_n, n \geq 4$, our main result provides a necessary and sufficient condition, expressed in terms of forbidden configurations for $M$, for the existence of a (cyclic) Gray code between $u$ and $v$ avoiding $M$.
This is work with Tom\'a\v{s} Dvo\v{r}\'ak, Petr Gregor, and Riste \v{S}krekovski.

Second, we present the proof by Ji\v{r}\'i Fink that every perfect matching of $Q_n, n \geq 2$, can be extended to a Hamiltonian cycle.

Letzte Aktualisierung:
03.12.2008