Order and Geometry

秩序与几何

• 批准号: 426572547
• 负责人: Professor Dr. Stefan Felsner
• 金额: --
• 依托单位: Fachgebiet Diskrete Mathematik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2019
• 资助国家: 德国
• 起止时间: 2018-12-31 至 2023-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/426572547?language=en
• 关键词: Order; 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.

通过几何对象定义的图和序在组合数学和图论中提供了丰富的例子。几何直觉常常引导着复杂的结构，否则就很复杂。此外，根据几何对象定义的图形和顺序在优化问题和理论计算机科学中建模依赖性。在这个项目中，我们专注于这个领域的组合方面。本文的研究分为三个部分，每一部分的研究都是围绕一些著名的、长期存在的问题展开的，如：（1）平面中轴对齐矩形相交图的色数的最佳界是什么？(with自1960年Asplund和Grüunbaum的开创性论文以来基本上没有进展）;（2）平面图的队列数有界吗？（Heath，Leighton and Rosenberg于1992年发表）;（3）平面偏序集的布尔维数有界吗？（由Nesetril和Pudlák在1989年提出）。这些问题描述了组合数学中序（或序）和几何之间不同类型的相互作用。我们研究的基本概念是理解和利用这些。