Order and Geometry

用几何对象定义的图和阶为组合学和图论提供了丰富的例子。几何直觉常常引导我们理解复杂的结构。此外，根据几何对象定义的图和阶在优化问题和理论计算机科学中建立了模型依赖关系。在这个项目中，我们专注于这个领域的组合方面。研究分为三行，每一行都将受到一些众所周知的开放的、长期存在的问题的推动，例如：(1)平面上轴列矩形相交图的色数的最佳可能界是什么？（自1960年阿斯普朗德和格伦鲍姆发表开创性论文以来，基本上没有任何进展）；(2)平面图的队列数是否有界？（由Heath、Leighton和Rosenberg于1992年推测）；(3)平面偏序集的布尔维数是否有界？（由Nesetril和Pudlák于1989年提出）。这些问题举例说明了组合学中顺序（或排序）与几何之间不同类型的相互作用。我们研究的基本概念是理解和利用这些。

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.