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 11, 2017

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

Bartosz Walczak - Jagiellonian University in Kraków & TU Berlin

Dimension and its variants for structurally restricted posets

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

Hendrik Schrezenmaier - TU Berlin

Pentagon contact representations

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.

Letzte Aktualisierung: 04.12.2017