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*−2*c*.

We will consider the analogous questions for posets and dimension. Now the discussion will really become interesting.

May 27, 2019 | 02:15 PM

Technische Universität Berlin

Institut für Mathematik

Straße des 17. Juni 136

10623 Berlin

Room MA 041 (Ground Floor)