Simplicial Lusternik-Schnirelmann category

Publ. Mat. 63 (2019), 265–293 DOI: 10.5565/PUBLMAT6311909 SIMPLICIAL LUSTERNIK–SCHNIRELMANN CATEGORY Desamparados Fern´ andez-Ternero, Enrique Mac´ ıas-Virg´ os, Erica Minuz, and Jos´ e Antonio Vilches Abstract: The simplicial LS-category of a finite abstract simplicial complex is a new invariant of the strong homotopy type, defined in purely combinatorial terms. We prove that it generalizes to arbitrary simplicial complexes the well known notion of arboricity of a graph, and that it allows to develop many notions and results of algebraic topology which are costumary in the classical theory of Lusternik–Schnirelmann category. Also we compare the simplicial category of a complex with the LS-category of its geometric realization and we discuss the simplicial analogue of the Whitehead formulation of the LS-category. 2010 Mathematics Subject Classification: 55U10, 55M30, 06F30. Key words: Lusternik–Schnirelmann category, strong homotopy type, geometric realization, Whitehead formulation of category, graph arboricity. 1. Introduction In a previous paper [9] we introduced the so-called simplicial Lusternik–Schnirelmann category of a simplicial complex. This invariant, denoted by scat K, is defined directly from the combinatorial structure of the complex K, instead of considering the topological LS-category of the geometric realization |K|, by replacing the notion of homotopy by that of contiguity. With this approach it turned out that the simplicial LS-category is an invariant of the strong homotopy type, as defined by Barmak and Minian in [4]. Also, simplicial LS-category is closely related to the LS-category of the finite T0-space represented by the Hasse diagram of K[18]. It is worth noting that although the idea of contiguous simplicial maps is a classic one, the corresponding theory of Lusternik–Schnirelmann category had not been developed until now. Then, many natural questions remained unsolved in this new context. The aim of this paper is to answer some of them: for instance, the relationship between scat Kand cat |K|(Theorem 4.4) or the Whitehead formulation of simplicial category (Definition 6.5), among others. Other results include a direct proof 266 D. Fern´ andez-Ternero, E. Mac´ ıas-Virg´ os, E. Minuz, J. A. Vilches of the formula scat(sd K)≤scat Kfor the barycentric subdivision (Theorem 3.1), or a counterexample of the analogue of the homotopy extension property for subcomplexes (Example 7.6). A final important result (Theorem 8.12) will be that simplicial category generalizes to arbitrary simplicial complexes the well known notion of arboricity of a graph. The contents of the paper are as follows. We start (Section 2) by introducing the definition of simplicial Lusternik–Schnirelmann category scat Kof the simplicial complex K. The idea is to define an analogue of the classical LS-category of a topological space, by replacing the notion of homotopic maps by that of contiguous simplicial maps. We then prove some basic properties of this new notion of category, and we recall our previous result [9] that scat is an invariant of the strong homotopy type. In particular, the category of the simplicial complex Kequals that of its core K0(the minimal subcomplex of K obtained by strong collapses). As a corollary we prove that scat Kis bounded above by the number of vertices and the number of maximal simplices of K0. In Section 3 we study the effect of barycentric subdivision on simplicial category and we give a direct proof of scat(sd K)≤scat K. For that we need to prove that if ϕ,ψare contiguous maps, then the induced maps sd ϕ, sd ψ, are in the same contiguity class. The only proof that we found in the literature is as a consequence of the results given in [4] via finite posets, so we give a direct one. In Section 4 we compare the simplicial category of the complex K with the classical LS-category of the geometric realization |K|, proving that cat |K| ≤ scat K. This implies that cat |K| ≤ scat(sdNK), for any iterated barycentric subdivision sdNKof K. We show an example where this inequality is strict. Section 5 deals with the study of simplicial products. Being more precise, we consider the categorical product, denoted by K×L. Then, we prove that scat(K×L)+1≤(scat K+ 1)(scat L+ 1). We are now (Section 6) in a position to discuss the simplicial analogue of the Whitehead formulation of the LS-category. It is known that for topological spaces Xwith “good” properties the LS-category can be computed as the least integer n= catWh Xsuch that the diagonal map ∆: X→Xn+1 factors (up to homotopy) through the so-called fat wedge Tn+1X. We try to adapt this result to abstract simplicial complexes. First, we define the n-th fat wedge TnKfor any pointed complex Kand we study its behaviour under contiguity. We then define a simplicial Whitehead category scatWh K, which is an invariant Simplicial Lusternik–Schnirelmann Category 267 of the pointed strong homotopy type and we are able to prove that scat K≤scatWh K. However, unlike the continuous case, the other inequality is not true, as we show by an example. In Section 7 we explain how the partial failure of the Whitehead formulation is related to the contiguity extension property. We discuss a new notion of cofibration in the simplicial setting. It is well known that if Ais a subcomplex of a CW-complex Xthen the pair (X, A) has the homotopy extension property. Therefore, if Lis a subcomplex of a simplicial complex K, the pair (|K|,|L|) has the (topological) homotopy extension property. We define a purely combinatorial analogue for a simplicial pair (K, L), but we show counterexamples where the contiguity extension property fails to be true. Finally, Section 8 is focused on the study of the simplicial LS-category in the one-dimensional case, that is, on graphs. The well known graphtheoretical notion of arboricity will play a central role in this study. The arboricity Υ(G) of the graph Gis the cardinality of a minimal decomposition of Ginto disjoint spanning forests, i.e., acyclic subgraphs which are not necessarily connected and cover all the vertices. The aim of this section is to prove that arboricity coincides with simplicial category. Being more precise, we prove that Υ(G) = scat G+ 1. The two main ideas are that categorical subcomplexes are precisely forests and that the notion of contiguity is a very rigid one in the setting of graphs, allowing only a limited number of moves. As a final comment, we emphasize that simplicial LS-category is a new strong homotopy invariant, defined in purely combinatorial terms, that generalizes to arbitrary simplicial complexes the well known notion of arboricity of a graph, and that allows to develop all the machinery of algebraic topology which is costumary in the classical theory of Lusternik–Schnirelmann category. 2. Simplicial category 2.1. The notion of simplicial LS-category. We recall the notion of simplicial LS-category, introduced by the authors in [9]. Let Kand Lbe abstract simplicial complexes. Remember (see [20, §3.5]) that two simplicial maps ϕ, ψ:K→Lare contiguous, denoted by ϕ∼cψ, if for any simplex σ={v0, . . . , vp}of K, the set of vertices ϕ(σ)∪ψ(σ) = {ϕ(v0), . . . , ϕ(vp), ψ(v0), . . . , ψ(vp)} is a simplex of L. More generally, two simplicial maps ϕ, ψ:K→Lare in the same contiguity class, denoted by ϕ∼ψ, if there is a sequence of 268 D. Fern´ andez-Ternero, E. Mac´ ıas-Virg´ os, E. Minuz, J. A. Vilches simplicial maps ϕi:K→L,i= 1, . . . , m, such that ϕ=ϕ1∼cϕ2∼c · · · ∼cϕm=ψ. At this point it is convenient to recall that the subcomplex L0⊆Lis said to be full subcomplex of Lif each simplex of Lwhose vertices belong to L0is also a simplex of L0. The next proposition can be proved easily from this definition. Proposition 2.1. Let ϕ, ψ :K→Lbe two simplicial maps. Let K0⊂Kbe a subcomplex and let L0⊂Lbe a full subcomplex such that ϕ(K0), ψ(K0)⊂ L0. If ϕand ψare contiguous then their restrictions ϕ0, ψ0:K0→L0are contiguous too. The concept of contiguity class provides a simplicial analogue of homotopy classes of continuous maps between topological spaces. By means of the notion of contiguity we define the key concept of categorical subcomplex. Definition 2.2. Let Kbe an abstract simplicial complex. We say that the subcomplex U⊂Kis categorical (in K) if there exists a vertex v∈K such that the inclusion i=iU:U→Kand the constant map c=cv:U→ Kare in the same contiguity class (denoted by i∼c). In other words, the inclusion of Ufactors through the vertex v∈K up to “simplicial homotopy” (meaning contiguity class). Notice that a categorical subcomplex may not be connected. Definition 2.3. Let Kbe an abstract simplicial complex. The simplicial LS-category of K, denoted by scat K, is the least integer n≥0 such that there exist n+ 1 categorical subcomplexes U0, . . . , Unof Kwhich cover K, that is, such that K=U0∪ · · · ∪ Un. For instance, as we shall explain in Subsection 2.3, scat K= 0 if and only if Kis strongly collapsible to a point, in the sense given by Barmak and Minian [3, 4]. 2.2. Maximal simplices. We now show that the simplicial LS-cate- gory can be obtained by taking into account only maximal simplices in its definition. The proof is inspired on the analogous idea for the LS-category of finite topological spaces, that was pointed out to us by J. Strom. Lemma 2.4. Let V⊂U⊂Kbe subcomplexes of K. If Uis categorical (in K) then Vis categorical (in K). Proof: If the inclusion i:U⊂Kverifies i∼cfor some constant map c:U→K, and j:V⊂Uis the inclusion, then i◦j:V→Kis the inclusion, c◦j:V→Kis a constant map, and c◦j∼i◦j. Simplicial Lusternik–Schnirelmann Category 269 Proposition 2.5. In Definition 2.3 one may assume that: 1. Each categorical subcomplex in the covering U0, . . . , Unis a union of maximal simplices of K. 2. Each maximal simplex of Kis contained in only one of the elements of the covering. Proof: Let U0, . . . , Un⊂Kbe a categorical covering. We shall replace each subcomplex Ujby another subcomplex Vj(may be empty) defined as the union of the simplices σ∈Ujwhich are maximal in K. First, V0, . . . , Vnis a covering of K, because if µis a simplex of K, it must be contained in some maximal simplex σ, which turns out to be contained in some Uj. Then µ⊂σ∈Vj, so µ∈Vj. Moreover, Vjis categorical (by Lemma 2.4), because Vj⊂Uj. The second part follows from the fact that if we remove each maximal simplex from all excepting one of the Vj, then the resulting subcomplexes are still categorical, by Lemma 2.4, and they cover K. 2.3. General properties. We state several general properties of simplicial LS-category. In [4] (see also [3]), Barmak and Minian introduced the notion of strong collapse, a particular type of simplicial collapse in the Whitehead’s sense (see Chapter 1, Section 2 of [5]) which is specially adapted to the simplicial structure. Actually, a strong collapse can be modelled as a simplicial map, in contrast with the general concept of simplicial collapse. Definition 2.6. A vertex vof a simplicial complex Kis dominated by another vertex v0if every maximal simplex that contains valso contains v0. An elementary strong collapse consists of removing the open star of a dominated vertex vfrom a simplicial complex K(see Figure 1). v′ v v′v′ Figure 1. An elementary strong collapse. The inverse of a strong collapse is called a strong expansion. Then, two simplicial complexes K,Lhave the same strong homotopy type, 270 D. Fern´ andez-Ternero, E. Mac´ ıas-Virg´ os, E. Minuz, J. A. Vilches denoted by K∼L, if they are related by a sequence of strong collapses and expansions. Surprisingly, this turns out to be intimately related to the classical notion of contiguity. More precisely, having the same strong homotopy type is equivalent to the existence of simplicial maps ϕ:K→ Land ψ:L→Ksuch that ψ◦ϕ∼1Kand ϕ◦ψ∼1L(see [4, Corollary 2.12]). The strong homotopy type gives a simplicial analogue to the homotopy type of topological spaces. Notice that scat K= 0 if and only if Kis strongly collapsible, that is, there is a finite sequence of elementary strong collapses reducing it to a vertex. Example 2.7. The simplicial complex in Figure 2 is not strong collapsible, in fact scat K= 1. 0 1 2 Figure 2. A complex Kwith scat K= 1. For the next example, let us recall the simplicial notions of star and link. Roughly speaking, they correspond to the simplicial counterparts of closed ball and sphere around a vertex. Being more precise, given a simplicial complex Kand v∈Ka vertex, the star of vin K, denoted by st(v;K), is the subcomplex of simplices σ∈Ksuch that σ∪{v} ∈ K. The link of vin K, denoted by lk(v;K), is the subcomplex of st(v;K) of simplices which do not contain v. Example 2.8. Let Kbe a finite simplicial complex and let abe a vertex not in K. The cone K∗ais the simplicial complex generated by the simplices of the form (v0, . . . , vn, a) where (v0, . . . , vn) is a simplex of K. Notice that K∗ais strong collapsible, that is, scat(K∗a) = 0. This result can be proved just by taking into account that lk(u, K ∗a) = lk(u, K)∗a (see [2]). Example 2.9. Let Kbe a finite simplicial complex such that scat K > 0, and let S0be the complex given by only two 0-simplices and no other simplices. We define the suspension of Kas ΣK=K∗S0. Then scat(ΣK) = 1. Notice that any suspension can be naturally decomposed as the union of two simplicial cones, and thus scat(K)≤1. Moreover in this case scat(Σ) 6= 0. First, assume that Kis a minimal complex, that is Simplicial Lusternik–Schnirelmann Category 271 Khas no dominated vertices. The maximal simplices of ΣKare (wi, a) and (wi, a0) where wi,i= 0, . . . , n are the maximal simplices of Kand a,a0are the 0-simplices of S0. Now, since Khas no dominated vertices then for every pair (v, u) of vertices in Kthere is a maximal simplex wiin Kcontaining vbut not containing u. Therefore, the maximal simplex (wi, a) in ΣKcontains vbut not u. So vand uare not dominated vertices in the suspension. Moreover any vertex vis not dominated by the vertices a(resp. a0) since there is always a maximal simplex containing vbut not a(xresp. a0), meaning the simplex containing v and a0(resp. a). Now assume that Kis not minimal, then there is a sequence of strong collapses and expansions from Kto its core K0. Since a point that is dominated in Kis also dominated in ΣK, then there is a sequence of strong collapses and expansions from ΣKto its core ΣK0. Therefore, by means of the next theorem, ΣKand ΣK0have the same strong homotopy type and the result follows. The next theorem was proved in [9, Theorem 3.4] by the authors. Theorem 2.10. The simplicial LS-category is an invariant of the strong homotopy type, that is, K∼Limplies scat K= scat L. Therefore a simplicial complex Kand its core K0have the same simplicial LS-category. Remember that the core of a complex is the minimal subcomplex obtained by eliminating dominated vertices (see for instance Barmak’s book [3]). More precisely, if a vertex vis dominated by another vertex v0, then the collapse r:K→K\vis a strong equivalence. Under a finite number of steps one attains a complex K0which is minimal, that is, it does not have dominated vertices. This minimal complex is unique up to simplicial isomorphism. The next result establishes two combinatorial upper bounds for the simplicial category which do not exist for the usual LS-category. Corollary 2.11. scat Kis strictly bounded from above by both: 1. The number of vertices of K. 2. The number of maximal simplices of its core K0. Proof: The star of a vertex st(v), v∈K0, is a strong collapsible subcomplex of K0because all vertices in st(v) are dominated by v. Therefore, the family {st(v) : v∈K0}provides a cover of K0by categorical subcomplexes, and so we have that scat K0< m, where mis the number of vertices of K0. Since the value of scat Kis a strong homotopy invariant, scat K= scat K0< m. On the other hand, let M(K0) be the number of maximal simplices of K0. Then, from Proposition 2.5 it follows that scat K0< M(K0) because any maximal simplex is a strong collapsible subcomplex of K0. 272 D. Fern´ andez-Ternero, E. Mac´ ıas-Virg´ os, E. Minuz, J. A. Vilches 2.4. Geometric simplicial category. In [9], the authors also introduced the notion of geometric simplicial category gscat Kof the complex K, which is the analogue of the geometric LS-category of a topological space introduced by Fox in [10], see also [6,§3.1]. The difference with scat Kis that each subcomplex in a categorical covering is required to be strongly collapsible in itself, rather than in the ambient complex; in other words, the identity, rather than the inclusion, is in the contiguity class of a constant map. Clearly, scat K≤gscat K. However, as in the continuous case, there are complexes where this inequality is strict; for example, in the standard triangulation of the 2-dimensional torus. Geometric simplicial category has a very different behaviour from that of the ordinary category. In particular it is neither hereditary nor homotopically invariant. However, the bounds of Corollary 2.11 are still true for gscat Kbecause gscat K0= max{gscat L:L∼K}, as proven in [9]. Definition 2.12. Let Kand Lbe two finite simplicial complexes. We define the join K∗Las the simplicial complex with set of vertices K0∪ L0and with simplices the simplices of K, the simplices of L, and the simplices given by σ∪τ,σsimplex in Kand τsimplex in L. Proposition 2.13. Let K,Lbe two finite simplicial complexes, then gscat(K∗L)≤min{gscat K, gscat L}. Proof: Suppose that min{gscat K, gscat L}= gscat K=n, then there are n+ 1 strong collapsible subcomplexes U0, . . . , Uncovering K. Consider the subcomplexes U0∗L, . . . ,Un∗L. These subcomplexes are strong collapsible [3, Proposition 5.1.16 ] and they provide a cover of K∗L. 3. Barycentric subdivision We now study the behaviour of scat under barycentric subdivisions. Our main result states that scat is decreasing under such kind of subdivisions. Theorem 3.1. Let sd Kbe the first barycentric subdivision of the simplicial complex K. Then scat(sd K)≤scat K. This theorem was proved in [9, Corollary 6.7] using results of Barmak and Minian (precisely, [4, Proposition 4.11 and Proposition 4.12]) about finite spaces. We shall reformulate them in order to give a direct proof. If Kis an abstract simplicial complex, its first barycentric subdivision can be defined formally as the complex sd Kwhose vertices {σ}are identified to the simplices σ={v0, . . . , vp}of K, while the simplices of sd Kare the sequences {σ1, . . . , σq}of simplices of Ksuch that σ1⊂ · · · ⊂ σq(see [16,§2.1]). Simplicial Lusternik–Schnirelmann Category 273 Definition 3.2. Let ϕ:K→Lbe a simplicial map. The induced map sd ϕ: sd K→sd Lis defined as (sd ϕ)({σ1, . . . , σq}) = {ϕ(σ1), . . . , ϕ(σq)}. Clearly sd ϕis a simplicial map, sd id = id and sd(ϕ◦ψ) = (sd ϕ)◦ (sd ψ). Proposition 3.3. If the simplicial maps ϕ, ψ :K→Lare in the same contiguity class, ϕ∼ψ, then sd ϕ, sd ψ: sd K→sd Lare in the same contiguity class, sd ϕ∼sd ψ. Proof: Without loss of generality, we may assume that the maps ϕand ψ are contiguous, ϕ∼cψ, which means that ϕ(σ)∪ψ(σ) is a simplex, for any simplex σ∈K. Let F: sd K→sd Lbe the map given by F({σ1, . . . , σq}) = {ϕ(σ1)∪ψ(σ1), . . . , ϕ(σq)∪ψ(σq)}. We shall prove that sd ϕ∼Fby increasing step by step the size of the set Ω(sd ϕ, F) = {σ∈K: (sd ϕ)({σ}) = F({σ})}. Note that (sd ϕ)({σ}) = {ϕ(σ)}, while F({σ}) = {ϕ(σ)∪ψ(σ)}. If sd ϕ=Fthere is nothing to prove. Otherwise, there exists µ∈K such that µ /∈Ω(sd ϕ, F), or equivalently, ϕ(µ) is strictly contained in ϕ(µ)∪ψ(µ). Let us take µto be of maximal dimension with this property; in this way ϕ(σ) = ϕ(σ)∪ψ(σ) when µis a proper face of σ. Now, we can define a new map F1: sd K→sd Las F1({σ}) = ((sd ϕ)({σ}) if σ6=µ, F({µ}) if σ=µ. It follows: (1) The map F1is simplicial. In fact, if {σ1, . . . , σq}is a simplex of sd K, then F1({σ1, . . . , σq}) = {ϕ(σ1), . . . , ϕ(σq)}, if σj6=µfor all j= 1, . . . , q, while F1({σ1, . . . , σq}) = {ϕ(σ1), . . . , ϕ(µ)∪ψ(µ}, . . . , ϕ(σq)}, if σj=µfor some j. In both cases the image is a simplex of sd L. Note that in the second case, by the maximality of µcited above, it follows that ϕ(µ)∪ψ(µ)⊂ϕ(σi) if i>j. 280 D. Fern´ andez-Ternero, E. Mac´ ıas-Virg´ os, E. Minuz, J. A. Vilches Corollary 5.4. Let K∼Lbe two complexes with the same strong homotopy type. Then Kn∼Ln. At this point we are in conditions to prove the main result of this section. It is interesting to point out that the corresponding result for the classical LS-category is cat(X×Y)≤cat X+cat Ywhen the topological space X×Yis completely normal [6, Theorem 1.37], while the result cat E+ 1 ≤(cat B+ 1)(cat F+ 1) is true for an arbitrary fibration [6, Theorem 1.41]. Theorem 5.5. Let Kand Lbe finite simplicial complexes. Then scat(K×L)+1≤(scat K+ 1)(scat L+ 1). Proof: Suppose that scat K=nand scat L=m, therefore there exists a categorical covering U0, . . . , Unof Kand a categorical covering V0, . . . , Vmof L. Consider the subcomplexes Ui×Vj⊂K×L, for 0≤i≤nand 0 ≤j≤m. We want to show that Ui×Vjform a categorical covering of K×L. Each inclusion map iUiis in the same contiguity class of a constant map cuiwhere uiis a vertex of K; analogously, each inclusion iVjis in the same contiguity class of a constant map cvjwhere vjis a vertex in L. By Proposition 5.3 the map iUi×iVj:Ui×Vj→K×Lis in the same contiguity class of the map cvi×cwj:Ui×Vj→K×L. Clearly, iUi×iWj=iUi×Vjand cvi×cwj=c(vi,wj), where (vi, wj) is a vertex of K×L. Therefore the subcomplexes Ui×Vjare categorical. Now, we shall prove that {Ui×Vj}is a covering of K×L. If {(v0, w0),...,(vq, wq)}is a simplex of K×Lthen {v0, . . . , vq}is contained in a subcomplex Uiof Kand {w0, . . . , wq}is contained in a subcomplex Wjof L. Then {(v0, w0),...,(vq, wq)}is contained in Ui×Vj. Thus, we conclude that scat(K×L)+1≤(n+ 1)(m+ 1). 6. Whitehead construction It is well known that for topological spaces Xwith “good properties” there is the following so-called Whitehead characterization of the topological LS-category (see [6, Theorem 1.55]): Theorem 6.1. cat X≤nif and only if the diagonal map ∆: X→Xn+1 factors (up to homotopy) through the so-called fat wedge Tn+1X. This result is a very useful tool for computing LS-category. In this section we shall try to adapt it to abstract simplicial complexes. Simplicial Lusternik–Schnirelmann Category 281 First we define a simplicial version of the topological fat wedge TnX of a topological space X[6,§1.6]. Also, we shall briefly develop the notion of pointed contiguity class. Let Kbe an abstract simplicial complex and fix some vertex v0of K as a base point. For each j= 1, . . . , n let (1) Kj=π−1 j({v0}) = K× · · · × {v0} × · · · × K be the subcomplex of Knspanned by the vertices whose j-th coordinate is the base point v0. Definition 6.2. For n≥1 the n-th fat wedge TnKis the subcomplex K1∪ · · · ∪ Kn⊂Kn. For instance, T1K={v0}is a point and T2Kis the wedge K∨K. Note that TnKis not a full subcomplex of Kn. A pointed map (that is, a simplicial map preserving the base points) ϕ: (K, v0)→(L, w0) induces a simplicial map Tnϕ:TnK→TnL, which is the restriction of ϕn:Kn→Kn. Proposition 6.3. Let ϕ, ψ :K→Lbe two contiguous simplicial maps preserving the base points. Then the induced maps Tnϕ, T nψ:TnK→ TnLare contiguous. Proof: The maps ϕn, ψn:Kn→Lnare contiguous by Proposition 5.3. Moreover they send each subcomplex Kjinto itself. Corollary 6.4. Let (K, v0)∼(L, w0)be two pointed simplicial complexes with the same pointed strong homotopy type, that is, we assume that the homotopy equivalences ϕ,ψbetween Kand L, as well as the sequences of contiguous maps defining the relations ψ◦ϕ∼1Kand ϕ◦ψ∼ 1L, preserve the base points. Then TnK∼TnL. We are now in position to discuss the Whitehead formulation of the simplicial LS-category. In order to be systematic we follow the approach of [6,§1.6], by defining a so-called simplicial Whitehead category scatWh Kand trying to compare it to the simplicial LS-cate- gory scat K. Definition 6.5. We say that scatWh K≤nif the diagonal map ∆: K→ Kn+1 factors through the fat wedge Tn+1Kup to contiguity class. That 282 D. Fern´ andez-Ternero, E. Mac´ ıas-Virg´ os, E. Minuz, J. A. Vilches is, there exists some simplicial map δ:K→Tn+1Ksuch that I◦δ∼∆, where we denote by I:Tn+1K⊂Kn+1 the inclusion: Tn+1KI//Kn+1 K δ OO ∆ 99 Theorem 6.6. scat K≤scatWh K. Proof: Assume that scatWh K=n, and let δ:K→Tn+1Kbe as in Definition 6.5. Let πj:Kn+1 →Kbe the projections onto each factor. Let Kj⊂Tn+1K,j= 1, . . . , n + 1, be the subcomplexes defined in (1). Since I◦δ∼∆, there exists a sequence I◦δ=ϕ1, ϕ2, . . . , ϕm= ∆ of maps such that ϕiand ϕi+1 are contiguous. Call Lj= ∆−1(Kj) the preimages of the Kj⊂Tn+1Kdefined above. Clearly, K=L1∪ · · · ∪ Ln+1. It only remains to show that each subcomplex Lj⊂K is categorical, that is, each inclusion map Ij:Lj⊂Kis in the same contiguity class that a constant map. Since ϕi∼cϕi+1 :K→Kn+1 it follows that πj◦ϕi◦Ij∼cπj◦ϕi+1 ◦Ij:Lj→K. Now, πj◦ϕ1◦Ij=πj◦I◦δ◦Ij, which is the constant map cv0because ∆(Lj)⊂Kj. On the other hand, πj◦ϕm◦Ij=πj◦∆◦Ijis the inclusion Ij. Then Ij∼cv0. We have found n+ 1 categorical subcomplexes covering K, therefore scat K≤n. In this section we shall prove that the converse inequality of Theorem 6.6 is not true, by exhibiting an example of a complex Ksuch that scat K= 1 while scatWh K > 2. The proof of the next propositions is inspired by a result about finite co-H-spaces proved in [14]. First we prove that the simplicial Whitehead category is an invariant of the pointed strong homotopy type. Proposition 6.7. If (K, v0)∼(L, v0)is a pointed strong equivalence as in Corollary 6.4, then scatWh K= scatWh L. Proof: Let scatWh L=n. Consider the following diagram and the strong equivalences Kn+1 ∼Ln+1 (Corollary 5.4) and Tn+1K∼Tn+1L(Corollary 6.4). Simplicial Lusternik–Schnirelmann Category 283 Kn ϕn //Ln ψn oo Tn+1K IK ?? Tn+1ϕ//Tn+1L Tn+1ψ oo IL BB K δK OO ∆K GG ϕ//L ψ oo δL OO ∆L HH With the obvious notations, from the relations ψ◦ϕ∼1Kand ϕ◦ψ∼1L it follows that ψn+1 ◦ϕn+1 ∼1Kn+1 , ϕn+1 ◦ψn+1 ∼1Ln+1 , as well as Tn+1ψ◦Tn+1ϕ∼1Tn+1K, Tn+1ϕ◦Tn+1ψ∼1Tn+1L. Moreover, from the definitions, we have IL◦Tn+1ϕ=ϕn◦IK, IK◦Tn+1ψ=ψn◦IL, as well as ∆L◦ϕ=ϕn◦∆K,∆K◦ψ=ψn◦∆L. Define δK:= Tn+1ψ◦δL◦ϕ. Since, from hypothesis, IL◦δL∼∆L, it follows IK◦δK= (IK◦Tn+1ψ)◦δL◦ϕ =ψn◦(IL◦δL)◦ϕ∼(ψn◦∆L)◦ϕ = ∆K◦(ψ◦ϕ)∼1K. Then scatWh K≤scat L. The other inequality is proved in the same way. Clearly, we may assume that the base point v0is in the core K0, hence eliminating dominated vertices is a pointed equivalence (K, v0)∼ (K0, v0). 284 D. Fern´ andez-Ternero, E. Mac´ ıas-Virg´ os, E. Minuz, J. A. Vilches Corollary 6.8. The simplicial Whitehead category of a complex equals that of its core, scatWh K= scatWh K0. We are now in a position to prove the main results of this section. Lemma 6.9 ([4, Proposition 2.7]).Let K0be a minimal complex and let ϕ:K0→K0be a simplicial map which lies in the same contiguity class as the identity. Then ϕis the identity. Theorem 6.10. Let Kbe a simplicial complex such that scatWh K≤1. Then Kis strongly collapsible, which is equivalent to scat K= 0. Proof: If scatWh K= 0 then the result follows from Theorem 6.6. If scatWh K=1 we have, from Corollary 6.8, that scatWh K0= 1. This means that there exists a simplicial map ϕ:K0→T2K0such that i◦ϕ∼ ∆, where ∆: K0→(K0)2is the diagonal map. Let π1, π2: (K0)2→K0 be the projections of the categorical product. Then i◦ϕ∼∆ =⇒π1◦i◦ϕ∼π1◦∆ = 1 =⇒π1◦i◦ϕ= 1 because K0is a minimal complex (Lemma 6.9). Remember that in the proof of Theorem 6.6 we denoted by L1(respectively, L2) the subcomplex ϕ−1({v0} × K) (resp. ϕ−1(K× {v0})). Then, for v∈L1we have v0=π1◦i◦ϕ(v) = vbecause ϕ(v)∈L1, which shows that L1={v0}. Analogously, π2◦i◦ϕ= 1 = π2◦∆ proves that L2={v0}. Then the core K0=L1∪L2={v0}is a point, that is, the complex Khas the strong homotopy type of a point. Example 6.11. The complex Kin Figure 6 has scat K= 1 so it is not strongly equivalent to a point. From Theorem 6.10 its Whitehead simplicial category is at least 2. Then scatWh K > scat K. 7. Cofibrations We now briefly discuss the notion of cofibration in the simplicial setting. The “homotopy extension property” is a very important notion in topology. A cofibration is a map A→Xwhich satisfies the homotopy extension property with respect to all spaces. It is well known (see [13, p. 14] or [17, p. 68]) that if Ais a subcomplex of a CW-complex X then the pair (X, A) has the homotopy extension property. Therefore, if L⊂Kis a subcomplex of a simplicial complex, the pair (|K|,|L|) of the geometric realizations has the (topological) homotopy extension property. We want to define a purely combinatorial analogue for a simplicial pair(K, L). Simplicial Lusternik–Schnirelmann Category 285 Definition 7.1. A simplicial map i:L→Khas the contiguity extension property if given two simplicial maps ϕ, ψ :L→Mwhich lie in the same contiguity class, ϕ∼ψ, and given an extension of ϕ(that is, a simplicial map ˜ϕ:K→Msuch that ˜ϕ◦i=ϕ), there exists an extension ˜ ψof ψ with ˜ϕ∼˜ ψ: L i  ϕ// ψ//M K ˜ϕ == ˜ ψ == Example 7.2. Let K0be the core of the complex K. Then the inclusion i:K0⊂Kis a simplicial cofibration. In fact, as explained before, there is a simplicial retraction r:K→K0such that r◦i= 1K0and i◦r∼1K. Then one can take ˜ ψ=r◦ψbecause ˜ϕ∼ϕ◦r. As an application of Theorem 6.10, we shall show that there are simplicial pairs (K, L) that do not have the extension property. Theorem 7.3. Let Kbe a connected simplicial complex with scat K= n. Assume that there is a categorical covering L1, . . . , Ln+1 of Ksuch that all the pairs (K, Lj)have the contiguity extension property. Then scatWh K=n. Proof: Due to Theorem 6.6 we only have to prove that scatWh K≤n. By hypothesis, each inclusion Ij:Lj→Kis in the same contiguity class that some constant map, whose image is a vertex vj. Since two such constant maps are contiguous if and only if the vertices vi,vjlie on the same simplex, and Kis connected, we can suppose that all the vertices are equal, say to some base point v0. Taking i=Ij,ϕ=Ij,ψ=v0, and ˜ϕ= 1K, the simplicial extension property gives maps ˜ ψj∼1Ksuch that ˜ ψj(Lj) = {v0}. Define the map δ:K→Tn+1K, δ(v)=(˜ ψ1(v),..., ˜ ψn+1(v)). It is well defined, because each vertex vis contained in some Lj, hence ˜ ψj(v) = v0, meaning that the j-th coordinate of δ(v) is the base point. Moreover δis a simplicial map. In fact, for any simplex σ∈Kwe have that δ(σ) is a simplex in Kn(Definition 5.1). Moreover, σmust be contained in some Lj, and δ(Lj)⊂Kj. Then δ(σ)∈Kj⊂Tn+1K. Now, let ˜ ψj=ϕ1 j∼c· · · ∼cϕm j= 1K 286 D. Fern´ andez-Ternero, E. Mac´ ıas-Virg´ os, E. Minuz, J. A. Vilches be the sequence of contiguous maps connecting ˜ ψjand 1K(clearly we may assume that the length mdoes not depend on j). Then the maps ( ˜ϕk 1,..., ˜ϕk n+1): K→Kn+1, k = 1, . . . , m, define a sequence of contiguous maps between J◦δ= ( ˜ ψ1,..., ˜ ψn+1) and ∆ = (1,...,1). Hence J◦δ∼∆, which means that scatWh K≤n. Remark 7.4.It is interesting to point out that from Theorem 7.3 and the proof of Theorem 6.6 it follows that scat K= scatWh Kif and only if there is a categorical covering L1, . . . , Ln+1 where each pair (K, Lj) has the contiguity extension property. As a corollary, some categorical covering of the complex Kin Figure 6 fails to verify the hypothesis of the preceding theorem, because scat K=1 but scatWh K > 2. Example 7.5. The subcomplex L=K\σ, of the complex Kin Figure 6, where σ={a, b, c}, has not the contiguity extension property. Let vbe the upper vertex of K(see Figure 6). Since Lis strongly collapsible to v, the inclusion ϕ=i:L→Kand the constant map ψ=cv:L→Klie in the same contiguity class. Fix ˜ϕ= 1K:K→Kto be the identity. If there exists ˜ ψ∼1Ksuch that ψ(L) = {v}there must be some sequence ˜ ψ∼cϕ1∼c· · · ∼c1Kof contiguous maps. However, since a, b, c ∈L, the simplicial map ϕ1must be constant, and we obtain that 1Kis contiguous to a constant map, which is a contradiction because scat K6= 0. Example 7.6. A simpler example was communicated to us by N. Scoville: let Kbe the 1-dimensional complex in Figure 7, with vertices a, b,cand let σbe the 1-simplex joining the vertices band c. Then the subcomplex L=K\σhas not the contiguity extension property. b a c σ Figure 7. The subcomplex L=K\σhas not the contiguity extension property. Simplicial Lusternik–Schnirelmann Category 287 8. Graphs 8.1. Arboricity. This section is focused on the study of the simplicial LS-category in the one-dimensional case, that is, on graphs. The well known graph-theoretical notion of arboricity will play a central role in this study. Basically, arboricity is based on the cardinality of minimal decompositions of a graph into disjoint spanning forests, i.e., acyclic subgraphs, which are non-necessarily connected and cover all the vertices. The aim of this section is to prove that arboricity coincides (up to one) with both simplicial and geometric simplicial categories. Remark 8.1.In [1], Aaronson and Scoville introduced a so-called discrete LS-category in the simplicial setting. They proved that, for the 1-dimensional case, it is equivalent to arboricity. Let us start with some basic notions on graph theory. A general reference is Harary’s book [12]. Definition 8.2. Let Gbe a graph. A cycle in Gis an alternating sequence of distinct vertices and edges, v0, e1, v1, . . . , vn−1, en, vn, where the incident vertices of each edge eiare vi−1and virespectively, and such that v0=vn. Under a topological point of view, cycles are triangulations of the circle S1. Definition 8.3. Aforest is a graph without cycles, alternatively it can be called acyclic graph. A tree is a connected forest. Definition 8.4. The arboricity of a graph G, denoted by Υ(G), is the minimum number of edge-disjoint spanning forests into which Gcan be decomposed. Nash-Williams [19] determined the arboricity of a general graph: Theorem 8.5 ([12, Theorem 9.10]).Let Gbe a nontrivial graph and let qnbe the maximum number of edges in any subgraph of Gwith nvertices. Then Υ(G) = max nqn n−1. Example 8.6. For the particular case of complete graphs (see Figure 4) it follows the following formula: Υ(K2n) = n= Υ(K2n−1). 8.2. Categorical subgraphs and forests. Now we prove some results which will be used later in this section. 288 D. Fern´ andez-Ternero, E. Mac´ ıas-Virg´ os, E. Minuz, J. A. Vilches Remark 8.7.Every standard elementary collapse in a graph is the deletion of a so-called leaf vertex vand the unique edge vv0containing v. Thus vis dominated by v0and hence, in graphs, every elementary collapse is an elementary strong collapse. Lemma 8.8. Let Gbe a connected graph and let L⊂Gbe a subgraph containing at least one cycle C. If ϕ:L→Gis a simplicial map contiguous to the inclusion iL:L→G, then ϕ(L)contains the cycle C. Moreover ϕ(L)⊂Land ϕ|Cis the inclusion iC:C→G. Proof: Every edge ein Lsatisfies that ϕ(e)∪eis a simplex in G(for graphs, “simplex” means a vertex or an edge), so, equivalently ϕ(e)⊆e; therefore, either ϕ(e) = eor ϕ(e) is one of the extreme vertices of e. This implies that ϕ(L)⊆L. Let Cbe a cycle contained in Land let us consider the restrictions to Cof ϕand the inclusion iL, denoted by ϕ|Cand iCrespectively, which are also contiguous as consequence of the fact that the composition of contiguous maps is contiguous. So, if ϕmaps every edge of the cycle C onto itself then ϕ(C) = Cand hence ϕ(L) contains the cycle C. Otherwise, there exists an edge e1in Csuch that ϕ(e1)6=e1; we can suppose without loss of generality that ϕ(e1) = v0. Now let us consider the edge e2which is adjacent to e1in v16=v0. Since the map ϕis simplicial, we have ϕ(v1) = v0, which is a contradiction with ϕ(e2)⊆e2. Finally, we conclude that all the edges in Cremain fixed by ϕso ϕ(L) contains at least one cycle. Remark 8.9.Let P⊂Gbe a a path in a graph, such that there is a simplicial map ϕ:P→Gcontiguous to the inclusion iP:P→G. By the same argument of the proof above, any edge econtained in P satisfies that either ϕ(e) = eor ϕ(e) = u, where uis one of the extreme vertices of ewith degree 1, i.e. uis a so-called leaf vertex of P. Thus, we conclude that the only possible reductions induced by a simplicial map contiguous to the inclusion are given by standard collapses. The next result establishes the equivalence for graphs between the notions of categorical subcomplex and acyclic subgraph. Theorem 8.10. Let Gbe a connected graph and let L⊆Gbe a subgraph. Then Lis categorical in Gif and only if Lis a forest. Proof: Let us suppose that there exists a categorical but non-acyclic subgraph L⊂G. By definition, there exists a vertex v∈Gsuch that the inclusion i=iL:L→Gand the constant map c=cv:L→Gare in the Simplicial Lusternik–Schnirelmann Category 289 same contiguity class, which gives a sequence iL=ϕ1∼c· · · ∼cϕm=cv of directly contiguous maps ϕi:L→G. Now, since iL∼cϕ2and Lcontains at least one cycle C, by taking into account the previous lemma we conclude that ϕ2(L) contains at least the cycle C. Moreover, (ϕ2)|C=iCis the inclusion iC:C⊂G. Now, ϕ2∼cϕ3implies, by composing with the inclusion ϕ2(L)⊂L, that iC= (ϕ2)|C∼c(ϕ3)|C. That means, by applying the lemma again, that ϕ3(C) is the cycle C, and by repeating the argument we shall arrive to a cycle that can be deformed into a point, which is impossible. Hence we conclude that Lis an acyclic subgraph of G, that is, Lis a forest. Conversely, let us assume that Lis a forest, so Lis a disjoint union of trees Tiwith i= 1, . . . , n. It is clear that each inclusion map Ti⊂Gis in the same contiguity class as the constant map sending the tree Tionto one of its vertices vi. Since Gis connected, there is at least one path in Gjoining every vertex viwith a given vertex v0. Then the inclusion of Lis in the same contiguity class as the constant map v. Hence Lis a categorical subcomplex in G. Lemma 8.11. Let Gbe a connected graph. For every covering of G by forests there exists a covering of Gby trees with the same number of elements. Proof: Let F1, . . . , Fkbe a covering of Gby forests. Since Gis connected, it follows that given two trees Tand T0in a forest Fiand any vertices v∈Tand v0∈T0, they can be linked by means of a path in G. By adding such a path to Fi, and removing, if necessary, the edges of the path which create cycles and are not contained in Fi, we link the trees T and T0of Fi(see Figure 8). FiTi v v′ v v′ Figure 8. Converting a forest into a tree.