Algebraic and topological combinatorics of posets

偏序集的代数和拓扑组合

• 批准号: 0500638
• 负责人: Patricia Hersh
• 金额: $ 10.16万
• 依托单位: Indiana University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-01 至 2009-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0500638&HistoricalAwards=false
• 关键词: Algebraic; topological; combinatorics; posets

The investigator will develop and apply combinatorial methods for studying the topological structure of simplicial complexes and cell complexes arising in combinatorics and related fields. A major focus is to deal with complexes of more general topological type than many of the prevalent methods within combinatorics were designed to handle, e.g. in new techniques for proving connectivity lower bounds. The investigator will continue her ongoing effort to develop techniques for constructing discrete Morse functions with few critical cells, with emphasis on order complexes of partially ordered sets and on related free resolutions (both for monomial ideals, and also for resolving a residue field over a monomial or toric ring). Substantial improvement, at least for order complexes, will likely require better understanding of the very rich structure governing gradient paths between critical cells. In related work, she also plans to study Poincare' series for free resolutions over monomial and toric rings, for instance trying to better understand for toric rings which such Poincare' series will be rational. She also intends to study modular elements in (non-geometric) lattices and to try to generalize lexicographic shellability to skeleta of complexes, motivated again by potential applications to constructing small free resolutions and also to bounding graph chromatic number (via better understanding of characteristic polynomial). Topological combinatorics, and in particular connectivity lower bounds, have in the past been used to determine and verify complexity theory lower bounds on the running time for certain types of algorithms, to deduce results in commutative algebra about relations among polynomials via the theory of free resolutions, and also to give lower bounds on the number of colors needed to color the vertices of a graph in such a way that no two vertices sharing an edge are the same color. The investigator is interested in further developing combinatorial techniques (such as a recently introduced discrete version of Morse theory) for studying topological structure, letting potential applications guide the way. Morse theory is a classical theory which analyzes the topological structure of an object by viewing the object progressively from bottom to top, keeping track of essential data at those moments in time where fundamental changes in structure take place; recently Robin Forman introduced a discrete version of this seemingly inherently continuous notion. One of the investigator's major focuses is to develop to practical machinery for making this theoretically very powerful tool convenient to use on real (and in many cases very complex) examples.

研究人员将开发和应用组合方法来研究组合学及相关领域中出现的单纯复形和胞复形的拓扑结构。一个主要的重点是处理复杂的更一般的拓扑类型比许多流行的方法在组合学的设计处理，例如在新的技术证明连通性下界。调查员将继续她正在进行的努力，以开发技术，用于构建离散的莫尔斯功能与几个关键细胞，重点是为了复杂的偏序集和相关的自由决议（既为单项式理想，也为解决剩余领域的单项式或环面环）。实质性的改进，至少对于有序复合体，可能需要更好地理解控制关键单元之间的梯度路径的非常丰富的结构。在相关的工作中，她还计划研究庞加莱系列的自由决议单项和环面环，例如试图更好地了解环面环等庞加莱系列将是合理的。她还打算研究（非几何）格中的模元素，并试图将字典式可壳性推广到复形的可壳性，再次受到构建小自由分辨率和边界图色数（通过更好地理解特征多项式）的潜在应用的启发。拓扑组合学，特别是连通性下界，在过去已经被用于确定和验证某些类型的算法的运行时间的复杂性理论下界，通过自由分解理论推导出关于多项式之间关系的交换代数结果，并且还给出了对图的顶点着色所需的颜色数量的下限，使得没有两个共享边的顶点是相同的颜色。研究人员有兴趣进一步发展组合技术（如最近推出的离散版本的莫尔斯理论）研究拓扑结构，让潜在的应用程序指导的方式。莫尔斯理论是一个经典的理论，它分析一个物体的拓扑结构，从下到上逐步观察物体，在结构发生根本变化的时刻及时跟踪基本数据;最近罗宾福尔曼介绍了这个看似内在连续概念的离散版本。研究人员的主要重点之一是开发实用的机器，使这个理论上非常强大的工具方便地用于真实的（在许多情况下非常复杂）的例子。