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
Abstract:
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
Abstract:
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.