Discrete Morse functions from lexicographic orders
Authors:
Eric Babson and Patricia Hersh
Journal:
Trans. Amer. Math. Soc. 357 (2005), 509534
MSC (2000):
Primary 05E25; Secondary 05A17, 05A18, 55P15
Published electronically:
September 2, 2004
MathSciNet review:
2095621
Fulltext 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 and 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 of partitions of a set with repetition is homotopy equivalent to a wedge of spheres of top dimension when is a hookshaped partition; it is likely that the proof may be extended to a larger class of and perhaps to all , despite a result of Ziegler (1986) which shows that is not always CohenMacaulay.
 1.
E. Babson, A. Björner, S. Linusson, J. Shareshian and V. Welker, Complexes of not connected graphs, Topology 38 (1999), 271299. MR 1660341 (2000a:57001)
 2.
E. Babson and D. Kozlov, Group actions on posets, To appear in J. Algebra.
 3.
L. Billera and G. Hetyei, Linear inequalities for flags in graded partially ordered sets, J. Combin. Theory Ser. A 89 (2000), 77104.MR 1736134 (2001m:52011)
 4.
A. Bjorner, Shellable and CohenMacaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), no. 1, 159183. MR 0570784 (81i:06001)
 5.
A. Björner, Posets, regular CW complexes and Bruhat order, European J. Combin. 5 (1984), no. 1, 716.MR 0746039 (86e:06002)
 6.
A. Björner, Topological Methods, in Handbook of Combinatorics (R. Graham, M. Grötschel and L. Lovasz, eds.), NorthHolland, Amsterdam, 1993.MR 1373690 (96m:52012)
 7.
A. Björner and M. Wachs, Bruhat order of Coxeter groups and shellability, Adv. in Math. 43 (1982), 87100. MR 0644668 (83i:20043)
 8.
A. Bjorner and M. Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277 (1983), no. 1, 323341. MR 0690055 (84f:06004)
 9.
A. Björner and M. Wachs, Nonpure shellable complexes and posets I, Trans. Amer. Math. Soc. 348 (1996), 12991327. MR 1333388 (96i:06008)
 10.
A. Björner and M. Wachs, Nonpure shellable complexes and posets II, Trans. Amer. Math. Soc. 349 (1997), 39453975. MR 1401765 (98b:06008)
 11.
M. Chari, On discrete Morse functions and combinatorial decompositions, Discrete Math 217 (2000), no. 13, 101113. MR 1766262 (2001g:52016)
 12.
J. Folkman, The homology groups of a lattice, J. Math. Mech. 15 (1966), 631636.MR 0188116 (32:5557)
 13.
R. Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), 90145.MR 1612391 (99b:57050)
 14.
P. Hersh, Lexicographic shellability for balanced complexes, J. Algebraic Combin. 17 (2003), no. 3, 225254. MR 2001670 (2004f:05190)
 15.
P. Hersh, On optimizing discrete Morse functions, Preprint 2003.
 16.
P. Hersh and R. Kleinberg, The refinement complex of the poset of partitions of a multiset, In preparation.
 17.
P. Hersh and V. Welker, Gröbner basis degree bounds on , To appear in Proceedings of the AMSIMSSIAM Joint Summer Research Conference on Integer Points in Polyhedra.
 18.
D. Kozlov, General lexicographic shellability and orbit arrangements, Ann. of Comb. 1 (1997), no. 1, 6790. MR 1474801 (98h:52023)
 19.
D. Kozlov, Complexes of directed trees, J. Combin. Theory Ser A 88 (1999), no. 1, 112122. MR 1713484 (2000j:05036)
 20.
GC. Rota, On the foundations of combinatorial theory I: Theory of Möbius functions, Z. Wahrsch. 2 (1964), 340368. MR 0174487 (30:4688)
 21.
J. Shareshian, On the shellability of the order complex of the subgroup lattice of a finite group, Trans. Amer. Math. Soc. 353 (2001), no. 7, 26892703.MR 1828468 (2002k:06006)
 22.
R. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972), 197217.MR 0309815 (46:8920)
 23.
R. Stanley, Enumerative Combinatorics, vol. I. Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986; second printing, Cambridge University Press, Cambridge/New York, 1997.MR 0847717 (87j:05003)
 24.
R. Stanley, Combinatorics and Commutative Algebra, second ed., Birkhäuser, Boston, 1996.MR 1453579 (98h:05001)
 25.
V. Welker, Direct sum decompositions of matroids and exponential structures, J. Combin. Theory Ser. B 63 (1995), no. 2, 222244. MR 1320168 (96e:05042)
 26.
