Algebraic and topological combinatorics of 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.