---
abstract: 'This paper uses dualities between facet ideal theory and Stanley-Reisner theory to show that the facet ideal of a simplicial tree is sequentially Cohen-Macaulay. The proof involves showing that the Alexander dual (or the cover dual, as we call it here) of a simplicial tree is a componentwise linear ideal. We conclude with additional combinatorial properties of simplicial trees.'
author:
- 'Sara Faridi[^1]'
title: 'Simplicial Trees are Sequentially Cohen-Macaulay'
---

The main result of the this paper is that the facet ideal of a simplicial tree is sequentially Cohen-Macaulay. Sequentially Cohen-Macaulay modules were introduced by Stanley \[S\] (following the introduction of nonpure shellability by Björner and Wachs \[BW\]) so that a nonpure shellable simplicial complex had a sequentially Cohen-Macaulay Stanley-Reisner ideal. Herzog and Hibi (\[HH\]) then defined the notion of a componentwise linear ideal, which extended a criterion of Eagon and Reiner (\[ER\]) for Cohen-Macaulayness of an ideal to a criterion for sequential Cohen-Macaulayness.

Simplicial trees, on the other hand, were introduced in \[F1\] in the context of Rees rings, and their facet ideals were studied further in \[F2\] for their Cohen-Macaulay properties, and in \[Z\] for their resolutions. The facet ideal of a given simplicial complex is a square-free monomial ideal where every generator is the product of the vertices of a facet of the complex. If the simplicial complex is a tree (Definition \[tree-def\]), it turns out that its facet ideal has many interesting algebraic and combinatorial properties.

Given a square-free monomial ideal, one could consider it as the facet ideal of one simplicial complex, and the Stanley-Reisner ideal of another. This in a sense gives two “languages” to study a square-free monomial ideal. Below we provide a dictionary which makes it easy to move from one language to the other. We use this dictionary to translate existing criteria for Cohen-Macaulayness and sequential Cohen-Macaulayness into the language of facet ideals, and then finally use these criteria to show that the facet ideal of a simplicial tree is sequentially Cohen-Macaulay (Corollary \[main-result\]).

There are several byproducts. An immediate one is that the facet ideal of an unmixed simplicial tree (Definition \[unmixed\]) is Cohen-Macaulay (Corollary \[F2-cor\]). This is discussed at length and proved independently in \[F2\], where we introduce the concept of “grafting” a simplicial complex. As it turns out, any unmixed tree is grafted, and any grafted simplicial complex is Cohen-Macaulay. This fact, in addition to proving the statement of Corollary \[F2-cor\], gives the precise combinatorial structure of a Cohen-Macaulay tree.

Another outcome is that the Stanley-Reisner complex corresponding to a Cohen-Macaulay tree is shellable. This was known in the case of graphs (\[V\]). In general, shellability is only a necessary condition for Cohen-Macaulayness.

The paper is organized as follows: Section \[basic-section\] reviews the basics of facet ideal theory, introducing cover complexes. In Section \[dualities-section\] we discuss how facet ideal theory relates to Stanley-Reisner theory. In Section \[trees-section\] we define simplicial trees and discuss their localization. In Section \[sequential-section\] we define sequentially Cohen-Macaulay and componentwise linear ideals, and introduce a criterion for an ideal to be sequentially Cohen-Macaulay, which we use in Section \[trees-scm-section\] to prove that trees are sequentially Cohen-Macaulay.

For the convenience of the reader, we have included a table of notation at the end of the paper (Figure \[index\]).

We would like to thank Jürgen Herzog for raising the question of whether simplicial trees are sequentially Cohen-Macaulay, and for an earlier reading of this manuscript.

