[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - May 27th 2019

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our next Monday Lecture & Colloquium on May 27th at 14:15 h & 16:00 h at TU Berlin.

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin 

Time: Monday, May 27th - 14:15 h

Lecture: William T. Trotter (Georgia Institute of Technology)

Title: Stability Analysis for Posets

Abstract:

Trivially, the maximum chromatic number of a graph on n vertices is n, and the only graph which achieves this value is the complete graph  K_n.  It is natural to ask whether this result is "stable", i.e.,  if n  is large, G  has n vertices and the chromatic number of G is close to n, must G  be close to being a complete graph? It is easy to see that for each  c>0, if  G  has n  vertices and chromatic number at least  n−c, then it contains a clique whose size is at least  n−2c. We will consider the analogous questions for posets and dimension.  Now the discussion will really become interesting.

Coffee & Tea Break :

Room MA 316 - Third Floor [British Reading]

Time: Monday, May 27th - 16:00 h s.t.

Colloquium: Felix Schröder (Technische Universität Berlin)

Title: Lower Bounds on the p-centered coloring number

Abstract:

A p-centered coloring is a vertex-coloring of a graph G such that every connected subgraph H of G either receives more than p colors or there is a color that appears exactly once in H. The concept was introduced by Nešetřil and Ossona de Mendez as a local condition for measuring sparsity.  We prove lower bounds on the p-centered coloring numbers. For outerplanar graphs, we show that their maximum p-centered coloring number  is in Theta(p log p). We have examples of graphs of treewidth k needing  (p+k choose k) colors, this matches the upper bound of Pilipczuk and Siebertz. We show that planar graphs may require Omega(p^2 log(p)) colors, while all of them admit a p-centered coloring with O(p^3 log(p)) colors. This improves an O(p^19) bound by Pilipczuk and Siebertz.