Monday, December 11, 2017
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Dimension is a standard measure of complexity of partially ordered sets (posets), introduced by Dushnik and Miller already in 1941. Bounded dimension provides a succinct representation of the poset, allowing queries of the form "is x<y?" to be answered in constant time. Under what circumstances is the dimension bounded? A recent line of research trying to address this question has focused on connections between the dimension and the graph-theoretic structure of a poset, leading to various new bounds on the dimension for structurally restricted posets. Still, the dimension is unbounded even for posets with very simple structure, e.g. planar ones. This motivates investigating stronger notions of dimension, such as Boolean dimension and local dimension, with the intent of obtaining succinct representations for much broader classes of posets. The aim of this talk is to provide a taste of this active area of research. I will introduce the concept of dimension and its variants, present proofs of some simple bounds, and survey most important recent results and open problems.
Colloquium - 16:00
Abstract:
Representations of planar triangulations as contact graphs of a set of
internally disjoint homothetic triangles or respectively of a set of
internally disjoint homothetic squares have received quite some
attention in recent years. In this talk we investigate representations
of planar triangulations as contact graphs of a set of internally
disjoint homothetic pentagons. Surprisingly such a representation
exists for every triangulation whose outer face is a 5-gon. We relate
these representations to five color forests. These combinatorial
structures resemble Schnyder woods respectively transversal
structures. In particular there is a bijection to certain
alpha-orientations and consequently a lattice structure on the set
of five color forests of a given graph. This lattice structure plays
a role in an algorithm that is supposed to compute a contact
representation with pentagons for a given graph. Based on a five
color forest the algorithm builds a system of linear equations and
solves it, if the solution is non-negative, it encodes distances
between corners of a pentagon representation. In this case the
representation is constructed and the algorithm terminates. Otherwise
negative variables guide a change of the five color forest and the
procedure is restarted with the new five color forest. Similar
algorithms have been proposed for contact representations with
homothetic triangles and with squares. The procedure has been
implemented, it computes the solution with few iterations.