Basic Definitions {#basic-section}
=================

This section is a review of the basic definitions and notations in facet ideal theory. Much of the material here appeared in more detail in \[F1\] and \[F2\], except for the discussion on the cover complex.

A *simplicial complex* $\Delta$ over a set of vertices $V=\{
  {v_1,\ldots,v_n}\}$ is a collection of subsets of $V$, with the property that $\{ v_i \} \in \Delta$ for all $i$, and if $F \in \Delta$ then all subsets of $F$ are also in $\Delta$ (including the empty set). An element of $\Delta$ is called a *face* of $\Delta$, and the *dimension* of a face $F$ of $\Delta$ is defined as $|F| -1$, where $|F|$ is the number of vertices of $F$. The faces of dimensions 0 and 1 are called *vertices* and *edges*, respectively, and ${ {\rm{dim}} \ }\emptyset =-1$. The maximal faces of $\Delta$ under inclusion are called *facets* of $\Delta$. The dimension of the simplicial complex $\Delta$ is the maximal dimension of its facets.

We denote the simplicial complex $\Delta$ with facets ${F_1,\ldots,F_q}$ by $$\Delta = {\langle {F_1,\ldots,F_q}\rangle}$$ and we call $\{ {F_1,\ldots,F_q}\}$ the *facet set* of $\Delta$. A simplicial complex with only one facet is called a *simplex*. By a *subcollection* of $\Delta$ we mean a simplicial complex whose facet set is a subset of the facet set of $\Delta$.

A simplicial complex ${\Delta}={\langle {F_1,\ldots,F_q}\rangle}$ is *connected* if for every pair $i,j$, $1
  \leq i < j \leq q$, there exists a sequence of facets $F_{t_1},\ldots,F_{t_r}$ of ${\Delta}$ such that $F_{t_1}=F_i$, $F_{t_r}=F_j$ and $F_{t_s} \cap F_{t_{s+1}} \neq \emptyset$ for $s=1,\ldots,r-1$.

\[facet-ideal\] Let $k$ be a field and ${x_1,\ldots,x_n}$ be a set of indeterminates, and $R=k[{x_1,\ldots,x_n}]$ be a polynomial ring.

-   Let $\Delta$ be a simplicial complex over $n$ vertices labeled ${v_1,\ldots,v_n}$. We define the *facet ideal* of ${\Delta}$, denoted by ${{\mathcal{F}}}({\Delta})$, to be the ideal of $R$ generated by square-free monomials $x_{i_1}\ldots x_{i_s}$, where $\{v_{i_1},\ldots, v_{i_s}\}$ is a facet of $\Delta$.

-   Let $I=({M_1,\ldots,M_q})$ be an ideal in $R$, where ${M_1,\ldots,M_q}$ are square-free monomials in ${x_1,\ldots,x_n}$ that form a minimal set of generators for $I$. We define the *facet complex* of $I$, denoted by ${\delta_{\mathcal{F}}}(I)$, to be the simplicial complex over a set of vertices ${v_1,\ldots,v_n}$ with facets ${F_1,\ldots,F_q}$, where for each $i$, $F_i=\{v_j {\ | \ }x_j|M_i, \ 1 \leq j \leq n
      \}$.

Throughout this paper we often use a letter $x$ to denote both a vertex of ${\Delta}$ and the corresponding variable appearing in ${{\mathcal{F}}}({\Delta})$, and $x_{i_1}\ldots x_{i_r}$ to denote a facet of ${\Delta}$ as well as a monomial generator of ${{\mathcal{F}}}({\Delta})$.

\[main-example\] If ${\Delta}$ is the simplicial complex ${\langle xyz,yzu,uv \rangle}$ drawn below, $$\includegraphics{india-facet.eps}$$ then ${{\mathcal{F}}}({\Delta})=(xyz,yuz,uv)$ is its facet ideal.

Facet ideals give a one-to-one correspondence between simplicial complexes and square-free monomial ideals.

Next we define the notion of a vertex cover. The combinatorial idea here comes from graph theory. In algebra, it corresponds to prime ideals lying over the facet ideal of a given simplicial complex.

\[unmixed\] Let $\Delta$ be a simplicial complex with vertex set $V$. A *vertex cover* for ${\Delta}$ is a subset $A$ of $V$ that intersects every facet of ${\Delta}$. If $A$ is a minimal element (under inclusion) of the set of vertex covers of ${\Delta}$, it is called a *minimal vertex cover*. The smallest of the cardinalities of the vertex covers of ${\Delta}$ is called the *vertex covering number* of ${\Delta}$ and is denoted by ${\alpha}({\Delta})$.

A simplicial complex $\Delta$ is *unmixed* if all of its minimal vertex covers have the same cardinality.

\[highlight-example\] If ${\Delta}$ is the simplicial complex in Example \[main-example\], then the vertex covers of ${\Delta}$ are: $${\bf
\{x,u\},\{y,u\},\{y,v\},\{z,u\},\{z,v\}},\{x,y,u\},\{x,z,u\},\{x,y,v\},
\ldots.$$ The first five vertex covers above (highlighted in bold), are the minimal vertex covers of ${\Delta}$.

In all the arguments in this paper, unless otherwise stated, $k$ denotes a field.

Given a square-free monomial ideal $I$ in a polynomial ring $k[{x_1,\ldots,x_n}]$, the vertices of ${\delta_{\mathcal{F}}}(I)$ are those variables that divide a monomial in the generating set of $I$; this set may not include all elements of $\{{x_1,\ldots,x_n}\}$. The fact that some extra variables may appear in the polynomial ring has little effect on the algebraic or combinatorial structure of ${\delta_{\mathcal{F}}}(I)$. On the other hand, if ${\Delta}$ is a simplicial complex, being able to consider the facet ideals of its subcomplexes as ideals in the same ambient ring simplifies many of our discussions. For this reason we make the following definition.

Let $I$ be a square-free monomial ideal in a polynomial ring $R=k[{x_1,\ldots,x_n}]$. A subset $A$ of the variables $\{{x_1,\ldots,x_n}\}$ is called a *(minimal) variable cover* of ${\Delta}={\delta_{\mathcal{F}}}(I)$ (or of $I$) if $A$ is the generating set for a (minimal) prime ideal of $R$ containing $I$.

If ${x_1,\ldots,x_n}$ are all vertices of ${\Delta}={\delta_{\mathcal{F}}}(I)$, then a variable cover of ${\Delta}$ is exactly the same as a vertex cover of ${\Delta}$. In general every variable cover of ${\Delta}$ contains a vertex cover of ${\Delta}$. For example for the ideal $I=(xy,xz) \subseteq k[x,y,z,u]$, $\{x,u\}$ is a variable cover but not a vertex cover. The minimal vertex covers of ${\Delta}$, however, are always the same as the minimal variable covers of ${\Delta}$.

We now construct a new simplicial complex using the minimal vertex covers of a given simplicial complex.

\[cover-complex\] Given a simplicial complex ${\Delta}$, the simplicial complex ${\Delta}_M$ called the *cover complex of* ${\Delta}$, is the simplicial complex whose facets are the minimal vertex covers of ${\Delta}$.

In Example \[highlight-example\], ${\Delta}={\langle xyz,yzu,uv \rangle}$ and ${\Delta}_M={\langle xu,yu,yv,zu,zv \rangle}.$

It is worth observing that ${\Delta}$ being unmixed is equivalent to ${\Delta_M}$ being *pure* (meaning that all facets of ${\Delta_M}$ are of the same dimension). This fact becomes useful in our discussions below. For example the simplicial complex ${\Delta}$ in Example \[highlight-example\] is unmixed, and ${\Delta_M}$ is pure.

The following fact is known in hypergraph theory (see, for example, \[B\]). We outline a proof below.

\[cover-complex-dual\] If ${\Delta}$ is a simplicial complex, then ${\Delta}_M$ is a dual of ${\Delta}$; i.e. ${\Delta}_{MM}={\Delta}.$

Suppose that ${\Delta}={\langle {F_1,\ldots,F_q}\rangle}$ and ${\Delta_M}={\langle {G_1,\ldots,G_p}\rangle}$. Suppose that for $i=1,\ldots,p$, $q_i$ is the prime ideal generated by the elements of $G_i$, so that we have $$I={{\mathcal{F}}}({\Delta})= q_1 \cap \ldots \cap q_p.$$

We first show that every facet of ${\Delta}$ is a vertex cover of ${\Delta_M}$. Consider the facet $F_1$. Since the monomial $F_1 \in q_i$ for all $i$, it follows that $F_1$ contains at least one vertex of each of the $G_i$. This proves that $F_1$ is a vertex cover of ${\Delta_M}$.

Suppose now that $F$ is any minimal vertex cover of ${\Delta_M}$. Since $F$ contains a vertex of each of the $G_i$, it belongs to all the ideals $q_i$ (if we consider $F$ as a monomial), and therefore $F \in I$. So some generator $F_j$ of $I$ must divide $F$. This means that $F_j
             \subseteq F$, but since $F_j$ is already a vertex cover of ${\Delta_M}$, it follows that $F=F_j$. This shows that ${F_1,\ldots,F_q}$ are all the minimal vertex covers of ${\Delta_M}$.

Relations to Stanley-Reisner theory {#dualities-section}
===================================

We begin by the basic definitions from Stanley-Reisner theory. For a detailed coverage of this topic, we refer the reader to \[BH\].

\[nonface-ideal\] Let $k$ be a field and ${x_1,\ldots,x_n}$ be a set of indeterminates, and $R=k[{x_1,\ldots,x_n}]$ be a polynomial ring.

-   Let $\Delta$ be a simplicial complex over $n$ vertices labeled ${v_1,\ldots,v_n}$. We define the *nonface ideal* or the *Stanley-Reisner ideal* of $\Delta$, denoted by ${{\mathcal{N}}}(\Delta)$, to be the ideal of $R$ generated by square-free monomials $x_{i_1}\ldots x_{i_s}$, where $\{v_{i_1},\ldots, v_{i_s}\}$ is not a face of $\Delta$.

-   Let $I=({M_1,\ldots,M_q})$ be an ideal in $R$, where ${M_1,\ldots,M_q}$ are square-free monomials in ${x_1,\ldots,x_n}$ that form a minimal set of generators for $I$. We define the *nonface complex* or the *Stanley-Reisner complex* of $I$, denoted by ${\delta_{\mathcal{N}}}(I)$, to be the simplicial complex over a set of vertices ${v_1,\ldots,v_n}$, where $\{v_{i_1},\ldots, v_{i_s}\}$ is a face of ${\delta_{\mathcal{N}}}(I)$ if and only if $x_{i_1}\ldots x_{i_s} \notin I$.

\[notation\] To simplify notation, we use ${\Delta_N}$ to mean the nonface complex of ${{\mathcal{F}}}({\Delta})$ for a given simplicial complex ${\Delta}$. In other words, we set $${\Delta_N}= {\delta_{\mathcal{N}}}({{\mathcal{F}}}({\Delta})).$$

Given an ideal $I \subseteq k[V]$ where $V=\{{x_1,\ldots,x_n}\}$, if there is no reason for confusion, we use ${\Delta}$ and ${\Delta_N}$ to denote ${\delta_{\mathcal{F}}}(I)$ and ${\delta_{\mathcal{N}}}(I)$, respectively. If $F$ is a face of ${\Delta}={\langle {F_1,\ldots,F_q}\rangle}$, we let the *complements* of $F$ and ${\Delta}$ be

${{F}^c}=V\setminus F$ and ${{{\Delta}}^c}={\langle {{F_1}^c},\ldots,{{F_q}^c} \rangle}$.

\[alex\] Let $I$ be a square-free monomial ideal in the polynomial ring $k[V]$ with $V=\{{x_1,\ldots,x_n}\}$. Then the *Alexander dual* of ${\Delta_N}$ is the simplicial complex $${{{\Delta_N}{}^{\vee}}} = \{ F \subset V {\ | \ }{{F}^c} \notin {\Delta_N}\}.$$

It is easy to see that ${{{{{\Delta_N}{}^{\vee}}}{}^{\vee}}} = {\Delta_N}$.

We now focus on the relations between ${\Delta}$ and ${\Delta_N}$ for a given square-free monomial ideal $I$. The first question we tackle is how to construct ${\Delta_N}$ from ${\Delta}$.

\[duality-relations\] Given a simplicial complex ${\Delta}$, we have

1.  ${\Delta_N}={{{\Delta_M}}^c}$;

2.  ${{{{\Delta_N}}{}^{\vee}}}= {{\Delta_M}}_N={{{\Delta}}^c}$.

<!-- -->

1.  This is easy to check. See, for example, \[BH\] Theorem 5.1.4.

2.  The last equality follows from Proposition \[cover-complex-dual\] and Part (a), since $${{\Delta_M}}{}_N = {{{{\Delta_M}}{}_M}^c}=
                 {{{\Delta}}^c}.$$

    We translate both sides of the first equation using the notations in \[notation\] and Definition \[alex\]:

    ${{{\Delta_N}{}^{\vee}}}=\{{{F}^c} {\ | \ }F \notin {\Delta_N}\}$ and $ {\Delta}^c= {\langle {{F}^c} {\ | \ }F {\rm \ is \ a \ facet\  of\ } {\Delta}\rangle}$.

    Suppose that ${{F}^c} \in {{{\Delta_N}{}^{\vee}}}$. Then $F \notin {\Delta_N}$, and therefore if $f$ denotes the monomial that is the product of the vertices of $F$, and $I={{\mathcal{N}}}({\Delta_N})$, then $f \in I$. It follows that for some generator $g$ of $I$, $g |f$. If $G$ is the facet of ${\Delta}$ corresponding to $g$, we have $G
                \subseteq F$, which implies that ${{F}^c} \subseteq {{G}^c}$; so ${{F}^c} \in {{{\Delta}}^c}$.

    Conversely, let $G \in {{{\Delta}}^c}$. Then $G \subseteq
                {{F}^c}$, where $F$ is a facet of ${\Delta}$, so $f \in I$ which implies that $F \notin {\Delta_N}$. So ${{F}^c} \in {{{\Delta_N}{}^{\vee}}}$, which implies that $G\in {{{\Delta_N}{}^{\vee}}}$.

Proposition \[duality-relations\] is basically saying that the relationship between ${\Delta_M}$ and ${{{\Delta_N}{}^{\vee}}}$ is the same as the relationship between ${\Delta}$ and ${\Delta_N}$. The example below clarifies this point.

\[diagram-example\] Let $I=(xyz,zu) \subseteq k[x,y,z,u]$. Then the *dual* ideal of $I$, which is the facet ideal of ${\Delta_M}$, or equivalently the nonface ideal of ${{{\Delta_N}{}^{\vee}}}$, is the ideal $J=(xu,yu,z)$. The relationship between the four simplicial complexes and the two ideals is shown in Figure \[diagram\].

$$\includegraphics{diagram.eps}$$

Proposition \[duality-relations\] justifies the following definition.

\[dual-ideal\] Given a square-free monomial ideal $I$ in a polynomial ring and ${\Delta}={\delta_{\mathcal{F}}}(I)$, we define the $dual$ of $I$, denoted by ${{{I{}^{\vee}}}}$, to be the facet ideal of ${\Delta_M}$, or equivalently, the nonface ideal of ${{{\Delta_N}{}^{\vee}}}$. So $${{{I{}^{\vee}}}}={{\mathcal{F}}}({\Delta_M})={{\mathcal{N}}}({{{\Delta_N}{}^{\vee}}}).$$

We now state a criterion for the Cohen-Macaulayness of a square-free monomial ideal that is due to Eagon and Reiner (\[ER\]) in the language stated above. First we define an ideal with a linear resolution.

An ideal $I$ in a polynomial ring $R=k[{x_1,\ldots,x_n}]$ over a field $k$, with the standard grading $\deg(x_i)=1$ for all $i$, is said to have a *linear resolution* if $R/I$ has a minimal free resolution such that for all $j>1$ the nonzero entries of the matrices of the maps $R^{\beta_j} \longrightarrow
  R^{\beta_{j-1}}$ are of degree 1.

\[eagon-reiner\] Let $I$ be a square-free monomial ideal in a polynomial ring $R$. Then $R/I$ is Cohen-Macaulay if and only if ${{{I{}^{\vee}}}}$ has a linear resolution.

Simplicial Trees {#trees-section}
================

Considering simplicial complexes as higher dimensional graphs, one can define the notion of a *tree* by extending the same concept from graph theory. Simplicial trees were first introduced in \[F1\] in order to generalize results of \[SVV\] on facet ideals of graph-trees. The construction turned out to have interesting additional combinatorial and algebraic properties.

Before we define a tree, we determine what “removing a facet” from a simplicial complex means. We define this idea so that it corresponds to dropping a generator from its facet ideal.

\[removal\] Suppose $\Delta$ is a simplicial complex with facets ${F_1,\ldots,F_q}$ and ${{\mathcal{F}}}(\Delta)=({M_1,\ldots,M_q})$ its facet ideal in $R=k[{x_1,\ldots,x_n}]$. The simplicial complex obtained by *removing the facet* $F_i$ from $\Delta$ is the simplicial complex $${\Delta}{\setminus \langle F_i\rangle}={\langle F_1,\ldots,\hat{F}_{i},\ldots,F_q \rangle}.$$

Note that ${{\mathcal{F}}}({\Delta}{\setminus \langle F_i\rangle}) = (M_1,\ldots,\hat{M}_{i} ,\ldots,M_q)$.

Also note that the vertex set of ${\Delta}{\setminus \langle F_i\rangle}$ is a subset of the vertex set of ${\Delta}$.

Let ${\Delta}$ be a simplicial complex with facets $F=\{x,y,z\}$, $G=\{y,z,u\}$ and $H=\{u,v\}$. Then ${\Delta}{\setminus \langle F\rangle} ={\langle G,H \rangle}$ is a simplicial complex with vertex set $\{y,z,u,v\}$.

In graph theory, a tree is defined as a connected cycle-free graph. An equivalent definition is that a tree is a connected graph whose every subgraph has a *leaf*, where a leaf is a vertex that belongs to only one edge. We make an analogous definition for simplicial complexes by extending (and slightly changing) the definition of a leaf.

A facet $F$ of a simplicial complex is called a *leaf* if either $F$ is the only facet of $\Delta$, or for some facet $G \in \Delta {\setminus \langle F\rangle}$ we have $$F \cap ({\Delta}{\setminus \langle F\rangle}) \subseteq G.$$

Equivalently, the facet $F$ is a leaf of ${\Delta}$ if $F \cap ({\Delta}{\setminus \langle F\rangle})$ is a face of ${\Delta}{\setminus \langle F\rangle}$.

\[leaf-example\] Let $I=(xyz,yzu,zuv)$. Then $F=xyz$ is a leaf, but $H=yzu$ is not, as one can see in the picture below.

$$\begin{tabular}{ccccc}
  \includegraphics{leaf1.eps} &$\cap$ &\includegraphics{rmv1.eps} &= &
\includegraphics{intersect1.eps} \\
&&&&\\
\includegraphics{leaf2.eps} &$\cap$ &\includegraphics{rmv2.eps} &= &
\includegraphics{intersect2.eps}
\end{tabular}$$

\[tree-def\] A connected simplicial complex $\Delta$ is a *tree* if every nonempty subcollection of $\Delta$ has a leaf. If ${\Delta}$ is not necessarily connected, but every subcollection has a leaf, then ${\Delta}$ is called a forest.

\[free-example\] The simplicial complexes in examples \[main-example\] and \[leaf-example\] are both trees, but the one below is not because it has no leaves. It is an easy exercise to see that a leaf must contain a free vertex, where a vertex is *free* if it belongs to only one facet. $$\includegraphics{not-a-tree.eps}$$

An effective way to make algebraic arguments on trees is using localization. It turns out that the minimal generating set of a localization of the facet ideal of a tree corresponds to a forest. As we shall see below, this fact makes it easy to use induction on the number of vertices of a tree.

For details on the localization of s simplicial complex see \[F2\]. Here we give an example to clarify what we mean by localization.

\[local-example\] Let ${\Delta}$ be the simplicial complex below with $I=(xyz,yzu,yuv)$ its facet ideal in the polynomial ring $R=k[x,y,z,u,v]$.

$$\includegraphics{basic-tree.eps}$$

Let $p=(x,u,z)$ be a prime ideal of $R$. Then $I_p=(xz,zu,u)=(xz,u)$ is the facet ideal of the forest below on the left. If $q= (y,z,v)$ then $I_q=(yz,yz,yv)=(yz,yv)$ corresponds to the tree on the right.

$$\begin{tabular}{lclc}
Localization at $p$:&
\includegraphics{localize-1.eps}&
\hspace{.2in}Localization at $q$:&
\includegraphics{localize-2.eps}
\end{tabular}$$

Example \[local-example\] is an example of the following general fact.

\[localization\] Let $I \subseteq k[{x_1,\ldots,x_n}]$ be the facet ideal of a tree, where $k$ is a field, and suppose that $p$ is a prime ideal of $k[{x_1,\ldots,x_n}]$. Then for any prime ideal $p$ of $R$, ${\delta_{\mathcal{F}}}(I_p)$ is a forest.

See \[F2\] Lemma 4.5.

Sequentially Cohen-Macaulay simplicial complexes {#sequential-section}
================================================

The notion of a sequentially Cohen-Macaulay ideal was introduced by Stanley following the introduction of nonpure shellability by Björner and Wachs \[BW\]. It was known that every shellable simplicial complex (which was by definition pure) was Cohen-Macaulay, but what about nonpure shellable simplicial complexes? As it turns out, “sequentially Cohen-Macaulay” is the correct notion to fill in the gap here. On the other hand, the criterion of Eagon and Reiner (\[ER\]) stated that a simplicial complex is Cohen-Macaulay if and only if its Alexander dual has a linear resolution. Herzog and Hibi (\[HH\]) developed the definition of a “componentwise linear ideal” so that the above criterion extended to sequentially Cohen-Macaulay ideals: a simplicial complex is sequentially Cohen-Macaulay if and only if its Alexander dual is componentwise linear.

In our setting, we use an equivalent characterization of sequentially Cohen-Macaulay given by Duval, along with Theorem \[eagon-reiner\] and the relationship between Alexander duality and cover complex duality discussed in Section \[dualities-section\], to prove that simplicial trees are sequentially Cohen-Macaulay. In fact, we show that if $I$ is the facet ideal of a simplicial tree, then the dual ${{{I{}^{\vee}}}}$ of $I$ has “square-free homogeneous components” with *linear quotients*. This property is slightly stronger than what we need, and it shows that if $I$ is a Cohen-Macaulay ideal to begin with, then ${\Delta_N}$ is shellable (which was known for the case where ${\Delta}$ is a graph; Theorem 6.4.7 of \[V\]).

Another outcome is the fact that an unmixed tree is Cohen-Macaulay (Corollary \[F2-cor\]), which was shown in \[F2\] using very different tools.

\[scm-def\] Let $M$ be a finitely generated ${\mathbb{Z}}$-graded module over a finitely generated ${\mathbb{N}}$-graded $k$-algebra, with $R_0=k$. We say that $M$ is *sequentially Cohen-Macaulay* if there exists a finite filtration $$0=M_0 \subseteq M_1 \subseteq \ldots \subseteq M_r=M$$ of $M$ by graded submodules $M_i$ satisfying the following two conditions.

1.  Each quotient $M_i/M_{i-1}$ is Cohen-Macaulay.

2.  ${ {\rm{dim}} \ }(M_1/M_0) < { {\rm{dim}} \ }(M_2/M_1) < \ldots < { {\rm{dim}} \ }(M_r/M_{r-1})$, where ${ {\rm{dim}} \ }$ denotes Krull dimension.

A simplicial complex is said to be *sequentially Cohen-Macaulay* if its Stanley-Reisner ideal has a sequentially Cohen-Macaulay quotient.

The following characterization of a sequentially Cohen-Macaulay simplicial complex given by Duval (\[D\] Theorem 3.3) is what we use in this paper.

\[scm\] Let $I$ be square-free monomial ideal $I$ in a polynomial ring $R$ over a field $k$, and let ${\Delta_N}={\delta_{\mathcal{N}}}(I)$. Then $R/I$ is sequentially Cohen-Macaulay if and only if for every $i$, $-1 \leq i \leq { {\rm{dim}} \ }{\Delta_N}$, if ${\Delta_{N,\ i}}$ is the pure $i$-dimensional subcomplex of ${\Delta_N}$, then $R/{{\mathcal{N}}}({\Delta_{N,\ i}})$ is Cohen-Macaulay.

\[SCM-example\] let $I=(xyz,zu)$ be the ideal of Example \[diagram-example\] in the diagram above. Then for $i=0,1,2$, we have the following three simplicial complexes, respectively, $$\includegraphics{0-component.eps} \hspace{1in}
\includegraphics{1-component.eps} \hspace{1in}
\includegraphics{2-component.eps}$$ which are, respectively, the nonface complexes of the ideals $I_0=(xy,xz,xu,yz,yu,zu)$, $I_1=(xyz,xyu,zu)$ and $I_2=(z)$. One can verify that all three of these ideals have Cohen-Macaulay quotients, so $I$ is sequentially Cohen-Macaulay.

We define a componentwise linear ideal in the square-free case using \[HH\] Proposition 1.5.

\[comp-def\] Let $I$ be a square-free monomial ideal in a polynomial ring $R$. For a positive integer $k$, the $k$-th *square-free homogeneous component* of $I$, denoted by $I_{[k]}$ is the ideal generated by all square-free monomials in $I$ of degree $k$. The ideal $I$ above is said to be *componentwise linear* if for all $k$, the square-free homogeneous component $I_{[k]}$ has a linear resolution.

Let $${\Delta}={\langle {F_1,\ldots,F_q}\rangle}$$ be a simplicial complex with ${{\mathcal{F}}}({\Delta})
        \subseteq k[V]$, $V=\{{x_1,\ldots,x_n}\}$, and let $${\Delta_M}={\langle {G_1,\ldots,G_p}\rangle}$$ be its cover complex . Then by Proposition \[duality-relations\] we know that $${\Delta_N}={\langle {{G_1}^c},\ldots,{{G_p}^c} \rangle}.$$ For a given $i$, consider the pure $i$-dimensional subcomplex of ${\Delta_N}$ $${\Delta_{N,\ i}}={\langle H_1,\ldots,H_u \rangle}.$$ By Theorem \[eagon-reiner\] showing that $I_i= {{\mathcal{N}}}({\Delta_{N,\ i}})$ is a Cohen-Macaulay ideal is equivalent to showing that ${{I_i{}^{\vee}}}$ has a linear resolution. By Proposition \[duality-relations\], ${{I_i{}^{\vee}}}$ is the facet ideal of ${{{\Delta_{N,\ i}}}^c}$.

So we focus on ${{H}^c}$, where $H$ is a facet of ${\Delta_{N,\ i}}$. Since $H$ belongs to a subcomplex of ${\Delta_N}$, for some facet ${{G_j}^c}$ of ${\Delta_N}$, $H \subseteq {{G_j}^c}$. This implies that $G_j={{{{G_j}^c}}^c} \subseteq {{H}^c}$; i.e. ${{H}^c}$ contains a minimal vertex cover of ${\Delta}$, and so ${{H}^c}$ is a variable cover of ${\Delta}$ of cardinality $n-(i+1)$.

Similarly, if $G$ is a variable cover of cardinality $n-(i+1)$ of ${\Delta}$, then one can see that ${{G}^c}$ is a facet of ${\Delta_{N,\ i}}$.

The discussion above shows that ${{I_i{}^{\vee}}}$ is generated by monomials corresponding to variable covers of cardinality $n-i-1$ of ${\Delta}$. In other words $${{I_i{}^{\vee}}}={{{I{}^{\vee}}}}_{[n-i-1]},$$ where ${{{I{}^{\vee}}}}_{[j]}$ denotes the $j$-th square-free homogeneous component of ${{{I{}^{\vee}}}}$, and showing that ${\Delta_{N,\ i}}$ is Cohen-Macaulay is equivalent to showing that ${{{I{}^{\vee}}}}_{[n-i-1]}$ has a linear resolution.

We have thus shown that:

\[scm-criterion\] Let $I$ be a square-free monomial ideal in a polynomial ring. Then $I$ is a sequentially Cohen-Macaulay ideal if and only if ${{{I{}^{\vee}}}}$ is componentwise linear.

Simplicial trees are Sequentially Cohen-Macaulay {#trees-scm-section}
================================================

This section contains the main results of the paper. Our goal here is to show that the facet ideal $I$ of a simplicial tree is sequentially Cohen-Macaulay. By Proposition \[scm-criterion\] this is equivalent to showing that the facet ideal ${{{I{}^{\vee}}}}$ of the cover complex of a tree is componentwise linear (Definition \[comp-def\]). In fact, we show that ${{{I{}^{\vee}}}}$ satisfies a stronger property: for every $i$, we show below that ${{{{I{}^{\vee}}}}_{[i]}}$ has linear quotients. This property, defined by Herzog and Takayama in \[HT\], implies that ${{{{I{}^{\vee}}}}_{[i]}}$ has a linear resolution. It also implies additional combinatorial properties for $I$ (see Corollary \[shellabale-cor\]).

\[linear-quotients-def\] If $I \subset k[{x_1,\ldots,x_n}]$ is a monomial ideal and $G(I)$ is its unique minimal set of monomial generators, then $I$ is said to have *linear quotients* if there is an ordering ${M_1,\ldots,M_q}$ on the elements of $G(I)$ such that for every $i=2,\ldots,q$, the quotient ideal $$(M_1,\ldots,M_{i-1}):M_i$$ is generated by a subset of the variables ${x_1,\ldots,x_n}$.

The following is a well-known fact. We reproduce an argument (almost identical to one given in \[Z\] for the case of trees).

\[quotient-resolution\] If $I=({M_1,\ldots,M_q})$ is a monomial ideal in the polynomial ring $R=k[{x_1,\ldots,x_n}]$ over the field $k$ that has linear quotients and all the $M_i$ are of the same degree, then $I$ has a linear resolution.

The proof is by induction on $q$. The case $q=1$ is clear. Given that the ideal $I'=(M_1,\ldots,M_{q-1})$ has linear quotients and therefore a linear resolution, and that the degree of all the $M_i$ is equal to $d$, we have that (see Section 5.5 of \[BH\]) for all $i$:

  --------------------------------------- -------------------------------------------------------------
  ${{\rm Tor}_{i}^{R}\ }(k,R/I')_a=0$     unless $a= i+d$;
  ${{\rm Tor}_{i}^{R}\ }(k,R/I':I)_a=0$   unless $a=i+1$ ($I':I$ is generated by degree 1 monomials).
  --------------------------------------- -------------------------------------------------------------

Consider the short exact sequence: $$0\longrightarrow
                R/(I':I) (-d) )\stackrel{.M_q}{\longrightarrow} R/I'
                \longrightarrow R/I \longrightarrow 0$$

We obtain the long exact homology sequence: $$\cdots \longrightarrow {{\rm Tor}_{i}^{R}\ }(k,R/(I':I)(-d))
               \longrightarrow {{\rm Tor}_{i}^{R}\ }(k,R/I')\longrightarrow
               {{\rm Tor}_{i}^{R}\ }(k,R/I)$$ $$\longrightarrow
               {{\rm Tor}_{i-1}^{R}\ }(k,R/(I':I)(-d)) \longrightarrow \cdots$$

For a given $i$, ${{\rm Tor}_{i}^{R}\ }(k,R/I)_a=0$ unless $${{\rm Tor}_{i}^{R}\ }(k,R/I')_a \neq0 \ {\rm or \ }
               {{\rm Tor}_{i-1}^{R}\ }(k,R/(I':I))(-d)_a \neq 0.$$ Either way, this means that for any $i$, if ${{\rm Tor}_{i}^{R}\ }(k,R/I)_a
               \neq 0$, then $a=i+d$. This implies that $R/I$ has a linear resolution.

We now set out to prove if $I \subseteq k[V]$, $V=\{{x_1,\ldots,x_n}\}$, is the facet ideal of a tree (in fact, a forest) ${\Delta}$, and $i$, ${\alpha}({\Delta})
  \leq i \leq n$, is a given integer, then ${{{{I{}^{\vee}}}}_{[i]}}$ has linear quotients.

We use induction on $n$. If $n=1$, ${\Delta}$ can only be the vertex ${\langle x_1 \rangle}$, and so the only thing to check is if ${{{{I{}^{\vee}}}}}_{[1]}=(x_1)$ has linear quotients, which is obvious.

Suppose that $n>1$. We first deal with some special cases. If ${\Delta}$ is a forest of singletons of the form $${\Delta}={\langle x_1,\ldots,x_j \rangle}$$ where $j<n$, then we can consider $I'={{\mathcal{F}}}({\Delta})$ as an ideal in the polynomial ring $R'=k[x_1,\ldots,x_{n-1}]$ ($I$ and $I'$ have the same generating set, they only live in two different rings). By the induction hypothesis, for every $i$, ${{I'{}^{\vee}}} _ {[i]}$ has linear quotients.

It is easy to see that for every $i$, $${{{I{}^{\vee}}}}_{[i]}= {{I'{}^{\vee}}} _ {[i]} +
x_n {{I'{}^{\vee}}} _ {[i-1]}.$$ Suppose that $${{I'{}^{\vee}}}_ {[i]}=(A_1,\ldots,
A_a) {\rm \ and \ } {{I'{}^{\vee}}} _ {[i-1]}=(B_1,\ldots,B_b)$$ where the generators of both ideals are written in the correct order for linear quotients (recall that we are using the notation $xA$ to mean $\{x\}
\cup A$, since generally we are always thinking of sets as monomials). To see that $${{{I{}^{\vee}}}}_{[i]}=(A_1,\ldots, A_a) + x_n(B_1,\ldots,B_b)$$ has linear quotients, we consider the case where for some monomial $m$ in $k[{x_1,\ldots,x_n}]$ (we can without loss of generality assume here that the products are square-free), $$mx_nB_j \in (A_1,\ldots, A_a,x_nB_1,\ldots,x_nB_{j-1}).$$ If $mx_nB_j \in (x_nB_1,\ldots,x_nB_{j-1})$, since ${{I'{}^{\vee}}} _ {[i-1]}$ has linear quotients, it follows that for some variable $z$ dividing the monomial $m$, we have $zx_nB_j \in (x_nB_1,\ldots,x_nB_{j-1})$ (note that $m \neq 1)$.

If $mx_nB_j \in (A_1,\ldots, A_a)$, then since $B_j$ is already a variable cover of ${\Delta}$, for any variable $z$ not in $B_j$, $zB_j$ covers ${\Delta}$ and is of cardinality $i$, and hence $zB_j \in
\{A_1,\ldots, A_a\}$. Therefore for any $z$ dividing $m$ we can again conclude that $zx_nB_j \in (A_1,\ldots, A_a)$.

This argument settles the case where ${\Delta}={\langle x_1,\ldots,x_j \rangle}$, and $j<n$.

If ${\Delta}={\langle {x_1,\ldots,x_n}\rangle}$, then the only ideal to consider is ${{{I{}^{\vee}}}}_{[n]}=(x_1\ldots x_n)$ which by definition has linear quotients.

So now we can assume that ${\Delta}$ is a forest containing a facet with more than one vertex.

We begin our discussion with the following simple observation.

\[D’-lemma\] Let ${\Delta}$ be a simplicial complex with ${{\mathcal{F}}}({\Delta})\subseteq k[V]$, $k$ a field, and $V=\{{x_1,\ldots,x_n}\}$. Suppose that $x
   \in V$ is such that $V \setminus \{x\}$ is a variable cover for ${\Delta}$, and let $p_x$ be the prime ideal generated by the set $V
   \setminus \{x\}$. Then localizing ${\Delta}$ at $p_x$ corresponds, via the cover duality, to removing all facets of ${\Delta_M}$ that contain $x$. In other words, if ${\Delta}'={\delta_{\mathcal{F}}}({{\mathcal{F}}}({\Delta})_{p_x})$ and ${A_1,\ldots,A_t}$ are the facets of ${\Delta_M}$ that contain $x$, then $${\Delta}'_M = {\Delta_M}{\setminus \langle {A_1,\ldots,A_t}\rangle}.$$

Note that a facet of ${\Delta}'_M$ is the generating set for a minimal prime of $I={{\mathcal{F}}}({\Delta})$ not containing $x$, and therefore belongs to ${\Delta_M}$ as well. Conversely, if $A$ is a facet of the right-hand-side, then it corresponds to a minimal prime of $I$ not containing $x$ and hence to a minimal prime of $I_{p_x}$.

Now assume that the forest ${\Delta}$ has a leaf $F$ with positive dimension and a free vertex (see Example \[free-example\]) $x=x_1$. We can write: $${\Delta_{M,\ [i]}}={\delta_{\mathcal{F}}}({{{{I{}^{\vee}}}}_{[i]}})= {\langle {A_1,\ldots,A_t}\rangle} \cup {\langle xB_1,\ldots,xB_s \rangle}$$ where ${A_1,\ldots,A_t}$ are all the variable covers of ${\Delta}$ that have cardinality $i$ and do not contain $x$, and $xB_1,\ldots,xB_s$ are all the other variable covers of cardinality $i$.

Now let $${\Delta}'={\delta_{\mathcal{F}}}({{\mathcal{F}}}({\Delta})_{p_x}) \ {\rm \ and }\ \ {\Delta}''= {\Delta}{\setminus \langle F\rangle}.$$ Both ${\Delta}'$ and ${\Delta}''$ are forests (by the definition of a tree, and by Lemma \[localization\]) whose vertex sets are contained in $\{x_2,\ldots,x_n\}$. Also note that ${\Delta}'$ is a nonempty simplicial complex.

With notation as above, by Lemma \[D’-lemma\] $${\Delta}'_{M,\
[i]}={\langle {A_1,\ldots,A_t}\rangle}.$$

Also notice that $${\Delta}''_{M,\ [i-1]}={\langle {B_1,\ldots,B_s}\rangle}.$$ To see this last equation, note that since for $j=1,\ldots,s$, $xB_j$ covers ${\Delta}$, $B_j$ has to cover ${\Delta}''$ (as $x$ is a free vertex of $F$ and hence only covers $F$). On the other hand, if $A$ is any variable cover of ${\Delta}''$ of cardinality $i-1$, then $xA$ is in ${\Delta_{M,\ [i]}}$, and so $xA \in
\{xB_1,\ldots,xB_s\}$.

Applying the induction hypothesis to the forests ${\Delta}'$ and ${\Delta}''$ we see that the ideals

${{{I'{}^{\vee}}}}_{[i]}=({A_1,\ldots,A_t})$ and ${{{I''{}^{\vee}}}}_{[i-1]}=({B_1,\ldots,B_s})$

of $k[x_2,\ldots,x_n]$ both have linear quotients. Without loss of generality assume that the given orders on the $A$’s and the $B$’s are appropriate for taking quotients. We show that the ideal $${{{{I{}^{\vee}}}}}_{[i]}=({A_1,\ldots,A_t})+ x({B_1,\ldots,B_s})$$ also has linear quotients. Here we assume that $1 < i <n$, since ${{{{I{}^{\vee}}}}}_{[n]}=(x_1 \ldots x_n)$ has linear quotients by definition, as does ${{{{I{}^{\vee}}}}}_{[1]}$ which is, if nonzero, generated by a subset of $\{{x_1,\ldots,x_n}\}$.

The first case of interest is the ideal $$({A_1,\ldots,A_t}): xB_1.$$ Now $B_1$ is a variable cover of ${\Delta}''= {\Delta}{\setminus \langle F\rangle}$, so $yB_1 \in {{{I{}^{\vee}}}}_{[i]}$ for any vertex $y$ of $F$ not in $B_1$. So if $m$ is any monomial such that $mxB_1 \in {{{I'{}^{\vee}}}}_{[i]}$, then for some monomial $n$ and some $j$, assuming without loss of generality that both products below are square-free, we have $$mxB_1 =nA_j.$$ If $B_1$ already contains a vertex of $F$, then it is a variable cover of cardinality $i-1$ for ${\Delta}'$, and so for any $y|m$, $yB_1 \in \{{A_1,\ldots,A_t}\}$. Otherwise, since there is some vertex $y$ of $F$ in $A_j$, $y$ has to divide $m$, which again implies that $yxB_1 \in
({A_1,\ldots,A_t})$.

In general, for the ideal $$({A_1,\ldots,A_t},xB_1,\ldots,xB_{j-1}):xB_j$$ if for some monomial $m$, $mxB_j
\in (xB_1,\ldots,xB_{j-1})$, then by the induction hypothesis on ${{{I''{}^{\vee}}}}_{[i-1]}$ there is a variable $y$ that divides $m$ such that $yxB_j \in (xB_1,\ldots,xB_{j-1})$.

If $mxB_j \in ({A_1,\ldots,A_t})$, then it follows from an argument identical to the case $j=1$ above that there is a variable $y$ dividing $m$ such that $yxB_j \in ({A_1,\ldots,A_t})$.

We have thus proved that:

\[linear-quotient-theorem\] If $I \subseteq k[{x_1,\ldots,x_n}]$ is the facet ideal of a simplicial tree (forest) ${\Delta}$, then ${{{{I{}^{\vee}}}}_{[i]}}$ has linear quotients for all $i={\alpha}({\Delta}),\ldots,n$.

Theorem \[linear-quotient-theorem\] along with Lemma \[quotient-resolution\] result in the following statement.

\[componentwise-corollary\] If ${\Delta}$ is a simplicial tree (forest), then ${{{{\mathcal{F}}}({\Delta}){}^{\vee}}}$ is a componentwise linear ideal.

Putting Corollary \[componentwise-corollary\] together with Proposition \[scm-criterion\], we arrive at our final goal.

\[main-result\] The facet ideal of a simplicial tree (forest) is sequentially Cohen-Macaulay.

The ideal $I$ in Example \[SCM-example\] is sequentially Cohen-Macaulay because it is the facet ideal of a tree.

It follows easily that if the tree ${\Delta}$ is unmixed to begin with, then it must be Cohen-Macaulay. This is because in this case ${{{{\mathcal{F}}}({\Delta}){}^{\vee}}}$ itself is a square-free homogeneous component, which has a linear resolution. So by applying Theorem \[eagon-reiner\] we have

\[F2-cor\] If ${\Delta}$ is an unmixed simplicial tree, then ${{\mathcal{F}}}({\Delta})$ has a Cohen-Macaulay quotient.

Corollary \[F2-cor\] was proved in \[F2\] using very different tools. In particular, in \[F2\] we show that a tree is unmixed if and only if it is “grafted”. The notion of grafting is what gives a Cohen-Macaulay tree its definitive combinatorial structure.

Another interesting fact that follows is that in the case of a simplicial tree ${\Delta}$, if ${\Delta}$ is Cohen-Macaulay, then ${\Delta_N}$ is shellable (see \[BH\] for the definition). Given a square-free monomial ideal $I$, if ${\delta_{\mathcal{N}}}(I)$ is shellable, then $I$ is Cohen-Macaulay (see \[BH\]), but the converse is not true in general.

\[shellabale-cor\] If ${\Delta}$ is a Cohen-Macaulay simplicial tree, then ${\Delta}_N$ is shellable.

If $I={{\mathcal{F}}}({\Delta})$ is Cohen-Macaulay, then by Theorem \[linear-quotient-theorem\], ${{{I{}^{\vee}}}}$ has linear quotients (since it has generators of the same degree). The rest follows directly from the definitions of shellability and linear quotients; see \[HHZ\] Theorem 1.4, part (c).

  ---------------------------------------- ----------------------------------------------------- ------------------------------

  [**Notation**]{}                         [**Meaning**]{}                                       [**First appearance**]{}

  ${{\mathcal{F}}}({\Delta})$              facet ideal of ${\Delta}$                             Definition \[facet-ideal\]
  ${\delta_{\mathcal{F}}}(I)$              facet complex of $I$                                  Definition \[facet-ideal\]
  ${\alpha}({\Delta})$                     vertex covering number of ${\Delta}$                  Definition \[unmixed\]
  ${\Delta_M}$                             cover complex of ${\Delta}$                           Definition \[cover-complex\]
  ${{\mathcal{N}}}({\Delta})$              nonface ideal of ${\Delta}$                           Definition \[nonface-ideal\]
  ${\delta_{\mathcal{N}}}(I)$              nonface complex of $I$                                Definition \[nonface-ideal\]
  ${\Delta_N}$                             ${\delta_{\mathcal{N}}}({{\mathcal{F}}}({\Delta}))$   Notation \[notation\]
  ${{F}^c}$, ${{{\Delta}}^c}$              complements of $F$ and ${\Delta}$                     Notation \[notation\]
  ${{{\Delta}{}^{\vee}}}$                  Alexander dual of ${\Delta}$                          Definition \[alex\]
  ${{{I{}^{\vee}}}}$                       dual of $I$                                           Definition \[dual-ideal\]
  ${\Delta}{\setminus \langle F\rangle}$   removal of facet $F$ from ${\Delta}$                  Definition \[removal\]
  ${\Delta_{N,\ i}}$                       pure $i$-dimensional subcomplex of ${\Delta_N}$       Theorem \[scm\]
  $I_{[i]}$                                $i$-th square-free homogeneous component of $I$       Definition \[comp-def\]
  $p_x$                                    ideal generated by all variables but $x$              Lemma \[D’-lemma\]
  ${\Delta_{M,\ [i]}}$                     facet complex of ${{{{I{}^{\vee}}}}_{[i]}}$           following Lemma \[D’-lemma\]

  ---------------------------------------- ----------------------------------------------------- ------------------------------

[1234]{}

Berge, C. *Hypergraphs, Combinatorics of finite sets*, North-Holland Mathematical Library, 45. North-Holland Publishing Co., Amsterdam, 1989.

Bruns, W., Herzog, J. *Cohen-Macaulay rings*, vol. 39, Cambridge studies in advanced mathematics, revised edition, 1998.

Björner, A., Wachs, M.L. *Shellable nonpure complexes and posets*, I. Trans. Amer. Math. Soc. 348 (1996), no. 4, 1299–1327.

Duval, A.M. *Algebraic shifting and sequentially Cohen-Macaulay simplicial complexes*, Electron. J. Combin. 3 (1996), no. 1, Research Paper 21

Eagon J.A., Reiner, V. *Resolution of Stanley-Reisner rings and Alexander duality*, J. Pure Appl. Algebra 130 (1998), no. 3, 265–275.

Faridi, S. *The facet ideal of a simplicial complex*, Manuscripta Mathematica 109 (2002), 159-174.

Faridi, S. *Cohen-Macaulay properties of square-free monomial ideals*, Preprint.

Herzog, J., Hibi, T. *Componentwise linear ideals*, Nagoya Math. J. 153 (1999), 141–153.

Herzog, J., Hibi, T., Zheng, X. *Dirac’s theorem on chordal graphs and Alexander duality*, Preprint.

Herzog, J., Reiner, V., Welker, V. *Componentwise linear ideals and Golod rings*, Michigan Math. J. 46 (1999), no. 2, 211–223.

Herzog, J., Takayama, Y. *Resolutions by mapping cones*, The Roos Festschrift volume, 2. Homology Homotopy Appl. 4 (2002), no. 2, part 2, 277–294 (electronic).

Stanley, R.P. *Combinatorics and commutative algebra*, Second edition. Progress in Mathematics, 41. Birkhäuser Boston, Inc., Boston, MA, 1996. x+164 pp. ISBN: 0-8176-3836-9.

Simis A., Vasconcelos W., Villarreal R., *On the ideal theory of graphs*, J. Algebra 167 (1994), no. 2, 389–416.

Villarreal R., *Monomial algebras*, Monographs and Textbooks in Pure and Applied Mathematics, 238. Marcel Dekker, Inc., New York, 2001.

Zheng, X. *Resolutions of facet ideals*, Preprint.

[^1]: Université du Québec à Montréal, Laboratoire de combinatoire et d’informatique mathématique, Case postale 8888, succursale Centre-Ville, Montréal, QC Canada H3C 3P8. email: *faridi@math.uqam.ca.* This research was supported by a NSERC Postdoctoral Fellowship.


The end of the Schulz honeymoon

Despite the surge in national polls and a huge media hype, Germany's Social Democrats have lost to Angela Merkel's ruling CDU in three state elections. A victory for Martin Schulz in the upcoming federal elections seems increasingly unlikely. Law-and-order will dominate the next four months - a topic closely associated with the CDU. So are there any real alternatives to another grand coalition?

Martin Schulz - Time for more social justice? (Photo: SPÖ OÖ/Alexander Schwarzl)

Most political observers and pundits expected the SPD to win the elections in Nordrhein-Westphalen (NRW), Germany’s most populous state and the party's heartland, last weekend. Many portrayed it as a trial run for the upcoming federal elections in September. After all, the SPD’s chancellor candidate, Martin Schulz, is from NRW and has never failed to mention his connection to the state. In the beginning of the year when Schulz was officially announced as the SPD’s candidate, the party rose quite significantly in the polls. The media as well as SPD politicians and grassroots campaigners were quick to speak of a “Schulz-effect”. In some polls his party surged up to 40% at the federal level. This also resonated in polls at the state level. According to a INSA poll conducted just a month before the elections, the SPD was ahead of the CDU by almost 9%. In the end the CDU was elected by 33% of the population, 1.8% ahead of the SPD. The strong results of the CDU and the FDP will even let them form a coalition - albeit with a tiny majority; something that seemed almost impossible a couple of weeks ago in NRW and at the federal level.

This is already the third state election where the SPD lost and the CDU, Angela Merkel’s ruling party, won by a surprisingly large margin. First in Saarland, then in Schleswig-Holstein and now in NRW. The first two elections were widely explained as not being representative and therefore with little significance for the federal elections. The SPD in Saarland admitted before the elections that it would enter a coalition with the Left Party - a no-no at the federal level. Similarly the result in Schleswig-Holstein was seen as an oddity in an agricultural dominated state mostly untouched by the refugee crisis. But NRW is different. Firstly, it’s the heartland for the SPD, especially the Ruhr Area, and Schulz’s home state. Secondly, Schulz specifically stated that this would be a test run for the federal elections and if Hannelore Kraft, the current NRW prime minister and vice-chair of the SPD, could win the elections, he would be able to achieve a home run in September. Thirdly, the CDU candidate, Armin Laschet, is regarded as a close ally of Angela Merkel and supporter of her refugee policy, as well as belonging to the left leaning wing of the CDU - not exactly what voters are looking for in a conservative party candidate in a campaign focused on law-and-order.

Usually the so-called “Schulz effect” is mentioned together with the demise of Merkel - or what some labelled Merkelmüdigkeit (tiredness of the chancellor). Foreign media, especially the English speaking press, were also convinced that she would never be able to politically survive the refugee crisis and predicted large electoral gains for the AfD, Germany’s right-wing populist party. The stark shift in her party’s refugee policy surely helped her, although the refugee crisis is far from solved. In addition, the chaotic and incompetent behaviour of the AfD should also not be understated. Nevertheless, Laschet managed to convince 33% of the voters that he is the right candidate to lead the most populous state, most likely in a coalition between the CDU and the FDP or possibly even in a “Jamaica coalition” between the CDU, FDP and the Green Party. This could be used as a trial for a future coalition at the federal level - the first such coalition in a large state.

The SPD’s Kraftlosigkeit in NRW

However, it would be foolish to speak of a resurgent “Merkel effect”. After all, in their seven years in power, the SPD-Green coalition under Kraft performed pretty poorly in most areas. They did not manage to reform the education system properly, crime rates are a lot higher than the German average and the state has underperformed in most economic indicators. Despite this the state prime minister continued to make social justice a central topic in her campaign. Voters simply did not believe she would do better this time. Or in other words, the SPD suffered under Kraftlosigkeit (literally weakness - a pun on Hannelore Kraft’s name)

The liberal one-man show

The most interesting result of the two state elections in May is the fact that the FDP won over 10% in both NRW and Schleswig-Holstein. In the 2013 federal elections the party failed to enter the Bundestag and was written off by most commentators at the time. Yet under the leadership of the young and charismatic leader Christian Lindner the party managed to resurge in the polls and is likely to also enter the Bundestag in September. However, another coalition with the CDU under Merkel at the federal level will make it very difficult for the FDP differentiate itself from the CDU and might result in a similar crash in 2021. Therefore, Lindner is right to keep talks open with all parties at the federal level (with the exception of the populist AfD and the socialist Left Party) to establish his party as an alternative with a distinctive liberal profile and not just a proponent of neoliberal and austerity policies. He has specifically stated that he is open to an Ampelkoalition (traffic light coalition) between the SPD, FDP and Green Party at the federal level. He was right to already exclude this possibility in NRW during the campaign, as this would have made his calls for change in the state’s politics not very credible. Even though a CDU-FDP coalition in NRW could be used by the SPD to showcase how such a comfortable partnership would only further neoliberal policies at the federal level. Or in other words, that the FDP is willing to sell itself out to the CDU another time.

Also noteworthy is the fact that the far-left Left Party failed to enter the Landtag (state parliament); a party that’s most popular in Eastern Germany. The Pirate Party, who had been surprisingly strong in the last elections and were represented in the state parliament for the first time, miserably failed this year. Internal fights and a failure to establish a coherent profile outside of privacy rights and digital governance made it an obvious fait.

It won’t be a smooth path for Merkel

So what does the NRW election tell us for the upcoming federal elections? Firstly, the last few years have taught us that a lot can happen in 4 months. The CDU’s powerful position can easily collapse with an unforeseen event, such as an Islamist terror attack or another influx of refugees. Approximately 900,000 African refugees are stuck in Libya alone waiting to make the dangerous crossing to Europe. According to Focus magazine, 200,000 of them could afford the trip this year. Only this year more than 1,000 have died in the Mediterranean Sea. The symptoms of the crisis have not changed and many Africans are desperate to reach Europe. The EU has failed to come up with a long-term solution to the problem, primarily because of the huge differences between the member states and populist national politics.

Further, law-and-order will be the most important in the campaigns for the federal elections, a topic traditionally associated with the CDU. Unlike the NRW election, the CDU won’t be able to attack the SPD for increasing crimes or failed integration policies, as the party has been heading the interior ministry since 2005. Furthermore, still not all refugees that entered Germany in the autumn of 2015 have been properly registered or identified. A recent scandal in the army revealed how easy it is to register as a Syrian asylum seeker under a false identity and without speaking a single word of Arabic. Not to mention the impact an actual terrorist attack committed by a refugee could have on the credibility of the CDU.

Secondly, Kraft’s down-to-earth approach and focus on social justice did not convince the voters in NRW. It seems unlikely that Schulz’s similar approach will enable him the landslide win pollsters were predicting in the beginning of the year. At the time voters were relatively unfamiliar with the former president of the European Parliament. He had not been a prominent figure in German politics and was seen as a fresh face. Merkel is trying to spin this in her favour; rather vote for stability and the experienced leader than the unknown. This resonates well with Germans. Of course, this isn’t entirely true and Schulz is by far not an unknown or inexperienced politician, as President of the European Parliament he has been able to turn himself into one of the most known EU politicians. He has supported Merkel during the refugee crisis, yet criticised her for Germany’s handling during the Greek debt crisis. The latter point might become more prominent in the upcoming months. Schulz has already indicated that he isn’t shy to talk about European solidarity, eurozone governance and euro-bonds. He has also showed strong support to reform the European common currency together with the newly elected French president Emmanuel Macron. Even though Merkel has made similar announcements, she has been critical of some of Macron’s plans in the past. This will make Schulz an easy target for her, who could claim that he would not represent German interests and is willing to turn the EU into a transfer union, where German tax payers are forced to finance southern European states. A very unpopular idea in Germany.

Get prepared for another grand coalition

According to the ARD-Deutschlandtrend poll from last week, in a direct presidential style election, 49% would vote for Merkel and only 36% for Schulz - a 180 degree turn from earlier this year. The Schulz hype has now finally come to an end. Soon he will have to make actual policy suggestions and they will prove that despite all his social justice talk he is actually a pretty centrist politician. He is very unlikely to achieve the result many party strategists were hoping for in January. Although the CDU and FDP managed to win a majority of seats in NRW, it is somewhat unlikely that this will happen at the federal elections, especially in a parliament with 6 parties. NRW and Schleswig-Holstein are both FDP strongholds and the frontrunners were the party’s two most prominent politicians in the entire country. It would be pretty surprising if the party manages to replicate such a result in September. The only real alternative to a grand coalition is, therefore, a “Jamaica coalition”. The probability of such a coalition will greatly depend on whether the pragmatic or the idealist wing (“Realos” vs “Fundis") manages to become the more prominent during the campaign and coalition talks. Unlike in Baden-Württemberg, where the Green Party rules in a coalition with the CDU, in NRW the idealists dominate the party and voters made it clear that most idealist demands are not mainstream enough (although state specific issues also played a great role, such as the performance of the Green education minister, Sylvia Löhrmann). At the moment it is unclear which wing will succeed but a “Jamaica coalition” could be tough to sell to the idealist core voters of the party. The right-wing segment of the CDU will also have difficulties with the idea of forming a coalition with the political "enemy". Further, the differences between the CDU and the Green Party seem to have increased quite dramatically since the refugee crisis. These fundamental disagreements might be quite difficult to bridge.

Yet it is also important to remember the last (and first) time the Green Party formed a coalition with the SPD at the federal level twenty years ago. At the time the conservative establishment saw the coalition highly critically. However, in retrospect the two Red/Green cabinets were one of the more successful in modern German history and have enabled the current economic strength of the country. Furthermore, the colation under Schröder not only reformed the welfare state but was also the first post-WW2 government to send German troops abroad, i.e. the Balkans and Afghanistan. But the new alignment of the SPD also hurt the party at its core; lots of traditional leftist voters saw their traditional political home sold out and not represented in the political system anymore.

In conclusion, the “Jamaica coalition” would provide Germany with a new coalition constellation that could counter the growing disenchantment with politics and the growing feeling that there are no real differences between the CDU and the SPD. The SPD would also greatly benefit from a term in opposition and could use the time to strengthen its profile. However, the more likely outcome is yet another grand coalition with Merkel as chancellor.


Q:

Passing variadic arguments as an array in Swift

Java 5+ allows passing variadic arguments either as an array, or individually. I expected Swift to allow passing variadic arguments as an array as well, but have no luck so far.
Here is a sample program, I tried in a playground. It creates an array of CVarArg and passes it to String(format:...)
let printData: [(format: String, param: [CVarArg])] =
    [(format: "This is blank", param: []),
     (format: "This is %@ %@", param: ["Swift", "language"])
   ]

for index in 0...1  {
    let pdata = printData[index]
    print (String(index+1) + " " + String(format: pdata.format, pdata.param))
}

I expected:
1 This is blank
2 This is Swift language

Instead it prints:
1 This is blank
2 This is (
    Swift,
    language
) (null)

Tried  using CVarArg... as a type:
let printData: [(format: String, param: CVarArg...)]

or bridging to CVarArg... :
String(format: pdata.format, pdata.param as CVarArg...)

In both cases I get compilation errors.
Is there a way to change the syntax of the above code to allow interpreting [CVarArg] in the expected way.

A:

I think your problem is that tuples do not support variadic arguments. So
 (format: "This is %@ %@", param: ["Swift", "language"])

is a tuple of two things: a string and an array and String(format:,_) sees the array as only one object. To solve your immediate problem, use String(format:,arguments:). e.g.
for index in 0...1  {
    let pdata = printData[index]
    print (String(index+1) + " " + String(format: pdata.format, arguments: pdata.param))
}

Given how easy it is to create a literal array, I'd question the need to use variadic arguments anywhere in Swift.