Order and Geometry

点击翻译按钮获取中文摘要

Graphs and orders defined by means of geometric objects provide a rich class of examples in combinatorics and graph theory. The geometric intuition often guides through constructions that are complex and complicated otherwise. Moreover, graphs and orders defined in terms of geometric objects model dependencies in optimization problems and theoretical computer science. Within this project we focus on the combinatorial side of this realm. The research is grouped into three lines and each line will be motivated by some notoriously open, long-standing problems such as: (1) What is the best possible bound for the chromatic number of intersection graphs of axisaligned rectangles in the plane? (with essentially no progress since the seminal paper by Asplund and Gr¨unbaum in 1960); (2) Is the queue number of planar graphs bounded? (conjectured by Heath, Leighton and Rosenberg in 1992); (3) Is the Boolean dimension of planar posets bounded? (posed by Nesetril and Pudlák in 1989).These problems exemplify different types of interplay between orders (or orderings) and geometry in combinatorics. The basic concept of our research is to understand and exploit these.