Discrete Morse theory for the collapsibility of supremum sections
Balthazar Bauer Lucas Isenmann










Balthazar Bauer
INRIA, DIENS, PSL research, CNRS, Paris, France


Lucas Isenmann
LIRMM, Université de Montpellier, CNRS, Montpellier, France







    The Dushnik-Miller dimension of a poset ≤ is the minimal number d of linear extensions ≤_1, … , ≤_d of ≤ such that ≤ is the intersection of ≤_1, … , ≤_d.
    Supremum sections are simplicial complexes introduced by Scarf <cit.> and are linked to the Dushnik-Miller as follows: the inclusion poset of a simplicial complex is of Dushnik-Miller dimension at most d if and only if it is included in a supremum section coming from a representation of dimension d.
    Collapsibility is a topological property of simplicial complexes which has been introduced by Whitehead <cit.> and which resembles shellability.
    While Ossona de Mendez <cit.> proved that a particular type of supremum sections are shellable, we show in this article that supremum sections are in general collapsible thanks to the discrete Morse theory developped by Forman <cit.>.




§ INTRODUCTION



The order dimension (also known as the Dushnik-Miller dimension) of a poset ≤ has been introduced by Dushnik and Miller <cit.>.
It is defined as the minimum number d of linear extensions ≤_1, …, ≤_d of ≤ such that ≤ is the intersection of these extensions i.e. ∀ x,y ∈ V, x ≤ y  (∀ i ∈1d, x ≤_i y).
See <cit.> for a comprehensive study of this topic.
This notion is important because, for example, of a theorem of Schnyder <cit.> which states that a graph is planar if and only if the Dushnik-Miller dimension of the inclusion poset of the associated simplicial complex is at most 3.
Representations were introduced by Scarf <cit.>.
A d-representation on a set V is a set of d linear orders on V.
Given R a representation on a set V, we can define a simplicial complex Σ(R) associated to this representation that we call its supremum section.
Scarf proved that every supremum section of a representation satisfying some additional properties, so called “standard”, is the inclusion poset of a d-polytope with one face removed.
Ossona de Mendez <cit.> proved that every abstract simplicial complex of Dushnik-Miller dimension at most d is contained in a complex which is shellable and has a straight line embedding in ℝ^d-1.
Supremum sections also appeared in commutative algebra: Bayer et al. <cit.> studied monomial ideals which are linked to supremum sections by what they call Scarf complexes.
They are used by Felsner et al. <cit.> in order to study orthogonal surfaces.
They also appear in the study of Gonçalves et al. <cit.> of a variant of Delaunay graphs and in the study of empty rectangles graphs by Felsner <cit.>.
Furthermore, they also appear in spanning-tree-decompositions and in the box representations problem as shown by Evans et al. <cit.>.



The goal of our article is to generalize the result of Ossona de Mendez about the shellability of standard supremum sections to every supremum sections.
As there exists supremum sections which are not shellable, for instance the simplicial complex characterized by its facets {a,b,c} and {c,d,e}, we will replace shellability by collapsibility which is a similar notion.
A collapse is a topological operation on simplicial complexes, and more generally on CW-complexes, introduced by Whitehead <cit.> in order to define a simple homotopy equivalence which is a refinement of the homotopy equivalence.
A complex is said to be collapsible if it collapses to a point.
See <cit.> for a comprehensive study of this topic.
The discrete Morse theory introduced by Forman <cit.> is based on this notion and has numerous applications in applied mathematics and computer science.

Homotopy equivalence is a topological notion of topological spaces introduced to classify topological spaces.
Roughly speaking, two spaces are said to be homotopy equivalent if there exists a continuous deformation from one to the other.
A topological space is said to be contractible if it is homotopy equivalent to a point.
Collapsible spaces form an important subclass of contractible spaces.
While contractibility is algorithmically  undecidable by a result of Novikov <cit.>, the subclass of collapsible spaces is algorithmically  recognizable.
More precisely Tancer <cit.> showed that it is NP-complete to decide whether a simplicial complex is collapsible.
Furthermore, every 1-dimensional contractible complex is collapsible but the house with two rooms <cit.> and the dunce hat <cit.> show that there are complexes which are contractible but not collapsible.
Finally, the conjecture of Zeeman <cit.>, which implies the Poincarré conjecture, states that for every finite contractible 2-dimensional CW-complex K, the space K × [0,1] is collapsible.














