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, May 11, 2009

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
MA 041

Lecture - 14:15

Sandi Klavzar - Ljubljana

Isometric dimension, lattice dimension, and Fibonacci dimension of a graph

The isometric dimension, the lattice dimension, and the Fibonacci dimension of a graph $G$ is the smallest integer $d$ such that $G$ admits an isometric embedding into the $d$-dimensional hypercube, the $d$-dimensional integer lattice, and the $d$-dimensional Fibonacci cube, respectively. In each of the three cases the same graphs, known as partial cubes, have finite dimension. In the first part of the talk we will present classical results about partial cubes such as Chepoi's expansion procedure and the role of Djokovic-Winkler's relation. In the second part we will have a closer look to the Fibonacci dimension, a concept recently introduced together with Sergio Cabello and David Eppstein. In particular, bounds on the Fibonacci dimension of a graph in terms of the isometric and lattice dimension will be presented and corresponding algorithmic issues will be discussed.

Colloquium - 16:00

Mareike Massow - TU Berlin

Linear Extension Diameter of Distributive Lattices

Given a finite poset P, we consider pairs of linear extensions of P with maximum distance, where the distance between two linear extensions L_1, L_2 is the number of pairs of elements of P appearing in different orders in L_1 and L_2. A diametral pair maximizes the distance among all pairs of linear extensions of P. The linear extension diameter of P is the distance between two linear extensions in a diametral pair. It equals the diameter of the linear extension graph of P, which has a natural isometric embedding into the hypercube of dimension {|P| \choose 2} and thus is a partial cube as defined in Sandi Klavzar's talk.

For general posets, it is NP-complete to compute the linear extension diameter. We prove a formula for the linear extension diameter of Boolean lattices which was conjectured by Felsner and Reuter in 1999. Furthermore, we can characterize all diametral pairs of linear extensions of Boolean lattices: They all have a reverse lexicographic structure. These results can be extended to factor lattices, which are downset lattices of unions of chains. It remains open whether something similar is true for other types of distributive lattices.
This is joint work with Stefan Felsner.

Letzte Aktualisierung: 06.05.2009