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
partners


Monday Lecture and Colloquium


Monday, January 25, 2016

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



Lecture - 14:15

Tom Trotter - Georgia Institute of Technology, Atlanta

Dimension for Posets and Structural Graph Theory

Abstract:
Although the roots of this work can be traced back more than 40 years, there has been a real surge of research in the last five years exploring connections between the dimension of a poset and the structural/topological properties of its order diagram and the associated cover graph. After reviewing essential preliminary material, we will explore the origins and motivation for the following three theorems, and we will outline the proof techniques used to prove them:

  1. If P is a poset with a planar diagram and all minimal elements of P are on the exterior face in a drawing without edge crossings of the diagram of P, then dim(P) ≤ 13.

  2. For every positive integer d, if P is a poset and dim(B) ≤ d whenever B is a block of P, then dim(P) ≤ d+2.

  3. For every positive integer k, there exists a constant d0 = d0(k) so that if P is a poset which does not contain a subposet consisting of two disjoint k-element chains
    with all points in one chain incomparable with all points of the other, and the cover graph of P is planar, then dim(P) ≤ d0.

These results represent joint work with Dave Howard, Noah Streib, Bartosz Walczak, Ruidong Wang and Stephen Young.




Colloquium - 16:00

Gwenaël Joret - Université Libre de Bruxelles

Dimension of planar posets

Abstract: In 2012, Streib and Trotter uncovered a connection between the dimension of posets and the topology of their order diagram by showing that posets with planar cover graphs have dimension bounded from above by a function of their height. That statement begged to be generalized---what about other classes of sparse graphs for instance?---and indeed several extensions of the Streib-Trotter theorem have been found recently, cf. Tom Trotter's talk.

In this talk, I will go back to the roots of this area and address the question of how good a bound on the dimension one can get for posets with planar cover graphs in terms of the height. Nowadays, we know of four genuinely different ways of proving the Streib-Trotter theorem but they all give exponential bounds, while Streib and Trotter suggested that a linear bound might exist. I will report on ongoing work on this problem, and in particular sketch a proof that there is a linear bound if the diagram of the poset can be drawn in a planar way. This is joint work with Piotr Micek and Veit Wiechert.



Letzte Aktualisierung: 14.01.2016