§ NOTATIONS



In the following, V is a finite set. 
An (abstract) simplicial complex Δ is a subset of 𝒫(V) closed by inclusion (i.e. ∀ X ∈Δ, ∀ Y ⊆ X, Y ∈Δ).
We call faces the elements of Δ and facets the maximal faces of Δ according to the inclusion order.


    
    Given a linear order ≤ on a set V, an element x ∈ V, and a set F ⊆ V, we say that x dominates F in ≤, and we denote it F≤ x, if f ≤ x for every f ∈ F. 
	A d- R on a set V is a set of d linear orders ≤_1 , … , ≤_d on V.	
	Given a d-representation R, an element x ∈ V, and a set F ⊆ V, we say that x dominates F in R if x dominates F in some order ≤_i∈ R.
	We define Σ(R) as the set of subsets F of V such that every v ∈ V dominates F in R.
	The set Σ(R) is called the  of R.


It is easy to show that if R is a d-representation on a set V, then Σ(R) is a simplicial complex.
An example is the following 3-representation on {a,b,c,d,e}: a <_1 b <_1 e <_1 d <_1 c, c <_2 b <_2 a <_2 d <_2 e, and e <_3 d <_3 c <_3 b <_3 a.
The corresponding complex Σ(R), depicted on the left of Figure <ref>, is characterized by its facets {a,b},
{b,c,d}, and {b,d,e}.
For example {a,b,c} is not in Σ(R) as b does not dominate {a,b,c} in any order.




    Let Δ be a simplicial complex.
    We say that a face F of Δ is a  of Δ if it is non-empty, non-maximal and contained in only one facet of Δ.
    
    Let Δ and Γ be two simplicial complexes.
    We say that Δ  to Γ if there exists k simplicial complexes Δ_1, … , Δ_k and a free face F_i of Δ_i for every i ∈1k-1 such that Δ_1 = Δ , Δ_i+1 = Δ_i ∖{ F ∈Δ_i :  F_i ⊆ F } for every i ∈1k-1 and Δ_k = Γ. 
    We say that Δ is  if it collapses to a point.


The Hasse diagram of a poset is the transitive reduction of the digraph of the poset.
Let R be a representation on a set V, we denote H(R) the Hasse diagram of the inclusion poset of Σ(R).


    Let (≤,V) be a poset and let M be a matching of the Hasse diagram of ≤.
    
    For an arc a of the Hasse diagram of ≤, we denote d(a) and u(a) the elements of V such that a = (u(a),d(a)) and d(a) < u(a).
    A matching M of the Hasse diagram of ≤ is said to be  if, when reversing the orientation of the arcs of M,  the Hasse diagram remains acyclic.


It is known that if ≤ is the poset of inclusion of a simplicial complex and M is a matching of the Hasse diagram of ≤ then M is acyclic if and only if there is no sequence of arcs m_1, … , m_n of M such that ( u(m_i+1),d(m_i)) is in the Hasse diagram for all i ∈1n-1 as well as  (u(m_1),d(m_n)).



    
    Let Δ be a simplicial complex.
    If the Hasse diagram of the inclusion poset of Δ admits a complete ( perfect) acyclic matching, then Δ is collapsible.




§ OUR CONTRIBUTION





    
    Let R be a representation on a set V.
    Then Σ(R) is collapsible.


Because of Theorem <ref>, it is enough to show that if R is a representation on a set V, then H(R) admits a complete acyclic matching.



 §.§ Proofs