G. Ziegler, On the poset of partitions of an integer, J. Combin. Theory Ser. A 42 (1986), no. 2, 215222.MR 0847552 (87k:06009)
 1.
 E. Babson, A. Björner, S. Linusson, J. Shareshian and V. Welker, Complexes of not connected graphs, Topology 38 (1999), 271299. MR 1660341 (2000a:57001)
 2.
 E. Babson and D. Kozlov, Group actions on posets, To appear in J. Algebra.
 3.
 L. Billera and G. Hetyei, Linear inequalities for flags in graded partially ordered sets, J. Combin. Theory Ser. A 89 (2000), 77104.MR 1736134 (2001m:52011)
 4.
 A. Bjorner, Shellable and CohenMacaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), no. 1, 159183. MR 0570784 (81i:06001)
 5.
 A. Björner, Posets, regular CW complexes and Bruhat order, European J. Combin. 5 (1984), no. 1, 716.MR 0746039 (86e:06002)
 6.
 A. Björner, Topological Methods, in Handbook of Combinatorics (R. Graham, M. Grötschel and L. Lovasz, eds.), NorthHolland, Amsterdam, 1993.MR 1373690 (96m:52012)
 7.
 A. Björner and M. Wachs, Bruhat order of Coxeter groups and shellability, Adv. in Math. 43 (1982), 87100. MR 0644668 (83i:20043)
 8.
 A. Bjorner and M. Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277 (1983), no. 1, 323341. MR 0690055 (84f:06004)
 9.
 A. Björner and M. Wachs, Nonpure shellable complexes and posets I, Trans. Amer. Math. Soc. 348 (1996), 12991327. MR 1333388 (96i:06008)
 10.
 A. Björner and M. Wachs, Nonpure shellable complexes and posets II, Trans. Amer. Math. Soc. 349 (1997), 39453975. MR 1401765 (98b:06008)
 11.
 M. Chari, On discrete Morse functions and combinatorial decompositions, Discrete Math 217 (2000), no. 13, 101113. MR 1766262 (2001g:52016)
 12.
 J. Folkman, The homology groups of a lattice, J. Math. Mech. 15 (1966), 631636.MR 0188116 (32:5557)
 13.
 R. Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), 90145.MR 1612391 (99b:57050)
 14.
 P. Hersh, Lexicographic shellability for balanced complexes, J. Algebraic Combin. 17 (2003), no. 3, 225254. MR 2001670 (2004f:05190)
 15.
 P. Hersh, On optimizing discrete Morse functions, Preprint 2003.
 16.
 P. Hersh and R. Kleinberg, The refinement complex of the poset of partitions of a multiset, In preparation.
 17.
 P. Hersh and V. Welker, Gröbner basis degree bounds on , To appear in Proceedings of the AMSIMSSIAM Joint Summer Research Conference on Integer Points in Polyhedra.
 18.
 D. Kozlov, General lexicographic shellability and orbit arrangements, Ann. of Comb. 1 (1997), no. 1, 6790. MR 1474801 (98h:52023)
 19.
 D. Kozlov, Complexes of directed trees, J. Combin. Theory Ser A 88 (1999), no. 1, 112122. MR 1713484 (2000j:05036)
 20.
 GC. Rota, On the foundations of combinatorial theory I: Theory of Möbius functions, Z. Wahrsch. 2 (1964), 340368. MR 0174487 (30:4688)
 21.
 J. Shareshian, On the shellability of the order complex of the subgroup lattice of a finite group, Trans. Amer. Math. Soc. 353 (2001), no. 7, 26892703.MR 1828468 (2002k:06006)
 22.
 R. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972), 197217.MR 0309815 (46:8920)
 23.
 R. Stanley, Enumerative Combinatorics, vol. I. Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986; second printing, Cambridge University Press, Cambridge/New York, 1997.MR 0847717 (87j:05003)
 24.
 R. Stanley, Combinatorics and Commutative Algebra, second ed., Birkhäuser, Boston, 1996.MR 1453579 (98h:05001)
 25.
 V. Welker, Direct sum decompositions of matroids and exponential structures, J. Combin. Theory Ser. B 63 (1995), no. 2, 222244. MR 1320168 (96e:05042)
 26.
 G. Ziegler, On the poset of partitions of an integer, J. Combin. Theory Ser. A 42 (1986), no. 2, 215222.MR 0847552 (87k:06009)
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 947205070
Email:
phersh@msri.org
DOI:
http://dx.doi.org/10.1090/S0002994704034956
PII:
S 00029947(04)034956
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
