Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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