The proof relies on an induction on the dimension of the representation R.
Let R be a d-representation on a set V.
We denote R' = (≤_1 , … , ≤_d-1) the (d-1)-representation on V obtained from R by deleting the order ≤_d.


    The simplicial complex Σ(R') is a subcomplex of Σ(R).


	Let F be a face of Σ(R').
	As every element x of V dominates F in at least one of the orders ≤_1, … , ≤_d-1, the element x also dominates F in at least one of the orders ≤_1 , … , ≤_d.
	We conclude that F ∈Σ(R).


See Figure <ref> to see what Σ(R') is for the example representation of Definition <ref>.



    We define the function ψ by

    
    ψΣ(R) ∖Σ(R')VFmin_<_d{x ∈ V : x <_i (max_≤_i F)   ∀ i ∈1d-1}

	Then the function ψ is well-defined.


	Let F be a face of Σ(R) ∖Σ(R').
	We denote f_i = max_≤_i F for every i ∈1d.
	As F ∉Σ(R'), there exists an element x ∈ V such that ∀ i ∈1d-1, x <_i f_i.
	So the minimum is taken in a non-empty set.


We define the sets  A = { F ∈Σ(R) ∖Σ(R') : ψ(F) ∉F } and B = { F ∈Σ(R) ∖Σ(R') : ψ(F) ∈ F }.
The goal is to find a complete acyclic matching between A and B.



    
    For every F ∈ A, we have F ∪{ψ(F)}∈ B, ψ(F ∪{ψ(F)}) = ψ(F) and max_≤_d F < ψ(F).
    
    For every F ∈ B, we have F ∖{ψ(F)}∈ A and ψ(F ∖{ψ(F)}) = ψ(F).


	Let F be in A, we denote F' = F ⋃{ψ(F)}.
	For every i ∈1d, we denote f_i (resp. f_i') the maximum of F (resp. F') in the order ≤_i.
	By definition of ψ, ψ(F) <_i f_i for every i ∈1d-1.
	Furthermore, f_d <_d ψ(F), otherwise ψ(F) would not dominate F.
	Thus, f_i = f_i' for every i ∈1d-1 and f_d <_d f_d' = ψ(F).
	Suppose that F' ∉Σ(R).
	Then there would exist a such that a does not dominate F' in any order.
	Thus a <_i f_i (=f_i') for every i ∈1d-1 and a <_d ψ(F) which contradicts the minimality of ψ(F).
	We deduce that F' ∈Σ(R).
	
	As ψ(F) <_i f_i' for every i ∈1d-1, ψ(F) does not dominate F' in R', F' ∉Σ(R') and ψ(F') ≤_d ψ(F).
	If ψ(F') <_d ψ(F) then we would have ψ(F') <_i f_i' for every i ∈1d as f_d' = ψ(F).
	We deduce that ψ(F') = ψ(F) = f_d' ∈ F'.
	Finally, we conclude that F ∪{ψ(F)}∈ B.
	
	The second property can be proved in the same manner.





    
    The Hasse diagram of the inclusion poset of Σ(R) ∖Σ(R') admits a complete acyclic matching.

See Figure <ref> to see an example of a complete acyclic matching.

    We define the function φ : A → B defined by φ(F) = F ∪{ψ(F)} for every F ∈ A.
    
    
    
	Let us show that φ is a bijection.
	To do so, we define the function η : B → A by η(F) = F ∖{ψ(F)} where F ∈ B.
	Lemma <ref> implies that η is well defined, that η∘φ = 𝗂𝖽_A, and that φ∘η = 𝗂𝖽_B.
	Thus φ is a bijection and φ defines a complete matching M = { (F,φ(F)) : F ∈ A } between A and B.
	
	
	
	
	
	
	
	
	
	
	Suppose that M is not acyclic: there exists a sequence m_1, … , m_n of arcs of M where  m_i = (F_i ∪{ψ(F_i)}, F_i) for a F_i ∈ A for every i ∈1n such that (F_i+1∪{ψ(F_i+1)}),F_i) is in the Hasse diagram for every i ∈1n-1 as well as (F_1 ∪{ψ(F_1)},F_n).
    As for every i ∈1n-1, F_i ⊆ F_i+1∪ψ(F_i+1) and |F_i| +1 = |F_i+1∪ψ(F_i+1)|, we deduce that ψ(F_i+1) ∈ F_i.
    Therefore ψ(F_i+1) <_d ψ(F_i) for every i ∈1n-1 and thus ψ(F_n) <_d ψ(F_1).
    As (F_1 ∪{ψ(F_1)},F_n ) is in the Hasse diagram, we show in the same way that ψ(F_1) <_d ψ(F_n) which contradicts the fact that ψ(F_n) <_d ψ(F_1).
    We conclude that M is a perfect acyclic matching of Σ(R)∖Σ(R').


We can now prove Theorem <ref>.

	We prove the result by induction on the number of orders.
	Let R = (≤_1) be a 1-representation on V.
	We denote m_1 the minimum on V in ≤_1.
	Let F be a face of Σ(R) which contains an element x different from m_1.
	Then m_1 does not dominate F in R as m_1 <_1 x.
	The set {m_1} is a face of Σ(R) as every element of V dominates {m_1} in the order ≤_1.
	Thus Σ(R) = {∅, {m_1}} and H(R) admits a complete acyclic matching ({m_1},∅).
	The base case is therefore true.
	
	Let d ≥ 2, we now suppose that the result is true for any (d-1)-representation on V.
	Let R= (≤_1 , … , ≤_d) be a d-representation on V.
	We denote R' = (≤_1 , … , ≤_d-1) the (d-1)-representation on V obtained from R by deleting the order ≤_d.
    We define K as Σ(R) ∖Σ(R').
    Because of Lemma <ref>, the Hasse diagram of the inclusion poset of K admits a complete acyclic matching M_1.

    By induction hypothesis, H(R') admits a complete acyclic matching M_2.
    Thus M_1 ∪ M_2 is a complete matching of H(R).
    Furthermore, H(R) is the union of H(R') and the Hasse diagram of the inclusion poset of K with some arcs between K and Σ(R').
    If an arc between K and Σ(R') is oriented from Σ(R') to K, then there would be a face F of Σ(R') that would contain a face G of K.
    As Σ(R') is closed by inclusion, then G is also in Σ(R') which contradicts the definition of K.
    Therefore the arcs between K and Σ(R') are oriented from K to Σ(R') and we deduce that M_1 ∪ M_2 is a perfect acyclic matching of H(R).
    We conclude by induction.





1

Bing R.H. Bing, Some aspects of the topology of 3-manifolds related to the Poincaré conjecture, Lectures on Modern Mathematics , II , Wiley, pp. 93–128, 1964.

BPS D. Bayer, I. Peeva, B. Sturmfels, Monomial resolutions, Mathematical Research Letters 5, 31 – 46, 1998.

Chari M. K. Chari, On discrete Morse functions and combinatorial decompositions. Discrete Mathematics, 217(1-3), 101-113, 2000.

DM B. Dushnik and E.W. Miller, Partially ordered sets,
   American Journal of Mathematics, 63(3): 600-610, 1941.
  
EFKU W. Evans, S. Felsner, G. Kobourov, and T. Ueckerdt,
  Graphs admitting d-realizers: spanning-tree-decompositions and
  box-representations Proc. of EuroCG 14, 2014.
  
Felsner S. Felsner, Empty Rectangles and Graph Dimension, ArXiv preprint arXiv:math/0601.767, 2006.
  
FK S. Felsner and S. Kappes. Orthogonal surfaces and their CP-orders. Order, vol. 25, no 1, p. 19-47, 2008.

Forman R. Forman, Witten–Morse theory for cell complexes. Topology,  vol. 37, no 5, p. 945-979, 1998.

GI D. Gonçalves and L. Isenmann, Dushnik-Miller dimension of TD-Delaunay complexes, Proc. of EuroCG 17, 2017.

Kozlov D. Kozlov. Combinatorial algebraic topology. Springer Science and Business Media, 2007.
  
MS E. Miller and B. Sturmfels, Combinatorial Commutative Algebra, Graduate Texts in Mathematics, Springer-Verlag, 2004.
  
Ossona P. Ossona de Mendez, Geometric Realization of
  Simplicial Complexes, Proc. of Int. Symp. on Graph Drawing
    1999 LNCS 1731, 323-332, 1999.

Scarf H. Scarf, The Computation of Economic Equilibria, vol. 24 of Cowles Foundation Monograph, Yale University Press, 1973.

Schnyder W. Schnyder, Planar graphs and poset dimension,
   Order 5(4): 323-343, 1989.

Tancer M. Tancer, Recognition of collapsible complexes is NP-complete, Discrete and Computational Geometry, 55(1), 21-38, 2016.

Trotter W. T. Trotter. Combinatorics and partially ordered sets: Dimension theory. Johns Hopkins Series in the Mathematical Sciences, The Johns Hopkins University Press, 1992.

VKF  I. A. Volodin, V. E. Kuznetsov and A. T. Fomenko. The problem of discriminating algorithmically the standard three-dimensional sphere. Russian Mathematical Surveys, 29(5), 71-172, 1974.

Whitehead J. H. C. Whitehead, Simplicial Spaces, Nuclei and m-groups. Proceedings of the London mathematical society, 2(1), 243-327, 1939.

Zeeman E. C. Zeeman, On the dunce hat. Topology, vol. 2, no 4, p. 341-358, 1963.





