Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

   

 

Discrete Morse functions from lexicographic orders


Authors: Eric Babson and Patricia Hersh
Journal: Trans. Amer. Math. Soc. 357 (2005), 509-534
MSC (2000): Primary 05E25; Secondary 05A17, 05A18, 55P15
Published electronically: September 2, 2004
MathSciNet review: 2095621
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper shows how to construct a discrete Morse function with a relatively small number of critical cells for the order complex of any finite poset with $\hat{0} $ and $\hat{1}$ from any lexicographic order on its maximal chains. Specifically, if we attach facets according to the lexicographic order on maximal chains, then each facet contributes at most one new face which is critical, and at most one Betti number changes; facets which do not change the homotopy type also do not contribute any critical faces. Dimensions of critical faces as well as a description of which facet attachments change the homotopy type are provided in terms of interval systems associated to the facets. As one application, the Möbius function may be computed as the alternating sum of Morse numbers.

The above construction enables us to prove that the poset $\Pi_n/S_{\lambda }$ of partitions of a set $\{ 1^{\lambda_1 },\dots ,k^{\lambda_k }\} $ with repetition is homotopy equivalent to a wedge of spheres of top dimension when $\lambda $ is a hook-shaped partition; it is likely that the proof may be extended to a larger class of $\lambda $ and perhaps to all $\lambda $, despite a result of Ziegler (1986) which shows that $\Pi_n/S_{\lambda }$ is not always Cohen-Macaulay.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05E25, 05A17, 05A18, 55P15

Retrieve articles in all journals with MSC (2000): 05E25, 05A17, 05A18, 55P15


Additional Information

Eric Babson
Affiliation: Department of Mathematics, Box 354350, University of Washington, Seattle, Washington 98195
Email: babson@math.washington.edu

Patricia Hersh
Affiliation: Department of Mathematics, Box 354350, University of Washington, Seattle, Washington 98195
Address at time of publication: The Mathematical Sciences Research Institute, 17 Gauss Way, Berkeley, California 94720-5070
Email: phersh@msri.org

DOI: http://dx.doi.org/10.1090/S0002-9947-04-03495-6
PII: S 0002-9947(04)03495-6
Keywords: Discrete Morse theory, poset, order complex, partition
Received by editor(s): July 1, 2003
Published electronically: September 2, 2004
Article copyright: © Copyright 2004 by Eric Babson and Patricia Hersh