text:
# Cohen-Macaulay Properties of Square-Free Monomial Ideals

## 1 Introduction

From the point of view of commutative algebra, the focus of this paper is on finding square-free monomial ideals that have Cohen-Macaulay quotients. In \[Vi1\] Villarreal proved a criterion for the Cohen-Macaulayness of edge ideals of graphs that are trees. Edge ideals are square-free monomial ideals where each generator is a product of two distinct variables of a polynomial ring. These ideals have been studied extensively by Villarreal, Vasconcelos and Simis among others. In \[Fa\] we studied a generalization of this concept; namely the *facet ideal* of a simplicial complex. By generalizing the definition of a “tree” to simplicial complexes, we extended the results of \[SVV\] from the class of edge ideals to all square-free monomial ideals.

Below we investigate the structure of simplicial complexes in order to show that Villarreal’s Cohen-Macaulay criterion for graph-trees extends to simplicial trees (Corollary 8.3). This is of algebraic and computational significance, as it provides an effective criterion for Cohen-Macaulayness that works for a large class of square-free monomial ideals. We introduce a condition on a simplicial complex that ensures the Cohen-Macaulayness of its facet ideal, and a method to build a Cohen-Macaulay ideal from any given square-free monomial ideal. Along the road to the algebraic goal, this study sheds light on the beautiful combinatorial structure of simplicial complexes.

The paper is organized as follows: Sections 2 to 4 review the basic definitions and cover the elementary properties of trees. In Section 5 we draw comparisons between graph theory and simplicial complex theory, and prove a generalized version of König’s Theorem in graph theory for simplicial complexes. We then go on to prove a structure theorem for unmixed trees in Section 6. We introduce the notion of a *grafted* simplicial complex in Section 7, and show that for simplicial trees, being grafted and being unmixed are equivalent conditions. The notion of grafting brings us to Section 8, where we prove that grafted simplicial complexes are Cohen-Macaulay, from which it follows that a simplicial tree is unmixed if and only if it is Cohen-Macaulay.

## 2 Definitions and notation

In this section we define the basic notions that we will use later in the paper. Some of the proofs that appeared earlier in \[Fa\] have been omitted here; we refer the reader to the relevant sections of \[Fa\] when that is the case.

###### Definition 2.1 (simplicial complex, facet and more).

A *simplicial complex* $`\mathrm{\Delta }`$ over a set of vertices $`V=\{v_1,\mathrm{},v_n\}`$ is a collection of subsets of $`V`$, with the property that $`\{v_i\}\mathrm{\Delta }`$ for all $`i`$, and if $`F\mathrm{\Delta }`$ then all subsets of $`F`$ are also in $`\mathrm{\Delta }`$ (including the empty set). An element of $`\mathrm{\Delta }`$ is called a *face* of $`\mathrm{\Delta }`$, and the *dimension* of a face $`F`$ of $`\mathrm{\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 $`\mathrm{dim}\mathrm{}=1`$.

The maximal faces of $`\mathrm{\Delta }`$ under inclusion are called *facets* of $`\mathrm{\Delta }`$. The dimension of the simplicial complex $`\mathrm{\Delta }`$ is the maximal dimension of its facets; in other words

$$\mathrm{dim}\mathrm{\Delta }=\mathrm{max}\{\mathrm{dim}F|F\mathrm{\Delta }\}.$$

We denote the simplicial complex $`\mathrm{\Delta }`$ with facets $`F_1,\mathrm{},F_q`$ by

$$\mathrm{\Delta }=F_1,\mathrm{},F_q$$

and we call $`\{F_1,\mathrm{},F_q\}`$ the *facet set* of $`\mathrm{\Delta }`$.

A simplicial complex with only one facet is called a *simplex*.

###### Definition 2.2 (subcollection).

By a *subcollection* of a simplicial complex $`\mathrm{\Delta }`$ we mean a simplicial complex whose facet set is a subset of the facet set of $`\mathrm{\Delta }`$.

###### Definition 2.3 (connected simplicial complex).

A simplicial complex $`\mathrm{\Delta }=F_1,\mathrm{},F_q`$ is *connected* if for every pair $`i,j`$, $`1i<jq`$, there exists a sequence of facets

$$F_{t_1},\mathrm{},F_{t_r}$$

of $`\mathrm{\Delta }`$ such that $`F_{t_1}=F_i`$, $`F_{t_r}=F_j`$ and

$$F_{t_s}F_{t_{s+1}}\mathrm{}$$

for $`s=1,\mathrm{},r1`$.

An equivalent definition is stated on page 222 of \[BH\]: $`\mathrm{\Delta }`$ as above is *disconnected* if its vertex set $`V`$ can be partitioned as $`V=V_1V_2`$, where $`V_1`$ and $`V_2`$ are nonempty subsets of $`V`$, such that no facet of $`\mathrm{\Delta }`$ has vertices in both $`V_1`$ and $`V_2`$. Otherwise $`\mathrm{\Delta }`$ is *connected*.

###### Definition 2.4 (facet ideal, non-face ideal).

Let $`\mathrm{\Delta }`$ be a simplicial complex over $`n`$ vertices labeled $`v_1,\mathrm{},v_n`$. Let $`k`$ be a field, $`x_1,\mathrm{},x_n`$ be indeterminates, and $`R`$ be the polynomial ring $`k[x_1,\mathrm{},x_n]`$.

(a) We define $`(\mathrm{\Delta })`$ to be the ideal of $`R`$ generated by all the square-free monomials $`x_{i_1}\mathrm{}x_{i_s}`$, where $`\{v_{i_1},\mathrm{},v_{i_s}\}`$ is a facet of $`\mathrm{\Delta }`$. We call $`(\mathrm{\Delta })`$ the *facet ideal* of $`\mathrm{\Delta }`$.

(b) We define $`𝒩(\mathrm{\Delta })`$ to be the ideal of $`R`$ generated by all the square-free monomials $`x_{i_1}\mathrm{}x_{i_s}`$, where $`\{v_{i_1},\mathrm{},v_{i_s}\}`$ is not a face of $`\mathrm{\Delta }`$. We call $`𝒩(\mathrm{\Delta })`$ the *non-face ideal* or the *Stanley-Reisner ideal* of $`\mathrm{\Delta }`$.

We refer the reader to \[S\] and \[BH\] for an extensive coverage of the theory of Stanley-Reisner ideals.

Throughout this paper we often use $`x_1,\mathrm{},x_n`$ to denote both the vertices of $`\mathrm{\Delta }`$ and the variables appearing in $`(\mathrm{\Delta })`$.

###### Definition 2.5 (facet complex, non-face complex).

Let $`I=(M_1,\mathrm{},M_q)`$ be an ideal in a polynomial ring $`k[x_1,\mathrm{},x_n]`$, where $`k`$ is a field and $`M_1,\mathrm{},M_q`$ are square-free monomials in $`x_1,\mathrm{},x_n`$ that form a minimal set of generators for $`I`$.

(a) We define $`\delta _{}(I)`$ to be the simplicial complex over a set of vertices $`v_1,\mathrm{},v_n`$ with facets $`F_1,\mathrm{},F_q`$, where for each $`i`$, $`F_i=\{v_j|x_j|M_i,1jn\}`$. We call $`\delta _{}(I)`$ the *facet complex* of $`I`$.

(b) We define $`\delta _𝒩(I)`$ to be the simplicial complex over a set of vertices $`v_1,\mathrm{},v_n`$, where $`\{v_{i_1},\mathrm{},v_{i_s}\}`$ is a face of $`\delta _𝒩(I)`$ if and only if $`x_{i_1}\mathrm{}x_{i_s}I`$. We call $`\delta _𝒩(I)`$ the *non-face complex* or the *Stanley-Reisner complex* of $`I`$.

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

Notice that given a square-free monomial ideal $`I`$ in a polynomial ring $`k[x_1,\mathrm{},x_n]`$, the vertices of $`\delta _{}(I)`$ are those variables that divide a monomial in the generating set of $`I`$; this set may not necessarily include all elements of $`\{x_1,\mathrm{},x_n\}`$. The fact that some extra variables may appear in the polynomial ring does not affect the algebraic or combinatorial structure of $`\delta _{}(I)`$. On the other hand, if $`\mathrm{\Delta }`$ is a simplicial complex, being able to consider the facet ideals of its subcomplexes as ideals in the same ring simplifies many of our discussions.

###### Example 2.6.

Let $`\mathrm{\Delta }`$ be the simplicial complex below.

Here $`𝒩(\mathrm{\Delta })=(yv,zu,uv)`$, $`(\mathrm{\Delta })=(xyu,xyz,xzv)`$ are ideals in the polynomial ring $`k[x,y,z,u,v]`$.

###### Example 2.7.

If $`I=(xy,xz)k[x,y,z]`$, then $`\delta _𝒩(I)`$ is the 1-dimensional simplicial complex:

and $`\delta _{}(I)`$ is the simple graph

In this special case $`I`$ is also called the *edge ideal* of the graph $`\delta _{}(I)`$ (this terminology is due to Villarreal; see \[Vi1\]).

We now generalize some notions from graph theory to simplicial complexes.

###### Definition 2.8 (minimal vertex cover, vertex covering number, unmixed).

Let $`\mathrm{\Delta }`$ be a simplicial complex with vertex set $`V`$ and facets $`F_1,\mathrm{},F_q`$. A *vertex cover* for $`\mathrm{\Delta }`$ is a subset $`A`$ of $`V`$, with the property that for every facet $`F_i`$ there is a vertex $`vA`$ such that $`vF_i`$. A *minimal vertex cover* of $`\mathrm{\Delta }`$ is a subset $`A`$ of $`V`$ such that $`A`$ is a vertex cover, and no proper subset of $`A`$ is a vertex cover for $`\mathrm{\Delta }`$. The smallest cardinality of a vertex cover of $`\mathrm{\Delta }`$ is called the *vertex covering number* of $`\mathrm{\Delta }`$ and is denoted by $`\alpha (\mathrm{\Delta })`$.

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

Note that a simplicial complex may have several minimal vertex covers.

###### Definition 2.9 (independent set, independence number).

Let $`\mathrm{\Delta }`$ be a simplicial complex. A set $`\{F_1,\mathrm{},F_u\}`$ of facets of $`\mathrm{\Delta }`$ is called an *independent set* if $`F_iF_j=\mathrm{}`$ whenever $`ij`$. The maximum possible cardinality of an independent set of facets in $`\mathrm{\Delta }`$, denoted by $`\beta (\mathrm{\Delta })`$, is called the *independence number* of $`\mathrm{\Delta }`$. An independent set of facets which is not a proper subset of any other independent set is called a *maximal independent set* of facets.

###### Example 2.10.

If $`\mathrm{\Delta }`$ is the simplicial complex

then $`\beta (\mathrm{\Delta })=2`$. Also, $`\mathrm{\Delta }`$ is unmixed as its minimal vertex covers, listed below, all have cardinality equal to two:

$$\{x,u\},\{y,u\},\{y,v\},\{z,u\},\{z,v\}$$

This, by the way, is an example of a “grafted” tree (see Definitions 3.5 and 7.1). We show later in the paper that all grafted trees are unmixed.

The graph $`\delta _{}(I)`$ in Example 2.7 however is not unmixed. This is because $`\{x\}`$ and $`\{y,z\}`$ are both minimal vertex covers for $`\delta _{}(I)`$ of different cardinalities. In this case $`\alpha (\delta _{}(I))=\beta (\delta _{}(I))=1`$. The same argument shows that the simplicial complex in Example 2.6 is not unmixed.

The following is an easy but very useful observation; see Proposition 1 in \[Fa\] for a proof.

###### Proposition 2.11.

Let $`\mathrm{\Delta }`$ be a simplicial complex over $`n`$ vertices labeled $`x_1,\mathrm{},x_n`$. Consider the ideal $`I=(\mathrm{\Delta })`$ in the polynomial ring $`R=k[x_1,\mathrm{},x_n]`$ over a field $`k`$. Then an ideal $`p=(x_{i_1},\mathrm{},x_{i_s})`$ of $`R`$ is a minimal prime of $`I`$ if and only if $`\{x_{i_1},\mathrm{},x_{i_s}\}`$ is a minimal vertex cover for $`\mathrm{\Delta }`$.

We say that a simplicial complex $`\mathrm{\Delta }`$ over a set of vertices $`x_1,\mathrm{},x_n`$ is Cohen-Macaulay if for a given field $`k`$, the quotient ring

$$k[x_1,\mathrm{},x_n]/(\mathrm{\Delta })$$

is Cohen-Macaulay. It follows directly from Proposition 2.11, or from an elementary duality with Stanley-Reisner theory discussed in Corollary 2 of \[Fa\], that in order for $`\mathrm{\Delta }`$ to be Cohen-Macaulay, it has to be unmixed.

###### Proposition 2.12 (A Cohen-Macaulay simplicial complex is unmixed).

Suppose that $`\mathrm{\Delta }`$ is a simplicial complex with vertex set $`x_1,\mathrm{},x_n`$. If $`k[x_1,\mathrm{},x_n]/(\mathrm{\Delta })`$ is Cohen-Macaulay, then $`\mathrm{\Delta }`$ is unmixed.

###### Discussion 2.13.

It is worth observing that for a square-free monomial ideal $`I`$, there is a natural way to construct $`\delta _𝒩(I)`$ and $`\delta _{}(I)`$ from each other using the structure of the minimal primes of $`I`$. To do this, consider the vertex set $`V`$ consisting of all variables that divide a monomial in the generating set of $`I`$. The following correspondence holds:

$`F=`$ facet of $`\delta _𝒩(I)`$ $``$ $`VF=`$ minimal vertex cover of $`\delta _{}(I)`$

Also

$$I=p$$

where the intersection is taken over all prime ideals $`p`$ of $`k[V]`$ that are generated by a minimal vertex cover of $`\delta _{}(I)`$ (or equivalently, primes $`p`$ that are generated by $`VF`$, where $`F`$ is a facet of $`\delta _𝒩(I)`$; see \[BH\] Theorem 5.1.4).

Regarding the dimension and codimension of $`I`$, note that by Theorem 5.1.4 of \[BH\] and the discussion above, setting $`R=k[V]`$ as above, we have

$$\mathrm{dim}R/I=\mathrm{dim}\delta _𝒩(I)+1=|V|\mathrm{vertex}\mathrm{covering}\mathrm{number}\mathrm{of}\delta _{}(I)$$

and

$$0ptI=\mathrm{vertex}\mathrm{covering}\mathrm{number}\mathrm{of}\delta _{}(I).$$

We illustrate all this through an example.

###### Example 2.14.

For $`I=(xy,xz)`$, where $`\delta _{}(I)`$ and $`\delta _𝒩(I)`$ are drawn in Example 2.7, we have:

| facets of $`\delta _𝒩(I)`$ | minimal vertex covers of $`\delta _{}(I)`$ |
| --- | --- |
| $`\{x\}`$ | $`\{y,z\}`$ |
| $`\{y,z\}`$ | $`\{x\}`$ |

Note that $`I=(x)(y,z)`$, and

$$\mathrm{dim}k[x,y,z]/(xy,xz)=2$$

as asserted in Discussion 2.13 above.

A notion crucial to the rest of the paper is “removing a facet”. We want the removal of a facet from a simplicial complex to correspond to dropping a generator from its facet ideal. We record this definition.

###### Definition 2.15 (facet removal).

Suppose $`\mathrm{\Delta }`$ is a simplicial complex with facets $`F_1,\mathrm{},F_q`$ and $`(\mathrm{\Delta })=(M_1,\mathrm{},M_q)`$ its facet ideal in $`R=k[x_1,\mathrm{},x_n]`$. The simplicial complex obtained by *removing the facet* $`F_i`$ from $`\mathrm{\Delta }`$ is the simplicial complex

$$\mathrm{\Delta }F_i=F_1,\mathrm{},\widehat{F}_i,\mathrm{},F_q.$$

Note that $`(\mathrm{\Delta }F_i)=(M_1,\mathrm{},\widehat{M}_i,\mathrm{},M_q)`$.

Also note that the vertex set of $`\mathrm{\Delta }F_i`$ is a subset of the vertex set of $`\mathrm{\Delta }`$.

###### Example 2.16.

let $`\mathrm{\Delta }`$ be the simplicial complex in Example 2.10 with facets $`F=\{x,y,z\}`$, $`G=\{y,z,u\}`$ and $`H=\{u,v\}`$. Then $`\mathrm{\Delta }F=G,H`$ is a simplicial complex with vertex set $`\{y,z,u,v\}`$.

## 3 Trees

In \[Fa\] we extended the notion of a “tree” from graphs to simplicial complexes. The construction, at the time, was motivated by two factors: the restriction to graphs should produce the classic graph-theoretical definition of a tree, and the new structure should fit into a machinery that proves that the facet ideal of a tree satisfies Sliding Depth condition (Theorem 1 of \[Fa\]).

The resulting definition not only satisfies those two properties, but as we prove later in this paper, it also generalizes graph-trees in the sense of Cohen-Macaulayness, which confirms that algebraically this in fact is the optimal way to extend the definition of a tree.

Recall that a connected graph is a tree if it has no cycles; for example, a triangle is not a tree. An equivalent definition states that a connected graph is a tree if every subgraph has a *leaf*, where a leaf is a vertex that belongs to only one edge of the graph. This latter description is the one that we adapt, with a slight change in the definition of a leaf, to the class of simplicial complexes.

###### Definition 3.1 (leaf, joint, universal set).

Suppose that $`\mathrm{\Delta }`$ is a simplicial complex. A facet $`F`$ of $`\mathrm{\Delta }`$ is called a *leaf* if either $`F`$ is the only facet of $`\mathrm{\Delta }`$, or there exists a facet $`G`$ in $`\mathrm{\Delta }F`$, such that

$$FF^{}FG$$

for every facet $`F^{}\mathrm{\Delta }F`$.

In other words, $`F`$ is a leaf of $`\mathrm{\Delta }`$ if it intersects $`\mathrm{\Delta }F`$ in a face of $`\mathrm{\Delta }F`$.

The set of all $`G`$ as above is denoted by $`𝒰_\mathrm{\Delta }(F)`$ and called the *universal set* of $`F`$ in $`\mathrm{\Delta }`$. If $`G𝒰_\mathrm{\Delta }(F)`$ and $`FG\mathrm{}`$, then $`G`$ is called a *joint* of $`F`$.

Another way to describe a leaf is the following: (with assumptions as above) $`F`$ is a leaf if either $`F`$ is the only facet of $`\mathrm{\Delta }`$ or the intersection of $`F`$ with the simplicial complex $`\mathrm{\Delta }F`$ is a face of $`\mathrm{\Delta }F`$.

###### Definition 3.2 (free vertex).

A vertex of a simplicial complex $`\mathrm{\Delta }`$ is *free* if it belongs to exactly one facet of $`\mathrm{\Delta }`$.

In order to be able to quickly identify a leaf in a simplicial complex, it is important to notice that a leaf must have a free vertex. This follows easily from Definition 3.1: otherwise, a leaf $`F`$ would be contained in its joints, which would contradict the fact that a leaf is a facet.

###### Example 3.3.

The simplicial complex in example 2.6 has two leaves: $`\{x,y,u\}`$ and $`\{x,z,v\}`$. The one below has no leaves, because every vertex is shared by at least two facets.

###### Example 3.4.

In the simplicial complex below with facets $`F_1=\{a,b,c\}`$, $`F_2=\{a,c,d\}`$ and $`F_3=\{b,c,d,e\}`$, the only candidate for a leaf is the facet $`F_3`$ (as it is the only facet with a free vertex), but neither one of $`F_1F_3`$ or $`F_2F_3`$ is contained in the other, so there are no leaves.

###### Definition 3.5 (tree).

Suppose that $`\mathrm{\Delta }`$ is a connected simplicial complex. We say that $`\mathrm{\Delta }`$ is a *tree* if every nonempty subcollection of $`\mathrm{\Delta }`$ (including $`\mathrm{\Delta }`$ itself) has a leaf.

Equivalently, a connected simplicial complex $`\mathrm{\Delta }`$ is a tree if every nonempty *connected* subcollection of $`\mathrm{\Delta }`$ has a leaf.

###### Definition 3.6 (forest).

A simplicial complex $`\mathrm{\Delta }`$ with the property that every connected component of $`\mathrm{\Delta }`$ is a tree is called a *forest*. In other words, a forest is a simplicial complex with the property that every nonempty subcollection has a leaf.

The simplicial complex in Example 2.6 above is a tree, whereas the ones in Examples 3.3 and 3.4 are not, as they have no leaves.

Here is a slightly less straightforward example:

###### Example 3.7.

The simplicial complex on the left is not a tree, because although all three facets $`\{x,y,u\}`$, $`\{x,v,z\}`$ and $`\{y,z,w\}`$ are leaves, if one removes the facet $`\{x,y,z\}`$, the remaining simplicial complex (on the right) has no leaf.

|  | $`\stackrel{\text{remove }\{x,y,z\}}{\text{}}`$ |  |
| --- | --- | --- |

Notice that in the case that $`\mathrm{\Delta }`$ is a graph, Definition 3.5 agrees with the definition of a tree in graph theory, with the difference that now the term “leaf” refers to an edge, rather than a vertex.

## 4 Basic properties of trees

###### Lemma 4.1 (A tree has at least two leaves).

Let $`\mathrm{\Delta }`$ be a tree of two or more facets. Then $`\mathrm{\Delta }`$ has at least two leaves.

###### Proof.

Suppose that $`\mathrm{\Delta }`$ has $`q`$ facets $`F_1,\mathrm{},F_q`$ where $`q2`$. We prove the lemma by induction on $`q`$.

The case $`q=2`$ follows from the definition of a leaf.

To prove the general case suppose that $`F_1`$ is a leaf of $`\mathrm{\Delta }`$ and $`G_1𝒰_\mathrm{\Delta }(F_1)`$. Consider the subcomplex $`\mathrm{\Delta }^{}=F_2,\mathrm{},F_q`$ of $`\mathrm{\Delta }`$. By induction hypothesis $`\mathrm{\Delta }^{}`$ has two distinct leaves; say $`F_2`$ and $`F_3`$ are those leaves. At least one of $`F_2`$ and $`F_3`$ must be different from $`G_1`$; say $`F_2G_1`$. We show that $`F_2`$ is a leaf for $`\mathrm{\Delta }`$.

Let $`G_2𝒰_\mathrm{\Delta }^{}(F_2)`$. Given any facet $`F_i`$ with $`i1,2`$, we already know by the fact that $`F_2`$ is a leaf of $`\mathrm{\Delta }^{}`$

$$F_iF_2G_2F_2.$$

We need to verify this for $`i=1`$.

Since $`F_1`$ is a leaf for $`\mathrm{\Delta }`$ and $`F_2F_1`$,

$$F_2F_1G_1F_1.$$

Intersecting both sides of this inclusion with $`F_2`$, we obtain

$$F_2F_1G_1F_1F_2G_1F_2G_2F_2$$

where the last inclusion holds because $`G_1F_2`$ and $`F_2`$ is a leaf of $`\mathrm{\Delta }^{}`$.

It follows that $`F_2`$, as well as $`F_1`$, is a leaf for $`\mathrm{\Delta }`$.

A promising property of trees from an algebraic point of view is that they behave well under localization, i.e. the localization of a tree is a forest. This property is in particular useful when making inductive arguments on trees, as localization usually corresponds to reducing the number of vertices of a simplicial complex. Before proving this, we first determine what the localization of a simplicial complex precisely looks like.

###### Discussion 4.2 (On the localization of a simplicial complex).

Suppose that

$$\mathrm{\Delta }=F_1,\mathrm{},F_q$$

is a simplicial complex over the vertex set $`V=\{x_1,\mathrm{},x_n\}`$. Let $`p`$ be a prime ideal of $`k[x_1,\mathrm{},x_n]`$ generated by a subset of $`\{x_1,\mathrm{},x_n\}`$ that contains $`I=(\mathrm{\Delta })`$ (We show later in the proof of Lemma 4.5 that this is the main case that we need to study). We would like to see what the simplicial complex associated to $`I_p`$ looks like.

So

$$p=(x_{i_1},\mathrm{},x_{i_r}).$$

Now suppose

$$I=(M_1,\mathrm{},M_q)$$

where each $`M_i`$ is the monomial corresponding to the facet $`F_i`$. It follows that

$$I_p=(M_1^{},\mathrm{},M_q^{})$$

where each $`M_i^{}`$ is obtained by dividing $`M_i`$ by the product of all the variables in $`V\{x_{i_1},\mathrm{},x_{i_r}\}`$ that appear in $`M_i`$. Some of the monomials in the generating set of $`I_p`$ are redundant after this elimination, so without loss of generality we can write:

$`I_p=(M_1^{},\mathrm{},M_t^{})`$ (1)
where $`M_{t+1}^{},\mathrm{},M_q^{}`$ are the redundant monomials.

We use the notation $`\delta _{}(I_p)`$ to indicate the simplicial complex associated to the monomial ideal with the same generating set as the one described for $`I_p`$ in (1), in the polynomial ring $`k[x_{i_1},\mathrm{},x_{i_r}]`$. It follows that:

$$\delta _{}(I_p)=F_1^{},\mathrm{},F_t^{}$$

where for each $`i`$,

$$F_i^{}=F_i\{x_{i_1},\mathrm{},x_{i_r}\}$$

and $`F_{t+1}^{},\mathrm{},F_q^{}`$ each contain at least one of $`F_1^{},\mathrm{},F_t^{}`$. This simplicial complex is called the *localization* of $`\mathrm{\Delta }`$ at the prime ideal $`p`$.

Note that every minimal vertex cover $`A`$ of $`\mathrm{\Delta }`$ that is contained in $`\{x_{i_1},\mathrm{},x_{i_r}\}`$ remains a minimal vertex cover of $`\delta _{}(I_p)`$, as the minimal prime over $`I`$ generated by the elements of $`A`$ remains a minimal prime of $`I_p`$.

Moreover if $`\mathrm{\Delta }`$ is unmixed then $`\delta _{}(I_p)`$ is also unmixed. Algebraically, this is easy to see, as the height of the minimal primes of $`I_p`$ remain the same. One can also see it from a combinatorial argument: If $`B\{x_{i_1},\mathrm{},x_{i_r}\}`$ is a minimal vertex cover for $`\delta _{}(I_p)`$, then $`B`$ covers all facets $`F_1^{},\mathrm{},F_t^{}`$, and therefore $`F_{t+1}^{},\mathrm{},F_q^{}`$, as well. Therefore $`B`$ covers all of $`F_1,\mathrm{},F_q`$, and so has a subset $`B^{}`$ of cardinality $`\alpha (\mathrm{\Delta })`$ that is a minimal vertex cover for $`\mathrm{\Delta }`$, and so $`B^{}`$ must cover $`\delta _{}(I_p)`$ as well. Therefore $`B^{}=B`$.

We have thus shown that:

###### Lemma 4.3 (Localization of an unmixed simplicial complex is unmixed).

Let $`\mathrm{\Delta }`$ be an unmixed simplicial complex with vertices $`x_1,\mathrm{},x_n`$, and let $`I=(\mathrm{\Delta })`$ be the facet ideal of $`\mathrm{\Delta }`$ in the polynomial ring $`R=k[x_1,\mathrm{},x_n]`$ where $`k`$ is a field. Then for any prime ideal $`p`$ of $`R`$, $`\delta _{}(I_p)`$ is unmixed with $`\alpha (\delta _{}(I_p))=\alpha (\mathrm{\Delta })`$.

We examine a specific case:

###### Example 4.4.

Let $`\mathrm{\Delta }`$ be the simplicial complex below with $`I=(xyu,xyz,xzv)`$ its facet ideal in the polynomial ring $`R=k[x,y,z,u,v]`$.

Let $`p=(u,x,z)`$ be a prime ideal of $`R`$. Then $`I_p=(xu,xz,xz)=(xu,xz)`$. The tree $`\delta _{}(I_p)`$, shown below, has minimal vertex covers $`\{x\}`$ and $`\{u,z\}`$, which are the generating sets for the minimal primes of $`I_p`$.

If $`q=(y,z,v)`$ then $`I_q=(y,yz,zv)=(y,zv)`$ which corresponds to the forest $`\delta _{}(I_q)`$ drawn below with minimal vertex covers $`\{y,z\}`$ and $`\{y,v\}`$.

Example 4.4 above also demonstrates the following lemma.

###### Lemma 4.5 (Localization of a tree is a forest).

Let $`\mathrm{\Delta }`$ be a tree with vertices $`x_1,\mathrm{},x_n`$, and let $`I=(\mathrm{\Delta })`$ be the facet ideal of $`\mathrm{\Delta }`$ in the polynomial ring $`R=k[x_1,\mathrm{},x_n]`$ where $`k`$ is a field. Then for any prime ideal $`p`$ of $`R`$, $`\delta _{}(I_p)`$ is a forest.

###### Proof.

The first step is to show that it is enough to prove this for prime ideals of $`R`$ generated by a subset of $`\{x_1,\mathrm{},x_n\}`$. To see this, assume that $`p`$ is a prime ideal of $`R`$ and that $`p^{}`$ is another prime of $`R`$ generated by all $`x_i\{x_1,\mathrm{},x_n\}`$ such that $`x_ip`$ (recall that the minimal primes of $`I`$ are generated by subsets of $`\{x_1,\mathrm{},x_n\}`$). So $`p^{}p`$. If $`I=(M_1,\mathrm{},M_q)`$, then

$$I_p^{}=(M_{1}^{}{}_{}{}^{},\mathrm{},M_{q}^{}{}_{}{}^{})$$

where for each $`i`$, $`M_{i}^{}{}_{}{}^{}`$ is the image of $`M_i`$ in $`I_p^{}`$. In other words, $`M_{i}^{}{}_{}{}^{}`$ is obtained by dividing $`M_i`$ by the product of all the $`x_j`$ such that $`x_j|M_i`$ and $`x_jp^{}`$. But $`x_jp^{}`$ implies that $`x_jp`$, and so it follows that $`M_{i}^{}{}_{}{}^{}I_p`$. Therefore $`I_p^{}I_p`$. On the other hand since $`p^{}p`$, $`I_pI_p^{}`$, which implies that $`I_p^{}=I_p`$ (the equality and inclusions of the ideals here mean equality and inclusion of their generating sets).

We now prove the theorem for $`p=(x_{i_1},\mathrm{},x_{i_r})`$. Following the setup in Discussion 4.2, we let

$$\mathrm{\Delta }=F_1,\mathrm{},F_q$$

$$I_p=(M_1^{},\mathrm{},M_t^{})$$

$$\mathrm{\Delta }^{}=\delta _{}(I_p)=F_1^{},\mathrm{},F_t^{}.$$

for some $`tq`$.

To show that $`\mathrm{\Delta }^{}`$ is a forest, we need to show that every nonempty subcollection of $`\mathrm{\Delta }^{}`$ has a leaf.

Let

$$\mathrm{\Delta }_1^{}=F_{j_1}^{},\mathrm{},F_{j_s}^{}$$

be a subcollection of $`\mathrm{\Delta }^{}`$ where $`F_{j_1}^{},\mathrm{},F_{j_s}^{}`$ are distinct facets. If $`s=1`$, $`F_{j_1}^{}`$ is obviously a leaf and so we are done; so suppose $`s>1`$. Consider the corresponding subcollection

$$\mathrm{\Delta }_1=F_{j_1},\mathrm{},F_{j_s}$$

of $`\mathrm{\Delta }`$, which has a leaf, say $`F_{j_1}`$. So there exists $`G\mathrm{\Delta }_1F_{j_1}`$, such that

$$F_{j_1}FF_{j_1}G$$

for every facet $`FF_{j_2},\mathrm{},F_{j_s}`$. Now since each of the $`F_{j_u}^{}`$ is a nonempty facet of $`\mathrm{\Delta }_1^{}`$ and $`G^{}F_{j_1}^{}`$, the same statement holds in $`\mathrm{\Delta }_1^{}`$; so

$$F_{j_1}^{}F^{}F_{j_1}^{}G^{}$$

for every facet $`F^{}\mathrm{\Delta }_1^{}F_{j_1}^{}`$. This implies that $`F_{j_1}^{}`$ is a leaf for $`\mathrm{\Delta }_1^{}`$.

## 5 Simplicial complexes as higher dimensional graphs

In this section we study simplicial complexes as graphs with higher dimension, drawing results that will help us later in inductive arguments on unmixed trees.

###### Lemma 5.1.

If $`\mathrm{\Delta }`$ is a simplicial complex that has a leaf $`F`$ with joint $`G`$, then $`\alpha (\mathrm{\Delta }G)=\alpha (\mathrm{\Delta })`$.

###### Proof.

Suppose $`\alpha (\mathrm{\Delta })=r`$. Let $`\mathrm{\Delta }^{}=\mathrm{\Delta }G`$ and let $`A`$ be a vertex cover of minimal cardinality for $`\mathrm{\Delta }^{}`$, which implies that $`|A|r`$, as any vertex cover of $`\mathrm{\Delta }`$ has a subset that is a vertex cover of $`\mathrm{\Delta }^{}`$. Since $`F`$ is a facet of $`\mathrm{\Delta }^{}`$, there exists a vertex $`xA`$ that belongs to $`F`$. If $`x`$ is a free vertex of $`F`$, we may replace it by a non-free vertex of $`F`$ to get a vertex cover $`A^{\prime \prime }`$ of $`\mathrm{\Delta }^{}`$, with a subset $`A^{}`$ that is a minimal vertex cover of $`\mathrm{\Delta }^{}`$, and so $`|A^{}||A|`$. But now $`A^{}`$ is a minimal vertex cover for all of $`\mathrm{\Delta }`$, and so $`|A^{}|=|A|=r`$ which implies that $`\alpha (\mathrm{\Delta }^{})=\alpha (\mathrm{\Delta })=r`$.∎

###### Corollary 5.2.

If the simplicial complex $`\mathrm{\Delta }`$ is a tree and $`G\mathrm{\Delta }`$ is a joint, then $`\alpha (\mathrm{\Delta }G)=\alpha (\mathrm{\Delta })`$.

This means that in a tree with more than one facet, it is always possible to remove a facet without reducing the vertex covering number. Moreover we show in Proposition 6.6 that if $`\mathrm{\Delta }`$ is an unmixed tree with a joint $`G`$, then $`\mathrm{\Delta }G`$ is also unmixed. As a result, one can use induction on the number of facets of an unmixed tree. Note that all these arguments remain valid for a forest.

We are now ready to extend König’s theorem from graph theory.

###### Theorem 5.3 (A generalization of König’s theorem).

If $`\mathrm{\Delta }`$ is a simplicial complex that is a tree (forest) and $`\alpha (\mathrm{\Delta })=r`$, then $`\mathrm{\Delta }`$ has $`r`$ independent facets, and therefore $`\alpha (\mathrm{\Delta })=\beta (\mathrm{\Delta })=r`$.

###### Proof.

We use induction on the number of facets $`q`$ of $`\mathrm{\Delta }`$. If $`q=1`$, then there is nothing to prove since $`\alpha (\mathrm{\Delta })=\beta (\mathrm{\Delta })=1`$.

Suppose that the theorem holds for forests with less than $`q`$ facets and let $`\mathrm{\Delta }`$ be a forest with $`q`$ facets. If every connected component of $`\mathrm{\Delta }`$ has only one facet, our claim follows immediately. Otherwise, by Corollary 5.2 one can remove a joint of $`\mathrm{\Delta }`$ to get a forest $`\mathrm{\Delta }^{}`$ with $`\alpha (\mathrm{\Delta }^{})=r`$, and so by induction hypothesis $`\mathrm{\Delta }^{}`$ has $`r`$ independent facets, which are also independent facets of $`\mathrm{\Delta }`$; so $`\alpha (\mathrm{\Delta })\beta (\mathrm{\Delta })`$. On the other hand it is clear that $`\alpha (\mathrm{\Delta })\beta (\mathrm{\Delta })`$, and so the assertion follows. ∎

## 6 The structure of an unmixed tree

This section is the combinatorial core of the paper. Here we give a precise description of the structure of an unmixed tree. It turns out that a tree is unmixed if and only if it is “grafted” (see Definition 7.1). The notion of grafting is what eventually builds a bridge between unmixed and Cohen-Macaulay trees.

Below $`V(\mathrm{\Delta })`$ stands for the vertex set of $`\mathrm{\Delta }`$.

###### Lemma 6.1.

Let $`\mathrm{\Delta }`$ be an unmixed simplicial complex. Suppose that $`\alpha (\mathrm{\Delta })=\beta (\mathrm{\Delta })=r`$, and $`\{F_1,\mathrm{},F_r\}`$ is a maximal independent set of facets of $`\mathrm{\Delta }`$. Then every vertex of $`\mathrm{\Delta }`$ belongs to one of the $`F_i`$. In other words, the vertex set of $`\mathrm{\Delta }`$ is the disjoint union of the vertex sets of the $`F_i`$:

$$V(\mathrm{\Delta })=V(F_1)\mathrm{}V(F_r)$$

###### Proof.

Let $`x`$ be an vertex of $`\mathrm{\Delta }`$ that does not belong to any of the $`F_i`$. Then one can find a minimal vertex cover $`A`$ of $`\mathrm{\Delta }`$ containing $`x`$ (this is always possible). But then $`A`$ must contain one vertex of each of the $`F_i`$ as well, which implies that $`|A|r+1`$. Since $`\mathrm{\Delta }`$ is unmixed, this is not possible. ∎

###### Remark 6.2.

Lemma 6.1 does not hold in general for any unmixed simplicial complex. Take, for example, the case of a complete graph $`G`$ over 5 vertices labeled $`x,y,z,u,v`$ (every pair of vertices of $`G`$ are connected by an edge). This graph is unmixed with $`\alpha (G)=4`$ and $`\beta (G)=2`$. However, $`\{xy,uv\}`$ is a maximal independent set of facets and the fifth vertex $`z`$ of $`G`$ is missing from the vertex set of the graph $`xy,uv`$, which contradicts the claim of Lemma 6.1.

Lemma 6.1 along with Theorem 5.3 provides us with the following property for unmixed trees.

###### Corollary 6.3.

If $`\mathrm{\Delta }`$ is an unmixed tree with $`\alpha (\mathrm{\Delta })=r`$, and $`\{F_1,\mathrm{},F_r\}`$ is a maximal independent set of facets of $`\mathrm{\Delta }`$, then $`V(\mathrm{\Delta })=V(F_1)\mathrm{}V(F_r)`$.

###### Corollary 6.4.

If $`\mathrm{\Delta }`$ is an unmixed tree, then any maximal independent set of facets of cardinality $`\alpha (\mathrm{\Delta })`$ of $`\mathrm{\Delta }`$ contains all the leaves. In particular, the leaves of an unmixed tree are independent.

###### Proof.

Every leaf has a free vertex, and so it follows from above that a independent set of facets of cardinality $`\alpha (\mathrm{\Delta })`$ must contain all the leaves. The claim then follows. ∎

###### Corollary 6.5.

If $`\mathrm{\Delta }`$ is an unmixed tree, then a maximal independent set of facets of cardinality $`\alpha (\mathrm{\Delta })`$ of $`\mathrm{\Delta }`$ cannot contain a joint. In particular, a joint of an unmixed tree cannot be a leaf.

###### Proof.

If $`G`$ is a joint, it has to intersect a leaf $`F`$ by definition, and as $`F`$ is in every maximal independent set of facets of cardinality $`\alpha (\mathrm{\Delta })`$, $`G`$ cannot be in any. ∎

But even more is true. For an unmixed tree $`\mathrm{\Delta }`$, there is only one maximal independent set of facets with $`\alpha (\mathrm{\Delta })`$ elements, and that is the set consisting of all the leaves. We prove this in Theorem 6.8.

The proposition below allows us to use induction on the number of facets of an unmixed tree.

###### Proposition 6.6.

Let $`\mathrm{\Delta }`$ be an unmixed tree with a leaf $`F`$, and let $`G`$ be a joint of $`F`$. Then $`\mathrm{\Delta }^{}=\mathrm{\Delta }G`$ is also unmixed.

###### Proof.

We use induction on the number of vertices of $`\mathrm{\Delta }`$. Let

$$\mathrm{\Delta }=F_1,\mathrm{},F_q$$

and

$$V=\{x_1,\mathrm{},x_n\}$$

be the vertex set for $`\mathrm{\Delta }`$.

The case $`n=1`$ is clear.

Suppose that $`\alpha (\mathrm{\Delta })=r`$ and $`A`$ is a minimal vertex cover for $`\mathrm{\Delta }^{}`$. By Corollary 5.2 $`\alpha (\mathrm{\Delta }^{})=r`$ as well. If $`A`$ contains any vertex of $`G`$, then it is also a minimal vertex cover for $`\mathrm{\Delta }`$ and hence of cardinality $`r`$. So suppose that

$$AG=\mathrm{}\mathrm{and}|A|>r.$$

Claim: *There is a vertex $`xV(AG)`$.*

* *Proof of Claim:* If not, then

$`V=AG.`$ (2)
We show that this is not possible.

Notice that for any $`yA`$ there is a facet $`H\mathrm{\Delta }^{}`$ such that $`HA=\{y\}`$ (If no such $`H`$ existed, then $`A\{y\}`$ would also be a vertex cover).

From (2) it follows that

$`H=(GH)\{y\}.`$ (3)
On the other hand using Theorem 5.3 we can assume $`\{F_1,\mathrm{},F_r\}`$ is a maximal independent set of facets in $`\mathrm{\Delta }`$. By Corollary 6.5

$$G\{F_1,\mathrm{},F_r\}.$$

As $`|A|>r`$, one of the $`F_i`$, say $`F_r`$, has to contain more than one element of $`A`$, so suppose

$$AF_r=\{y_1,\mathrm{},y_s\}$$

where $`s>1`$ and $`y_1,\mathrm{},y_s`$ are distinct elements of $`A`$. It follows from (2) that

$`F_r=(F_rG)\{y_1,\mathrm{},y_s\}.`$ (4)
From the discussion preceding (3) above, one can pick $`H_1,\mathrm{},H_s`$ to be facets of $`\mathrm{\Delta }^{}`$ such that

$`H_i=(GH_i)\{y_i\}`$ (5)
for $`i=1,\mathrm{},s`$, and consider the tree

$$G,F_r,H_1,\mathrm{},H_s$$

which by Lemma 4.1 is supposed to have two leaves. But based on the descriptions of $`F_r,H_1,\mathrm{},H_s`$ in (4) and (5), only one facet of this tree, namely $`G`$, could possibly have a free vertex, which is a contradiction. This proves the claim.

We now proceed to showing that $`|A|>r`$ is not possible.

Let $`xV(AG).`$ We localize at the prime ideal $`p`$ generated by $`V\{x\}`$, and use the induction hypothesis.

Let

$$I=(\mathrm{\Delta })\mathrm{and}I^{}=(\mathrm{\Delta }^{})$$

and let

$$\mathrm{\Delta }_p=\delta _{}(I_p)\mathrm{and}\mathrm{\Delta }_{}^{}{}_{p}{}^{}=\delta _{}(I_{}^{}{}_{p}{}^{}).$$

From Discussion 4.2 we know that, without loss of generality, for some $`tq`$

$$\mathrm{\Delta }_p=\stackrel{~}{F}_1,\mathrm{},\stackrel{~}{F}_t$$

where $`\stackrel{~}{F}_i=F_i\{x\}`$, and each of $`\stackrel{~}{F}_{t+1},\mathrm{},\stackrel{~}{F}_q`$ contains at least one of $`\stackrel{~}{F}_1,\mathrm{},\stackrel{~}{F}_t`$.

We also know by Lemma 4.5 that $`\mathrm{\Delta }_p`$ is a forest whose vertex set is a proper subset of $`V`$.

By Lemma 4.3 $`\mathrm{\Delta }_p`$ is unmixed with $`\alpha (\mathrm{\Delta }_p)=r`$

We now focus on $`\mathrm{\Delta }_{}^{}{}_{p}{}^{}`$. Besides possibly $`\stackrel{~}{G}`$, all other facets of $`\mathrm{\Delta }_p`$ and $`\mathrm{\Delta }_{}^{}{}_{p}{}^{}`$ are the same. We show why this is true.

Let $`\stackrel{~}{F}_i\mathrm{\Delta }_{}^{}{}_{p}{}^{}`$. Then clearly

$$\stackrel{~}{F}_j\stackrel{~}{F}_i\mathrm{for}\mathrm{all}F_j\mathrm{\Delta }^{},ji.$$

On the other hand, as $`\stackrel{~}{G}=G`$ and $`GF_i`$, we have

$$\stackrel{~}{G}\stackrel{~}{F}_i$$

and so $`\stackrel{~}{F}_i\mathrm{\Delta }_p.`$

Conversely, if $`\stackrel{~}{F}_i\mathrm{\Delta }_p`$, then

$$\stackrel{~}{F}_j\stackrel{~}{F}_i\mathrm{for}\mathrm{all}F_j\mathrm{\Delta },ji$$

which implies the same for all $`F_j\mathrm{\Delta }^{}`$, and therefore $`\stackrel{~}{F}_i\mathrm{\Delta }_{}^{}{}_{p}{}^{}`$.

So there are two possible scenarios:

1. If $`\stackrel{~}{G}\mathrm{\Delta }_p`$, then

$$\mathrm{\Delta }_p=\mathrm{\Delta }_{}^{}{}_{p}{}^{}$$

which implies that $`A`$ is also a minimal vertex cover of $`\mathrm{\Delta }_p`$, which is unmixed, and hence $`|A|=r`$; a contradiction.
2. If $`\stackrel{~}{G}\mathrm{\Delta }_p`$ then

$$\stackrel{~}{F}\mathrm{\Delta }_p.$$

If not, then for some facet $`H`$ of $`\mathrm{\Delta }`$, we have $`\stackrel{~}{H}\stackrel{~}{F}`$, so $`HF\mathrm{}`$ and therefore, since $`G`$ is a joint of the leaf $`F`$,

$$HFGF$$

which immediately results in

$$\stackrel{~}{H}\stackrel{~}{G}$$

which is not possible.

In fact, $`\stackrel{~}{F}`$ remains a leaf in $`\mathrm{\Delta }_p`$, since if $`\stackrel{~}{H}`$ is a facet of $`\mathrm{\Delta }_p`$ such that $`\stackrel{~}{H}\stackrel{~}{F}\mathrm{}`$, then

$$\mathrm{}HFGF\stackrel{~}{H}\stackrel{~}{F}\stackrel{~}{G}\stackrel{~}{F}$$

and so $`\stackrel{~}{G}`$ is a joint of $`\mathrm{\Delta }_p`$.

Now by the induction hypothesis,

$$\mathrm{\Delta }_{}^{}{}_{p}{}^{}=\mathrm{\Delta }_p\stackrel{~}{G}$$

is an unmixed forest. This again implies that $`|A|=r`$; a contradiction.

###### Example 6.7.

Although not obvious at a first glance, Proposition 6.6 does not necessarily hold if $`G`$ is not a tree. The following example of an unmixed graph $`G`$ with a leaf demonstrates this point.

The graph $`G`$ above was taken from the table of unmixed graphs in \[Vi2\]. The minimal vertex covers of $`G`$, all of cardinality 3, are $`\{w,z,y\},\{v,x,u\},`$ and $`\{v,z,y\}`$. But once one removes the joint $`\{v,z\}`$, $`G^{}`$ has minimal vertex covers $`\{w,y,z\}`$ and $`\{w,y,x,u\}`$ of different cardinalities, and is therefore not unmixed.

###### Theorem 6.8 (Structure theorem for unmixed trees).

Suppose that $`\mathrm{\Delta }`$ is an unmixed tree with more than one facet such that $`\alpha (\mathrm{\Delta })=r`$. Then $`\mathrm{\Delta }`$ can be written as

$$\mathrm{\Delta }=F_1,\mathrm{},F_rG_1,\mathrm{},G_s$$

with the following properties:

1. $`F_1,\mathrm{},F_r`$ are all the leaves of $`\mathrm{\Delta }`$;
2. $`\{G_1,\mathrm{},G_s\}\{F_1,\mathrm{},F_r\}=\mathrm{}`$;
3. For $`ij`$, $`F_iF_j=\mathrm{}`$;
4. If a facet $`H\mathrm{\Delta }`$ is not a leaf, then it does not contain a free vertex.

###### Proof.

If we prove $`(i)`$, then parts $`(ii)`$, $`(iii)`$ and $`(iv)`$ will follow from $`(i)`$, Corollary 6.4 and Corollary 6.3.

We prove part $`(i)`$ by induction on the number of facets $`q`$ of $`\mathrm{\Delta }`$. If $`q>1`$, then $`q3`$ (if $`\mathrm{\Delta }`$ is a tree of two facets, both facets must be leaves by Lemma 4.1, and since $`\mathrm{\Delta }`$ is connected, we can get minimal vertex covers of cardinalities one and two, which means that $`\mathrm{\Delta }`$ is not unmixed).

So the base case for induction is when $`q=3`$. In this case, let $`F_1`$ and $`F_2`$ be the two disjoint leaves of $`\mathrm{\Delta }`$, and let $`G_1`$ be the third facet. Since $`\mathrm{\Delta }`$ is connected and unmixed, $`G_1`$ cannot be a leaf (because the leaves are pairwise disjoint). So $`G_1`$ is a joint for both $`F_1`$ and $`F_2`$ and this settles the case $`q=3`$.

For the general case, suppose that $`G`$ is a joint of $`\mathrm{\Delta }`$. By Corollary 6.5, $`G`$ is not a leaf. By Corollary 5.2 and Proposition 6.6, if we remove $`G`$, the forest $`\mathrm{\Delta }^{}=\mathrm{\Delta }G`$ is unmixed and $`\alpha (\mathrm{\Delta }^{})=r`$. By the induction hypothesis,

$`\mathrm{\Delta }^{}=F_1,\mathrm{},F_rG_1,\mathrm{},G_s`$ (6)
where conditions $`(i)`$ to $`(iv)`$ are satisfied. It is easy to see from condition $`(iv)`$ that if $`F`$ is a leaf of $`\mathrm{\Delta }`$, then it will still be a leaf of $`\mathrm{\Delta }^{}`$ (because it has a free vertex).

Our goal is to show that the converse is true, that is, to show that $`F_1,\mathrm{},F_r`$ are all the leaves of $`\mathrm{\Delta }`$.

We have the following presentation for $`\mathrm{\Delta }`$:

$`\mathrm{\Delta }=F_1,\mathrm{},F_rG_1,\mathrm{},G_sG.`$ (7)
There are two cases to consider.

1. $`G`$ is the only joint of $`\mathrm{\Delta }`$.

Suppose, without loss of generality, that for some $`e`$, $`F_1,\mathrm{},F_{e1}`$ are leaves of $`\mathrm{\Delta }`$ and $`F_e,\mathrm{},F_r`$ are not leaves of $`\mathrm{\Delta }`$. Remove $`F_1,\mathrm{},F_{e1}`$ from $`\mathrm{\Delta }`$ to obtain the forest

$$\mathrm{\Delta }^{\prime \prime }=F_e,\mathrm{},F_rG_1,\mathrm{},G_sG.$$

By Lemma 4.1, $`\mathrm{\Delta }^{\prime \prime }`$ has at least two leaves. Neither one of $`G_1,\mathrm{},G_s`$ could be a leaf, because neither one of them has a free vertex. To see this, note that by the induction hypothesis on $`\mathrm{\Delta }^{}`$ and part ($`iv`$) of the theorem, $`G_1,\mathrm{},G_s`$ do not have free vertices in $`\mathrm{\Delta }^{}`$, and hence they cannot have free vertices in $`\mathrm{\Delta }`$. As facets of $`\mathrm{\Delta }^{\prime \prime }`$, they still do not have free vertices, because as $`G`$ is the only joint of $`\mathrm{\Delta }`$,

$$G_iF_jGF_jG\mathrm{for}1is\mathrm{and}1je1.$$

Since $`G`$ is a facet of $`\mathrm{\Delta }^{\prime \prime }`$ the removal of $`F_1,\mathrm{},F_{e1}`$ does not free any vertices of $`G_1,\mathrm{},G_s`$.

This implies that at least one of $`F_e,\mathrm{},F_r`$ is a leaf of $`\mathrm{\Delta }^{\prime \prime }`$. Suppose that $`F_e`$ is a leaf. Then there exists a facet $`G^{}\mathrm{\Delta }^{\prime \prime }`$ such that

$$HF_eG^{}F_e\mathrm{for}\mathrm{all}H\mathrm{\Delta }^{\prime \prime }F_e.$$

Since $`F_iF_e=\mathrm{}`$ for $`i=1,\mathrm{}e1`$, it follows that

$$HF_eG^{}F_e\mathrm{for}\mathrm{all}H\mathrm{\Delta }F_e$$

and so $`F_e`$ is a leaf of $`\mathrm{\Delta }`$, which is a contradiction.
2. $`\mathrm{\Delta }`$ has another joint $`G^{}`$ distinct from $`G`$.

Consider the presentation of $`\mathrm{\Delta }`$ as in (7). As $`\{F_1,\mathrm{},F_r\}`$ is a maximal independent set of facets in $`\mathrm{\Delta }`$, it cannot contain $`G^{}`$ (Corollary 6.5). Therefore

$$G^{}\{G_1,\mathrm{},G_s\}.$$

We show that, say, $`F_1`$ is a leaf of $`\mathrm{\Delta }`$.

Consider the two unmixed forests

$$\mathrm{\Delta }^{}=\mathrm{\Delta }G\mathrm{and}\mathrm{\Delta }^{\prime \prime }=\mathrm{\Delta }G^{}.$$

We already know from before that $`F_1`$ is a leaf of $`\mathrm{\Delta }^{}`$. From the fact that $`\{F_1,\mathrm{},F_r\}`$ is a maximal independent set of facets in $`\mathrm{\Delta }^{\prime \prime }`$ and Corollary 6.4 and the induction hypothesis, it follows that $`F_1`$ is also a leaf of $`\mathrm{\Delta }^{\prime \prime }`$.

So, by the definition of a leaf, there is a facet, say $`G_1`$, in $`\mathrm{\Delta }^{}`$, such that

$`HF_1G_1F_1\mathrm{for}\mathrm{all}HG,F_1.`$ (8)
and a facet $`G_2\mathrm{\Delta }^{\prime \prime }`$ such that

$`HF_1G_2F_1\mathrm{for}\mathrm{all}HG^{},F_1.`$ (9)
The possible scenarios are the following.

1. $`G_1G^{}`$ or $`G_2G`$.

    Suppose $`G_1G^{}`$. In this case $`G_1\mathrm{\Delta }^{\prime \prime }`$, and so because of (9)

    $$G_1F_1G_2F_1$$

    which with (8) and (9) implies that

    $$HF_1G_2F_1\mathrm{for}\mathrm{all}HF_1$$

    hence $`F_1`$ is a leaf of $`\mathrm{\Delta }`$. The case $`G_2G`$ is identical.
    2. $`G_1=G^{}`$ and $`G_2=G`$.

    In this case, Statements (8) and (9), respectively, translate into

    $`\{\begin{array}{cc}HF_1G^{}F_1\hfill & \mathrm{for}\mathrm{all}HG,F_1\hfill \\ HF_1GF_1\hfill & \mathrm{for}\mathrm{all}HG^{},F_1\hfill \end{array}`$ (12)
    If $`F_1`$ is not a leaf of $`\mathrm{\Delta }`$, it follows from (12) that

    $`\{\begin{array}{c}GF_1G^{}F_1\hfill \\ G^{}F_1GF_1\hfill \\ HF_1(GG^{})F_1\mathrm{for}\mathrm{all}HG,G^{},F_1\hfill \end{array}`$ (16)
    By (16) there exist

    $`x(GF_1)G^{}\mathrm{and}y(G^{}F_1)G.`$ (17)
    Claim: *There is a minimal vertex cover for $`\mathrm{\Delta }G,G^{},F_1`$ that avoids all the vertices in $`G`$, $`G^{}`$ and $`F_1`$.*

    * *Proof of Claim:* We first show that there is no facet of $`\mathrm{\Delta }G,G^{},F_1`$ that has all its vertices in $`GG^{}`$. Suppose that $`H`$ is such a facet:

        $`H=(HG)(HG^{})`$ (18)
        and consider the tree

        $$\mathrm{\Delta }_1=G,G^{},F_1,H.$$

        By Lemma 4.1, $`\mathrm{\Delta }_1`$ must have two leaves. Note that $`H`$ cannot be a leaf, since because of (18) it has no free vertices. If $`F_1`$ is a leaf, then it cannot have $`G`$ or $`G^{}`$ as its joint, since that violates the first two conditions in (16), and so $`H`$ must be its joint. But then it follows that

        $$GF_1HF_1.$$

        This implies that $`xH`$ (where $`x`$ is defined in (17)), which along with the third part of (16), results in $`xG^{}`$, which is a contradiction.

        So $`G`$ and $`G^{}`$ are the two leaves of $`\mathrm{\Delta }_1`$. Consider $`G`$ first. If $`G^{}`$ is a joint for $`G`$, it follows that

        $$F_1GG^{}GG^{}$$

        which contradicts (16).

        If $`H`$ is a joint of $`G`$, then

        $$F_1GHG$$

        which implies that $`xH`$, but this again means $`xG^{}`$ (because of (16)), which is a contradiction. So $`F_1`$ is the only possible joint for $`G`$.

        With an identical argument for $`G^{}`$, it follows that $`F_1`$ is a joint for both $`G`$ and $`G^{}`$ in $`\mathrm{\Delta }_1`$, and therefore

        $$HGF_1G\mathrm{and}HG^{}F_1G^{}$$

        which along with (18) implies that

        $$HF_1$$

        which is impossible since $`H`$ and $`F_1`$ are both facets of $`\mathrm{\Delta }`$.

        So we have shown that every facet of $`\mathrm{\Delta }`$ other than $`G`$, $`G^{}`$ and $`F_1`$, has at least one vertex outside $`G`$ and $`G^{}`$ (and therefore by the third condition in (16), outside $`F_1`$).

        For each facet $`H`$ of $`\mathrm{\Delta }G,G^{},F_1`$, pick a vertex $`zH`$ that avoids all three facets $`G`$, $`G^{}`$ and $`F_1`$. The set of these vertices is a vertex cover for $`\mathrm{\Delta }G,G^{},F_1`$, and so it has a subset that is a minimal vertex cover. This proves the claim.

    Now let $`A`$ be a minimal vertex cover for $`\mathrm{\Delta }G,G^{},F_1`$ that avoids all the vertices in $`G`$, $`G^{}`$ and $`F_1`$. Since $`\mathrm{\Delta }G,G^{},F_1`$ has $`r1`$ independent facets, $`|A|r1`$. Now $`A\{x,y\}`$ is a minimal vertex cover for $`\mathrm{\Delta }`$ with more than $`r`$ vertices, which contradicts the fact that $`\mathrm{\Delta }`$ is unmixed with vertex covering number equal to $`r`$ (Note that $`x`$ and $`y`$ do not belong to any facet of $`\mathrm{\Delta }G,G^{},F_1`$, as this would contradict the third condition in (16)).

So both cases 1 and 2 lead to contradictions, therefore all of $`F_1,\mathrm{},F_r`$ must be leaves of $`\mathrm{\Delta }`$, which proves the theorem. ∎

###### Example 6.9.

The simplicial complex $`\mathrm{\Delta }`$ shown below is an unmixed tree, satisfying properties (i) to (iv) of Theorem 6.8.

It is important to notice that Theorem 6.8 does not suggest that every facet in an unmixed tree is either a leaf or a joint (See Example 6.10 below). On the other hand two different leaves in an unmixed tree may share a joint, as is the case with the unmixed graph $`xy,yz,zu`$. For these reasons the two numbers $`r`$ and $`s`$ in the statement of Theorem 6.8 that count the number of leaves and non-leaves, respectively, do not seem to have any particular relationship to one another.

###### Example 6.10.

The following simplicial complex, which is the facet complex of the ideal

$$(xu,uvew,zvew,efw,efg,fgy)$$

is an unmixed tree with a facet $`\{e,f,w\}`$ that is neither a leaf nor a joint. In fact, the two leaves $`\{x,u\}`$ and $`\{z,v,e,w\}`$ share a joint $`\{u,v,e,w\}`$.

Above, for simplicity, an $`n`$-dimensional facet (simplex) is drawn as a shaded polygon with $`n+1`$ vertices. The picture in 3D is as follows:

## 7 Grafting simplicial complexes

All that we proved in the previous section about unmixed trees can be put into one definition– namely that of a grafted tree. In fact, the method of grafting works as an effective way to build an unmixed simplicial complex from any given simplicial complex by adding new leaves (Theorem 7.6). It turns out that a grafted simplicial complex is Cohen-Macaulay (Theorem 8.2).

###### Definition 7.1 (grafting).

A simplicial complex $`\mathrm{\Delta }`$ is a *grafting* of the simplicial complex $`\mathrm{\Delta }^{}=G_1,\mathrm{},G_s`$ with the simplices $`F_1,\mathrm{},F_r`$ (or we say that $`\mathrm{\Delta }`$ is *grafted*) if

$$\mathrm{\Delta }=F_1,\mathrm{},F_rG_1,\mathrm{},G_s$$

with the following properties:

1. $`V(\mathrm{\Delta }^{})V(F_1)\mathrm{}V(F_r)`$;
2. $`F_1,\mathrm{},F_r`$ are all the leaves of $`\mathrm{\Delta }`$;
3. $`\{G_1,\mathrm{},G_s\}\{F_1,\mathrm{},F_r\}=\mathrm{}`$;
4. For $`ij`$, $`F_iF_j=\mathrm{}`$;
5. If $`G_i`$ is a joint of $`\mathrm{\Delta }`$, then $`\mathrm{\Delta }G_i`$ is also grafted.

Note that a simplicial complex that consists of only one facet or several pairwise disjoint facets is indeed grafted, as it could be considered as a grafting of the empty simplicial complex. It is easy to check that conditions (i) to (v) above are satisfied in this case.

It is also clear that the union of two or more grafted simplicial complexes is itself grafted.

###### Remark 7.2.

Condition (v) above implies that if $`F`$ is a leaf of a grafted $`\mathrm{\Delta }`$, then all the facets $`H`$ that intersect $`F`$ have embedded intersections; in other words if $`HF`$ and $`H^{}F`$ are both nonempty, then

$$HFH^{}F\mathrm{or}H^{}FHF.$$

This implies that there is a chain of intersections

$$H_1F\mathrm{}H_tF$$

where $`H_1,\mathrm{},H_t`$ are all the facets of $`\mathrm{\Delta }`$ that intersect $`F`$.

###### Remark 7.3.

Condition (v) in Definition 7.1 can be replaced by “$`\mathrm{\Delta }G_i`$ is grafted for all $`i=1,\mathrm{},s`$”. This is because even if $`G_i`$ is not a joint of $`\mathrm{\Delta }`$, $`\mathrm{\Delta }G_i`$ satisfies properties (i), (iii) and (iv), and it satisfies (ii) and (v) because of Remark 7.2, and so $`\mathrm{\Delta }G_i`$ is grafted.

###### Remark 7.4 (A grafting of a tree is also a tree).

If $`\mathrm{\Delta }^{}`$ in Definition 7.1 is a tree, then $`\mathrm{\Delta }`$ is also a tree. To see this, consider any subcollection $`\mathrm{\Delta }^{\prime \prime }`$ of $`\mathrm{\Delta }`$. If $`\mathrm{\Delta }^{\prime \prime }`$ contains $`F_i`$ for some $`i`$, then by remarks 7.2 and 7.3 $`F_i`$ is a leaf of $`\mathrm{\Delta }^{\prime \prime }`$. If $`\mathrm{\Delta }^{\prime \prime }`$ contains neither of the $`F_i`$, then it is a subcollection of the tree $`\mathrm{\Delta }^{}`$, which implies that $`\mathrm{\Delta }^{\prime \prime }`$ has a leaf.

The “suspension” of a graph, as defined in \[Vi1\], is also a grafting of that graph.

###### Example 7.5.

The tree $`F_1,F_2,G_1,G_2`$ that appeared in Example 6.9 above is a grafting of the tree $`G_1,G_2`$ with the leaves $`F_1`$ and $`F_2`$. In fact, there may be more than one way to graft a given simplicial complex. For example, some possible ways of grafting $`G_1,G_2`$ are shown below:

###### Theorem 7.6 (A grafted simplicial complex is unmixed).

Let

$$\mathrm{\Delta }=F_1,\mathrm{},F_rG_1,\mathrm{},G_s$$

be a grafting of the simplicial complex $`G_1,\mathrm{},G_s`$ with the simplices $`F_1,\mathrm{},F_r`$. Then $`\mathrm{\Delta }`$ is unmixed, and $`\alpha (\mathrm{\Delta })=r`$.

###### Proof.

If $`G_1,\mathrm{},G_s`$ is the empty simplicial complex, the claim is immediate, so we assume that it is nonempty.

We argue by induction on the number of facets $`q`$ of $`\mathrm{\Delta }`$. The first case to consider is $`q=3`$. In this case, $`\mathrm{\Delta }`$ must have at least two leaves, as if there were only one leaf $`F_1`$, i.e. if $`\mathrm{\Delta }=F_1G_1,G_2`$, then by Condition (i) of Definition 7.1 we would have $`G_1F_1`$ and $`G_2F_1`$, which is impossible. So $`\mathrm{\Delta }=F_1,F_2G_1`$, where $`G_1F_1F_2`$ and $`F_1F_2=\mathrm{}`$. It is now easy to see that $`\mathrm{\Delta }`$ is unmixed with $`\alpha (\mathrm{\Delta })=2`$.

Suppose $`\mathrm{\Delta }`$ has $`q>3`$ facets, and let $`G_1`$ be a joint of the leaf $`F_1`$. By Part (v) of Definition 7.1 $`\mathrm{\Delta }^{}=\mathrm{\Delta }G_1`$ is also grafted, and therefore by the induction hypothesis unmixed with $`\alpha (\mathrm{\Delta }^{})=r`$.

Let $`A`$ be a minimal vertex cover of $`\mathrm{\Delta }`$. We already know that $`|A|r`$ as $`F_1,\mathrm{},F_r`$ are $`r`$ independent facets of $`\mathrm{\Delta }`$. Now suppose that $`|A|>r`$ . Since $`A`$ is also a vertex cover for $`\mathrm{\Delta }^{}`$, it has a subset $`A^{}`$ that is a minimal vertex cover of $`\mathrm{\Delta }^{}`$ with $`|A^{}|=r`$. Since $`A^{}`$ is a proper subset of $`A`$, it is not a vertex cover for $`\mathrm{\Delta }`$, and therefore $`A^{}`$ cannot contain a vertex of $`G_1`$. So $`A^{}`$ contains a free vertex $`x`$ of $`F_1`$ (all non-free vertices of $`F_1`$ are shared with $`G_1`$). Now $`A`$ must contain a vertex $`y`$ of $`G_1`$; say $`yG_1F_2`$ ($`yF_1`$, since in that case $`x`$ would be redundant). So

$$A=A^{}\{y\}.$$

On the other hand $`A^{}`$ must also contain a vertex of $`F_2`$, say $`z`$. So $`F_2`$ contributes two vertices $`y`$ and $`z`$ to $`A`$; note that neither one of $`y`$ or $`z`$ could be a free vertex, as in that case the free one would be redundant.

Now suppose that $`G_2`$ is a joint of $`F_2`$. Remove $`G_2`$ from $`\mathrm{\Delta }`$ to get

$$\mathrm{\Delta }^{\prime \prime }=\mathrm{\Delta }G_2.$$

So $`A`$ has a subset $`A^{\prime \prime }`$, $`|A^{\prime \prime }|=r`$, that is a minimal vertex cover for $`\mathrm{\Delta }^{\prime \prime }`$. But as $`A`$ already has exactly one vertex in each of $`F_1,F_3,\mathrm{},F_r`$, the only way to get $`A^{\prime \prime }`$ from $`A`$ is to remove one of $`y`$ or $`z`$, this means that:

$$A^{\prime \prime }=A\{y\}\mathrm{or}A^{\prime \prime }=A\{z\}.$$

In either case $`A^{\prime \prime }`$ contains a vertex of $`G_2`$, which implies that $`A^{\prime \prime }`$ is a minimal vertex cover for $`\mathrm{\Delta }`$; a contradiction. ∎

Example 7.5 demonstrates Theorem 7.6: $`\mathrm{\Delta }=G_1,G_2`$ is a non-unmixed tree, which gets grafted with some leaves to make the unmixed trees $`\mathrm{\Delta }^{}`$, $`\mathrm{\Delta }^{\prime \prime }`$ and $`\mathrm{\Delta }^{\prime \prime \prime }`$.

One could graft any simplicial complex, even a badly non-unmixed non-tree.

###### Example 7.7.

Let $`\mathrm{\Delta }^{}`$ be the non-unmixed non-tree in Example 3.3. We could graft $`\mathrm{\Delta }^{}`$ with three new leaves

$$\{x,y,v\},\{u,w\},\{z,e\}$$

The resulting picture below is unmixed, and moreover, as we prove later, Cohen-Macaulay.

In the case of a tree theorems 6.8 and 7.6 put together with Corollary 6.3 produce a much stronger statement:

###### Corollary 7.8 (A tree is unmixed if and only if grafted).

Suppose the simplicial complex $`\mathrm{\Delta }`$ is a tree. Then $`\mathrm{\Delta }`$ is unmixed if and only if $`\mathrm{\Delta }`$ is grafted.

Grafted simplicial complexes behave well under localization; in other words, the localization of a grafted simplicial complex is also grafted. In the case of trees this follows directly from Corollary 7.8, Lemma 4.3 and Lemma 4.5. But the statement holds more generally.

###### Proposition 7.9 (Localization of a grafted simplicial complex is grafted).

Let $`I=(\mathrm{\Delta })`$ where $`\mathrm{\Delta }`$ is a grafted simplicial complex with vertices labeled $`x_1,\mathrm{},x_n`$. Suppose that $`k`$ is a field and $`p`$ is a prime ideal of the polynomial ring $`k[x_1,\mathrm{},x_n]`$. Then $`\delta _{}(I_p)`$ is a grafted simplicial complex.

###### Proof.

With notation as in Definition 7.1, let

$$\mathrm{\Delta }=F_1,\mathrm{},F_rG_1,\mathrm{},G_s.$$

If $`\mathrm{\Delta }`$ has only one facet, the statement of the theorem follows immediately, so assume that $`\mathrm{\Delta }`$ has two or more facets.

As in the proof of Lemma 4.5, it is enough to assume that $`p`$ is generated by a subset of $`\{x_1,\mathrm{},x_n\}`$, so

$$p=(x_{i_1},\mathrm{},x_{i_h}).$$

Following Discussion 4.2, let

$$\mathrm{\Delta }_p=\delta _{}(I_p)=F_1^{},\mathrm{},F_t^{}G_1^{},\mathrm{},G_u^{}$$

where for $`i=1,\mathrm{},r`$ and $`j=1,\mathrm{},s`$

$$F_i^{}=F_i\{x_{i_1},\mathrm{},x_{i_h}\}\mathrm{and}G_j^{}=G_j\{x_{i_1},\mathrm{},x_{i_h}\}$$

and $`F_{t+1}^{},\mathrm{},F_r^{},G_{u+1}^{},\mathrm{},G_s^{}`$ each contain at least one of

$`F_1^{},\mathrm{},F_t^{},G_1^{},\mathrm{},G_u^{}.`$ (19)
We now rename the facets of $`\mathrm{\Delta }_p`$ as follows. For $`i=1,\mathrm{},t`$, let

$$H_i=F_i^{}.$$

For each $`i=t+1,\mathrm{},r`$, $`F_i^{}`$ contains one of the facets appearing in (19). But as by definition $`F_iF_j=\mathrm{}`$ for all $`ji`$, there must be some $`ju`$ for which $`G_j^{}F_i^{}`$. For this particular $`j`$, set

$$H_i=G_j^{}.$$

This choice of $`j`$ is well-defined: if there were some $`fu`$ distinct from $`j`$ such that $`G_f^{}F_i^{}`$, then it would follow from Remark 7.2 that either $`G_j^{}G_f^{}`$ or $`G_f^{}G_j^{}`$, which contradicts the fact that both $`G_j^{}`$ and $`G_f^{}`$ are facets of $`\mathrm{\Delta }_p`$.

We now represent $`\mathrm{\Delta }_p`$ as

$$\mathrm{\Delta }_p=H_1,\mathrm{},H_rE_1,\mathrm{},E_v$$

where $`E_1,\mathrm{},E_v`$ represent all the other facets of $`\mathrm{\Delta }_p`$ that were not labeled by some $`H_i`$.

Our goal is to show that $`\mathrm{\Delta }_p`$ is a grafting of the simplicial complex $`E_1,\mathrm{},E_v`$ with the simplices $`H_1,\mathrm{},H_r`$.

It is clear by our construction that the facets $`H_1,\mathrm{},H_r`$ are pairwise disjoint. To see this, notice that for each pair of distinct numbers $`i_1,i_2r`$, there is a pair of distinct numbers $`j_1,j_2r`$ such that

$$H_{i_1}F_{j_1}^{}F_{j_1}\mathrm{and}H_{i_2}F_{j_2}^{}F_{j_2}$$

and as $`F_{j_1}F_{j_2}=\mathrm{}`$,

$$H_{i_1}H_{i_2}=\mathrm{}.$$

So Condition (iv) of Definition 7.1 is satisfied.

On the other hand, by Theorem 7.6 $`\mathrm{\Delta }`$ is unmixed, so by Lemma 4.3 $`\mathrm{\Delta }_p`$ is unmixed with $`\alpha (\mathrm{\Delta }_p)=\alpha (\mathrm{\Delta })=r`$. We now apply Lemma 6.1 to $`\mathrm{\Delta }_p`$ to deduce that

$$V(\mathrm{\Delta }_p)=V(H_1)\mathrm{}V(H_r),$$

which implies Condition (i) in Definition 7.1. This also implies that $`E_1,\mathrm{},E_v`$ cannot have free vertices, and hence cannot be leaves of $`\mathrm{\Delta }_p`$.

Condition (iii) is satisfied by the construction of $`\mathrm{\Delta }_p`$.

We need to show that $`H_1,\mathrm{},H_r`$ are all leaves of $`\mathrm{\Delta }_p`$. If $`\mathrm{\Delta }_p=H_1,\mathrm{},H_r`$ then $`\mathrm{\Delta }_p`$ is grafted by definition. So suppose that $`\mathrm{\Delta }_p`$ has a connected component $`\mathrm{\Delta }^{}`$ with two or more facets. As $`\mathrm{\Delta }^{}`$ is connected, it must contain some of the $`E_i`$, and as $`V(\mathrm{\Delta }_p)=V(H_1)\mathrm{}V(H_r)`$, $`\mathrm{\Delta }^{}`$ must also contain some of the $`H_j`$. So we can without loss of generality assume that

$$\mathrm{\Delta }^{}=H_1,\mathrm{},H_eE_1,\mathrm{},E_f$$

for some $`1er`$ and $`1fv`$.

We now show that, for example, $`H_1`$ is a leaf for $`\mathrm{\Delta }^{}`$. There are two cases to consider:

1. $`H_1=F_i^{}`$ for some $`i`$ such that $`1it`$.

Since $`\mathrm{\Delta }^{}`$ is connected, it has some facets that intersect $`H_i`$; suppose that $`E_{j_1},\mathrm{},E_{j_l}`$ are all the facets of $`\mathrm{\Delta }^{}H_1`$ such that

$$H_1E_{j_z}\mathrm{}$$

for $`z=1,\mathrm{},l`$.

For each $`z=1,\mathrm{},l`$ suppose that

$$E_{j_z}=G_{m_z}^{}.$$

The above paragraph translates into

$$F_i^{}G_{m_z}^{}\mathrm{}$$

and hence

$$F_iG_{m_z}\mathrm{}$$

for $`z=1,\mathrm{},l`$.

From Remark 7.2 it follows that there is some total order of inclusion on the nonempty sets $`F_iG_{m_z}`$; we assume that

$$F_iG_{m_1}F_iG_{m_2}\mathrm{}F_iG_{m_l}$$

which after intersecting each set with $`\{x_{i_1},\mathrm{},x_{i_h}\}`$ turns into

$$F_i^{}G_{m_1}^{}F_i^{}G_{m_2}^{}\mathrm{}F_i^{}G_{m_l}^{}$$

which is equivalent to

$$H_1E_{j_1}H_1E_{j_2}\mathrm{}H_1E_{j_l}$$

It follows that $`H_1`$ is a leaf of $`\mathrm{\Delta }^{}`$, and in addition, Condition (v) of Definition 7.1 is satisfied.
2. $`H_1=G_j^{}`$ for some $`j`$ such that $`1ju`$.

In this case for some $`i`$, $`t<ir`$,

$$H_1=G_j^{}F_i^{}.$$

Exactly as above, let $`E_{j_1},\mathrm{},E_{j_l}`$ be all the facets of $`\mathrm{\Delta }^{}H_1`$ such that $`H_1E_{j_z}\mathrm{}`$, and let $`E_{j_z}=G_{m_z}^{}`$ for $`z=1,\mathrm{},l`$.

As all the sets $`F_iG_{m_z}`$ are nonempty, we follow the exact argument as above to obtain the chain

$$F_i^{}G_{m_1}^{}F_i^{}G_{m_2}^{}\mathrm{}F_i^{}G_{m_l}^{}$$

As $`G_j^{}F_i^{}`$, we can intersect all these sets with $`G_j^{}`$ to obtain

$$G_j^{}G_{m_1}^{}G_j^{}G_{m_2}^{}\mathrm{}G_j^{}G_{m_l}^{}$$

which is equivalent to

$$H_1E_{j_1}H_1E_{j_2}\mathrm{}H_1E_{j_l}$$

It follows that $`H_1`$ is a leaf of $`\mathrm{\Delta }^{}`$, and also Condition (v) of Definition 7.1 is satisfied.

## 8 Grafted simplicial complexes are Cohen-Macaulay

We are now ready to show that the facet ideal of a grafted simplicial complex has a Cohen-Macaulay quotient. Besides revealing a wealth of square-free monomial ideals with Cohen-Macaulay quotients, this result implies that all unmixed trees are Cohen-Macaulay.

Let $`\mathrm{\Delta }`$ be a grafted simplicial complex over a vertex set $`V=\{x_1,\mathrm{},x_n\}`$. By Definition 7.1, $`\mathrm{\Delta }`$ will have the form

$$\mathrm{\Delta }=F_1,\mathrm{},F_rG_1,\mathrm{},G_s$$

where $`\alpha (\mathrm{\Delta })=r`$ and $`F_1,\mathrm{},F_r`$ are the leaves of $`\mathrm{\Delta }`$.

Let

$$(\mathrm{\Delta })=k[x_1,\mathrm{},x_n]/(\mathrm{\Delta }),$$

where $`k`$ is a field and let

$$𝐦=(x_1,\mathrm{},x_n)$$

be the irrelevant maximal ideal.

From Discussion 2.13 we know that

$$\mathrm{dim}(\mathrm{\Delta })=nr.$$

In order to show that $`(\mathrm{\Delta })`$ is Cohen-Macaulay, it is enough to show that there is a homogeneous regular sequence in $`𝐦`$ of length $`nr`$.

It is interesting to observe how the previous sentence follows also from Proposition 7.9: if $`m`$ is any other maximal ideal of $`(\mathrm{\Delta })`$, from the proof of Lemma 4.5 and Proposition 7.9 we see that if $`p=(x_1,\mathrm{},x_e)`$ is the ideal generated by all of $`x_i`$ that belong to $`m`$, then $`I_m=I_p`$ is the facet ideal of a grafted simplicial complex over the vertex set $`\{x_1,\mathrm{},x_e\}`$. So one can write $`m=p+q`$ where $`q`$ is a prime ideal of $`k[x_{e+1},\mathrm{},x_n]`$. It follows that

$$(\mathrm{\Delta })_m=k[x_1,\mathrm{},x_e]_p/I_p_kk[x_{e+1},\mathrm{},x_n]_q.$$

As $`k[x_{e+1},\mathrm{},x_n]_q`$ is clearly Cohen-Macaulay, by Theorem 5.5.5 of \[V\], it is enough to show that $`k[x_1,\mathrm{},x_e]_p/I_p`$ is Cohen-Macaulay in order to conclude that $`(\mathrm{\Delta })_m`$ is Cohen-Macaulay. But this is again the case of localizing at the irrelevant ideal.

Now suppose that for each $`ir`$,

$$F_i=y_ix_1^i\mathrm{}x_{u_i}^i$$

where $`y_i`$ is a free vertex of the leaf $`F_i`$, and $`y_i,x_1^i,\mathrm{},x_{u_i}^iV`$. We wish to show that

$`y_1x_1^1,\mathrm{},y_1x_{u_1}^1,\mathrm{},y_rx_1^r,\mathrm{},y_rx_{u_r}^r`$ (20)
is a regular sequence in $`(\mathrm{\Delta })`$. This follows from the process of “polarization” that we describe below.

###### Proposition 8.1 (\[Fr\]).

Let $`R`$ be the ring $`k[x_1,\mathrm{},x_n]/(M_1,\mathrm{},M_q)`$, where $`M_1,\mathrm{},M_q`$ are monomials in the variables $`x_1,\mathrm{},x_n`$, and $`k`$ is a field. Then there is an $`Nn`$, and a set of square-free monomials $`N_1,\mathrm{},N_q`$ in the polynomial ring $`k[x_1,\mathrm{},x_N]`$, such that

$$R=R^{}/(f_1,\mathrm{},f_{Nn})$$

where $`R^{}=k[x_1,\mathrm{},x_N]/(N_1,\mathrm{},N_q)`$ and $`f_1,\mathrm{},f_{Nn}`$ is a regular sequence of forms of degree one in $`R^{}`$.

For the purpose of our argument, it is instructive to see an outline of the proof of this proposition.

###### Sketch of proof.

Suppose, without loss of generality, that $`x_1|M_i`$ for $`1is`$, and $`x_1M_j`$ for $`s<jq`$.

For $`i=1,\mathrm{},s`$ we set

$$M_i^{}=\frac{M_i}{x_1}$$

so that we can write

$$I=(M_1,\mathrm{},M_q)=(x_1M_1^{},\mathrm{},x_1M_s^{},M_{s+1},\mathrm{},M_q).$$

Define

$$I_1=(x_{n+1}M_1^{},\mathrm{},x_{n+1}M_s^{},M_{s+1},\mathrm{},M_q)k[x_1,\mathrm{},x_n,x_{n+1}].$$

Then $`R=R_1/(x_{n+1}x_1)`$ where

$$R_1=k[x_1,\mathrm{},x_n,x_{n+1}]/I_1.$$

It is then shown that $`x_{n+1}x_1`$ is a non-zerodivisor in $`R_1`$. If $`I_1`$ is square-free, we are done. Otherwise one applies the same procedure to $`I_1`$ continually until the ideal becomes square-free. ∎

What we would like to show is that Sequence (20) polarizes the ring

$$S=k[y_1,\mathrm{},y_r]/(y_1^{u_1+1},\mathrm{},y_r^{u_r+1},E_1,\mathrm{},E_s)$$

into the ring $`(\mathrm{\Delta })`$, where $`E_1,\mathrm{},E_s`$ are monomials corresponding to the facets $`G_1,\mathrm{},G_s`$, where each vertex belonging to $`F_i`$ has been replaced by the free vertex $`y_i`$. In other words if

$$J=(y_1x_1^1,\mathrm{},y_1x_{u_1}^1,\mathrm{},y_rx_1^r,\mathrm{},y_rx_{u_r}^r),$$

we wish to show that

$$S=(\mathrm{\Delta })/J.$$

It will then follow from the proof of Proposition 8.1 (as detailed in \[Fr\] as well as in \[Vi2\]) that Sequence (20) is a regular sequence in $`(\mathrm{\Delta })`$.

Intuitively our claim is straightforward to see. The only problem that may arise is if after applying Sequence (20) to $`S`$, we end up with a permutation of the vertices of $`\mathrm{\Delta }`$. To prevent this from happening, we use the subtle structure of a grafted simplicial complex (Remark 7.2) that the facets intersecting a leaf do so in an embedded (and therefore ordered) manner. In other words, suppose for the leaf $`F_i`$, the facets $`H_1^i,\mathrm{},H_{e_i}^i`$ are all the facets of $`\mathrm{\Delta }F_i`$ that intersect $`F_i`$, with the ordering

$`H_1^iF_i\mathrm{}H_{e_i}^iF_i.`$ (21)
So in Sequence (20), we order

$`y_ix_1^i,\mathrm{},y_ix_{u_i}^i`$ (22)
such that if for any $`e`$ and $`f`$, $`x_e^iH_f^i`$ then $`x_e^iH_{f+1}^i`$.

We now use induction on the number of facets of $`\mathrm{\Delta }`$. If we remove a joint, say $`G_1𝒰_\mathrm{\Delta }(F_1)`$, we obtain a grafted simplicial complex

$$\mathrm{\Delta }^{}=\mathrm{\Delta }G_1$$

over the same set of vertices $`x_1,\mathrm{},x_n`$, with $`\alpha (\mathrm{\Delta }^{})=\alpha (\mathrm{\Delta })`$ (Lemma 5.1). Therefore if

$$(\mathrm{\Delta }^{})=k[x_1,\mathrm{},x_n]/(\mathrm{\Delta }^{})$$

then

$$\mathrm{dim}(\mathrm{\Delta })=\mathrm{dim}(\mathrm{\Delta }^{}).$$

Moreover, $`\mathrm{\Delta }^{}`$ has $`F_1,\mathrm{},F_r`$ as leaves. So by the induction hypothesis, Sequence (20) polarizes the ring

$$S^{}=k[y_1,\mathrm{},y_r]/(y_1^{u_1+1},\mathrm{},y_r^{u_r+1},E_2,\mathrm{},E_s)$$

into $`(\mathrm{\Delta }^{})`$, or in other words,

$$S^{}=(\mathrm{\Delta }^{})/J.$$

The induction hypothesis has ensured that after applying Sequence (20) to $`S^{}`$, all facets of $`\mathrm{\Delta }^{}`$ are restored to their original positions and labeling. Now it all reduces to showing that during this polarization process, $`E_1`$ turns into $`G_1`$.

This is clear, as for every $`i`$, $`G_1F_i`$ has its place in the ordered sequence (21), and so if $`|G_1F_i|=h_i`$, then the first $`h_i`$ applications of Sequence (22) restore $`G_1F_i`$ before moving on to facets that have larger intersections with $`F_i`$. As $`G_1`$ has disjoint intersections with $`F_1,\mathrm{},F_r`$, once Sequence (22) has been applied for all $`i`$, $`G_1`$ is restored to its proper position.

We have shown that:

###### Theorem 8.2 (Grafted simplicial complexes are Cohen-Macaulay).

Let $`\mathrm{\Delta }`$ be a grafted simplicial complex over a set of vertices labeled $`x_1,\mathrm{},x_n`$, and let $`k`$ be a field. Then $`(\mathrm{\Delta })=k[x_1,\mathrm{},x_n]/(\mathrm{\Delta })`$ is Cohen-Macaulay.

Theorem 8.2 along with Proposition 2.12 and Corollary 7.8 imply that for a tree being unmixed and being Cohen-Macaulay are equivalent conditions.

###### Corollary 8.3 (A tree is Cohen-Macaulay if and only if unmixed).

Let $`\mathrm{\Delta }`$ be a tree over a set of vertices $`x_1,\mathrm{},x_n`$, and let $`k`$ be a field. Then the quotient ring $`k[x_1,\mathrm{},x_n]/(\mathrm{\Delta })`$ is Cohen-Macaulay if and only if $`\mathrm{\Delta }`$ is unmixed.


format: text

text:
# The 𝑞-component static model : modeling social networks

## I Introduction

Recently there have been considerable efforts to understand complex systems in terms of random graph, consisting of vertices and edges, where vertices (edges) represent individuals (acquaintances or their interactions) Strogatz01 ; Albert02 ; Dorogovtsev02 ; Newman03a . In such complex networks, the emergence of a power-law degree distribution, $`P(k)k^\gamma `$, is an interesting feature. Such networks are called scale-free (SF) networks. To illustrate such SF behavior, many in silico models have been introduced, whose examples include the Barabási and Albert model Barabasi99 , the Huberman and Adamic model Huberman99 , etc. In those models, the number of vertices grows with time.

The static model Goh01 ; Caldarelli02  is another type of in silico model designed to generate SF networks, where the number of vertices is fixed. Each vertex is indexed by an integer $`i`$ ($`i=1,\mathrm{},N`$) and assigned its own weight $`w_i=i^\alpha `$, where $`\alpha `$ is a tunable parameter. Next, two different vertices $`(i,j)`$ are selected with probabilities equal to normalized weights, $`w_i/_kw_k`$ and $`w_j/_kw_k`$, respectively, and are connected via an edge unless one exists already. This process is repeated until $`mN`$ edges are present in the system, so that the mean degree is $`2m`$. Then it follows that the degree distribution is SF with the exponent $`\gamma =1+1/\alpha `$. Thus, tuning the parameter $`\alpha `$ in $`[0.5,1)`$, we can obtain a continuous spectrum of the exponent $`\gamma `$ in the range $`2<\gamma 3`$, for which the degree distribution has finite mean and diverging variance. Since the number of vertices does not grow, one may wonder if this model can be applied to evolving real world network. However, since the model network can be easily generated and exhibits little hump in the degree distribution, it can be useful to study many aspects of SF networks.

In this paper, we generalize the static model by allowing a $`q`$-component weight $`(w_i^{(1)},w_i^{(2)},\mathrm{},w_i^{(q)})`$ to each vertex $`i`$. We suppose that the $`\mu `$-th component $`w_i^{(\mu )}`$ of a vertex $`i`$ represents its own weight or fitness to a subgroup $`(\mu )`$ ($`\mu =1,\mathrm{},q`$) in a society. For example, we suppose that two persons $`i`$ and $`j`$ are alumni of a high school, a subgroup $`(\mu )`$. They would have different weights $`w_i^{(\mu )}`$ and $`w_j^{(\mu )}`$ in the subgroup $`(\mu )`$, determined by their school activities. The person $`i`$ and another person $`k`$ are colleagues in a company, another subgroup $`(\nu )`$. They have also different weights, $`w_i^{(\nu )}`$ and $`w_k^{(\nu )}`$, by their positions in the company, the subgroup $`(\nu )`$. Then the person $`i`$ has weights $`w_i^{(\mu )}`$ and $`w_i^{(\nu )}`$ in different subgroups, which are not the same in general. We make an edge between the pair ($`i`$,$`j`$) in one color representing the subgroup $`(\mu )`$ and the pair ($`i`$,$`k`$) in another color for the subgroup $`(\nu )`$. Vertices in the system are connected with edges in $`q`$ different colors representing different subgroups. Subgroups are then connected each other by weak ties as explained later. Since our society comprises many different subgroups and a person can be acquainted with other people belonging to diverse subgroups, this generalized static model is useful for modeling social networks. Meanwhile, it is noteworthy that our model is reminiscent of the generalization of the Ising model to the $`q`$-component cubic model Kim75  in equilibrium spin systems.

So far, there have been many attempts to explain the structures and the properties of social networks social . Recently, Watts et al. Watts02  introduced a hierarchical model for social network. In the model, individuals belong to groups that in turn belong to groups of groups and so on, creating a tree-like hierarchical structure of social organization. Here an individual can belong to more than one group, as a result of which the distance between two persons is shorter than the ultrametric distance between them. Such hierarchical model illustrates well the small-world property of social network as implied in the Milgram’s “six degrees of separation” Milgram67 . Another simple social network model, introduced by Newman and Park Newman03c , is based on the concept of bipartite graph Newman01  and community structure Girvan02 . This has an advantage toward explaining the non-trivial high clustering of real-world social networks. While our $`q`$-component model is similar to the hierarchical model and the community model in the spirit of dividing people into subgroups, however, we assign weights to each person for each subgroup, and connections are made following those weights.

Social network exhibits an interesting feature in the degree-degree correlation function, different from biological or information networks. Newman Newman02a  studied the degree-degree correlation in terms of the correlation function between the remaining degrees of the two vertices on each side of an edge, where the remaining degree means the degree of that vertex minus one. He introduced the assortativity coefficient $`r`$, defined as

$$r=\frac{1}{\sigma _q^2}\underset{j,k}{}jk(e_{jk}q_jq_k),$$
(1)
where $`e_{jk}`$ is the joint probability that the two vertices on each side of a randomly chosen link have $`j`$ and $`k`$ remaining degrees, respectively. $`q_k`$ is the normalized distribution of the remaining degree $`q_k=(k+1)P(k+1)/_jjP(j)`$, and $`\sigma _q^2=_kk^2q_k[_kkq_k]^2`$. Interestingly, complex networks can be classified into three types, having $`r<0`$, $`r0`$ and $`r>0`$, called the dissortative, the neutral, and the assortative network, respectively Newman02a . Most social networks are assortative as shown in TABLE I, while the Internet and the protein interaction network are dissortative. While many in silico models have been introduced, most of them are neutral. Thus it would be interesting to introduce an in silico model having the assortativity coefficient as positive and large as empirical values, which would enable one to understand a basic mechanism of social network formation. We will show that such assortative networks can be generated via the $`q`$-component static model.

## II Model

The $`q`$-component static model network is constructed as follows. Initially, $`N`$ vertices are present in the system, representing $`N`$ people in a society. Each vertex is assigned a $`q`$-component weight $`(w_i^{(1)},w_i^{(2)},\mathrm{},w_i^{(q)})`$, where $`i`$ is the vertex index. $`w_i^{(\mu )}`$, the $`\mu `$-th weight of a vertex $`i`$, is given as $`\mathrm{}_{i,\mu }^{\alpha _\mu }`$, where $`\mathrm{}_{i,\mu }`$ is the rank of the vertex $`i`$ in the $`\mu `$-th subgroup. We take $`\{\mathrm{}_{1,\mu },\mathrm{},\mathrm{}_{N,\mu }\}`$ be a random permutation of the integers $`\{1,\mathrm{},N\}`$. $`\alpha _\mu `$ is also taken to be a real random number distributed uniformly in the range $`[0.5,1)`$. In general, ranks of a person for different subgroups should be correlated in real society; however, we take them as independent in this work for simplicity. As the number of people $`N`$ becomes large, the number of distinct subgroups $`q`$ can increase in real world. Thus, we set $`q`$ to be $`q=sN`$ with $`s1`$. Then $`1/s`$ is the average number of people belonging to one subgroup.

Edges are connected as follows: First, among the $`q`$ components, we choose a component $`\mu `$ at random. Second, we choose two vertices $`(i,j)`$ with probabilities equal to normalized weights, $`p_i^{(\mu )}w_i^{(\mu )}/_kw_k^{(\mu )}`$ and $`p_j^{(\mu )}w_j^{(\mu )}/_kw_k^{(\mu )}`$, and attach an edge between them with the $`\mu `$-th color unless an edge in that color exists already. Edge color is distinct for each component. Note that the pair $`(i,j)`$ can be connected via more than one edge in different colors. Edges in different component are distinguished by their own colors. The process of attaching such edges is repeated until $`(1f)mN`$ edges are added to the system. $`f`$ is a parameter between 0 and 1. We will see that $`m`$ is related to the average degree. Since the component was chosen randomly, the number of edges in one color is $`(1f)mN/q`$ on average.

To construct a minimal model mimicking social relations, we need elements playing the role of “weak ties” Granovetter73 . So, to take into account of social relationships among people having different backgrounds, we suppose that additional social relationships are formed following the maximum weights among the $`q`$ components each individual has. Let $`w_{i,m}=\text{max}(p_i^{(1)},\mathrm{},p_i^{(q)})`$ be the normalized maximum weight of vertex $`i`$. Then two distinct vertices $`i`$ and $`j`$ are chosen with probabilities, $`w_{i,m}/_kw_{k,m}`$ and $`w_{j,m}/_kw_{k,m}`$, respectively, and are linked by a new color different from the previous $`q`$ colors unless such an edge exists already. This process is repeated until $`fmN`$ edges are formed. Edges formed by such maximum weights can be regarded as weak ties, introduced by Granovetter Granovetter73  which play an important role in social networks, connecting different subgroups. We find that the assortativity coefficient is enhanced by the presence of such weak ties.

Networks constructed in this way have $`mN`$ edges with $`(q+1)`$ colors representing internal structure of subgroups. So, some pair of vertices are linked by more than one edges in different colors, albeit such incidences are not so frequent when $`q`$ is large. However, when we measure the network properties such as the shortest pathways, the degree of a vertex, the assortativity coefficient, and so on, we regard those multiple edges as a single one. Thus the mean degree $`k`$ is slightly less than $`2m`$ by about 5% for typical networks we consider below. A small size network constructed in this way is shown in FIG. 1.

## III Simulation results

We perform numerical simulations for various values of $`q`$, $`f`$, $`m`$ and $`N`$, and examine the diameter $`d`$ and the assortativity coefficient $`r`$ as functions of those parameters. Here the diameter is the average distance between a connected pair of vertices along the shortest pathways.

First, the shape of the degree distribution depends on the number of subgroups. For small $`q`$, the degree distribution follows a power law with $`\gamma 2.8`$, however, for large $`q`$, it has a highly skewed form, approximately obeying a power law for a part of its range, and having an apparently exponential cutoff for larger $`k`$. The exponential cutoff for large $`k`$ originates from the randomness of ranks of each subgroup, and the SF behavior for intermediate $`k`$ does from the SF behavior of each subgroup. A similar crossover behavior can be found in real social networks, for example, the collaboration networks of physicists, biologists and movie stars Newman02b .

Second, we examine the assortative coefficient $`r`$ as a function of $`f`$ for a fixed $`N`$ and several values of $`m`$ and $`q`$. As shown in FIG. 3, the assortativity coefficient exhibits a peak around $`f0.2`$, meaning that the connections among subgroups are mostly optimized. Thus we limit our further consideration to the case $`f=0.2`$. Meanwhile, the diameter gradually decreases with increasing $`f`$ as shown in the inset of FIG. 3.

Third, we study the assortativity coefficient $`r`$ as a function of $`N`$ for various $`m`$ and $`q`$. It is likely that $`r`$ increases with increasing $`N`$ as $`r\mathrm{ln}\mathrm{ln}N`$ as shown in Fig. 4, but it seems to saturate for larger $`N`$. It also increases with increasing $`m`$ and $`q`$, as shown in FIG. 4. Thus the $`q`$-component static model exhibits $`r`$ values as large as empirical values listed in TABLE I. Some numerical results of $`r`$ listed in TABLE II show a quantitative agreement with the ones obtained in real social networks.

Fourth, the diameter $`d`$ is investigated as a function of the number of vertices $`N`$ for various $`m`$ and $`q`$, as shown in FIG. 5. It is found that the diameter is proportional to $`d\mathrm{ln}N`$ as in the case of random graph, in which $`d\mathrm{ln}N/\mathrm{ln}k`$ Chung01 . Furthermore, the diameter becomes smaller as $`m`$ increases, which is like the case of random graphs. However, the diameter is almost insensitive to $`q`$. To test the so-called “six degrees of separation”, we extrapolate the straight line in the semi-logarithmic plot of FIG. 5 to large $`N`$ for $`m=10`$ and $`q=N/100`$. We obtain $`d6.0`$ for $`N=10^8`$ and $`d6.7`$ for $`N=10^9`$, in reasonable agreement with the Milgram’s “six degrees of separation” Milgram67 . Here the choice of $`m=10`$ and $`q=N/100`$ comes from the facts that a person knows about 20 other people on average (see Chapter 5 of Ref. Barabasi02b ), and there are about 100 members on average in a subgroup Simmel02 .

Fifth, one of the properties well studied for complex networks is the clustering coefficient $`C`$, which is defined as the average over all vertices of the ratio of the number of triangles connected to a given vertex to the number of triples centered on that vertex. It is known that for the neutral network, the clustering coefficient behaves as $`C(N)N^{(73\gamma )/(\gamma 1)}`$ Newman03a ; Newman03c . Thus when $`\gamma =3`$, $`C(N)N^1`$. For the $`q`$-component static model, while $`r`$ is not close to zero, the rule of attaching edges is such that no explicit degree-degree correlation enters, so that it is natural to expect the behavior $`C(N)N^1`$. Indeed, the measured behavior is close to the expected one as shown in FIG. 6, but the slope in FIG. 6 exhibits small deviations for smaller $`q`$. For neutral networks, it is known that the clustering coefficient of a vertex with $`k`$ is almost independent of degree $`k`$. Even in our case, we find that indeed $`C(k)`$ is independent of $`k`$ for different $`N`$ as shown in the inset of FIG. 6.

## IV Conclusions

We have introduced the $`q`$-component static model assigning a $`q`$-component weight to each vertex. The weight of a given component of a vertex mimics a weight or fitness of that person in that subgroup. Through this model, we obtained the diameter of the acquaintance network as small as the Milgram’s “six degrees of separation” and the assortativity coefficient as positive and large as empirical values for a variety of social networks. Moreover, we obtain the degree distribution in a skewed form, which is also similar to those of real world social networks. The clustering coefficients $`C(N)`$ and $`C(k)`$ behave as those of a neutral network, being due to the absence of intrinsic degree-degree correlation. Such deficiency of the present model may be improved by introducing the hierarchical structure among subgroups, or correlated ranks of a person for different subgroups.

###### Acknowledgements.

The authors would like to thank K.-I. Goh for sharing his code for the static model and valuable discussions. This work is supported by the KOSEF Grant No. R14-2002-059-01000-0 in the ABRL program and BK21 program of Ministry of Education, Korea.


text:
# Stromatolites: why do we care?

## I Introduction

Let us explain the meaning of the title of this paper. One of the papers of these Proceedings michael  is devoted to the intriguing problem of distinguishing biotic from a-biotic stromatolites. Why do we care about the conclusion of Ref. michael ? This is the meaning of the question posed by the title of this paper. To answer this question, we have to draw the reader’s attention to an earlier work giulia , devoted to the problem of assessing the complexity of a process, as it is mirrored by a time series derived in some way from the process under study. The title of the paper of Ref. giulia : ” Compression and diffusion: a joint approach to detect complexity” is self-explanatory. In fact, the authors of Ref. giulia  discussed two methods of analysis of time series, the former with a mathematical foundation, and the latter with a physical (dynamic) foundation. The former method rests on the concept of computable information content and is, consequently, closely related to the compression algorithm used in Ref. michael . The second method rests on converting first the time series to study into a diffusion process. Then, as a second step, we evaluate the entropy of this diffusion process giulia , this being the reason why the method is called Diffusion Entropy (DE) method. We refer the reader to the paper of Ref. giulia  for details on both method. Here we limit ourselves to observing that the connection between the two methods of analysis is explained as follows. If a time series is found to be compressible, this is an indication that there is strong correlation. This strong correlation means that the diffusion process generated by the first step of the DE method must reach an anomalous scaling regime, with a scaling parameter $`\delta `$ that is expected to be different from the scaling of diffusion process that would be generated by a random time series. We expect that the more compressible the time series is, the larger is the deviation of the diffusion scaling from the ordinary value ($`\delta =0.5`$). This is the main reason why we care about the results of paper michael , which uses the compression method to study stromatolites. If the arguments of Ref. giulia  are correct, and of general validity, then the DE method applied to the same stromatolites as those studied in Ref. michael , should yield for the biotic stromatolite a scaling parameter larger than that stemming from the a-biotic stromatolite. However, to get this wished result, which would support the conclusion of the earlier paper michael  and, at the same time, would confirm that the arguments of Ref. giulia  have a general validity, we have to adapt the DE method to the specific requests posed by the analysis of digital images of polished stromatolite slabs. We solve this problem in Section 2. Section 3 is devoted to illustrating the results and Section 4 to the concluding remarks.

## II Methods

In this Section we describe, briefly, how to adapt the DE method to the analysis of digital RGB uncompressed TIFF format images of polished stromatolite slabs. For technical details on the meaning of the acronyms, we refer the reader to the paper of Ref. michael  and to the papers there quoted. Each pixel of a digitalized RGB image is labeled with three integer numbers, representing the intensity of each of the three fundamental colors: a value of $`0`$ indicates the absence of the color, while a value of $`255`$ indicates the presence of the color with the maximum possible intensity, according to the RGB scale. Therefore each RGB image is represented by three $`M\times N`$ different matrixes, with $`M`$ and $`N`$ denoting the dimensions, in pixels, of the image. The DE method for the analysis of time series, namely an ordered sequence of data represented by an one dimensional array, rests on using the time series itself, to create a diffusion process and to monitor the entropy increase as a function of time. To accomplish this, we move a window of increasing size $`l`$ through the time series, summing all the data therein contained. If $`N`$ is the length of the time series and $`l`$ is the size of the window adopted, $`Nl+1`$ different data are obtained through the moving and summing procedure. This numbers are considered as the possible positions that an imaginary walker can assume after moving for a time $`l`$, and used to define the probability density function (pdf) of the diffusion process at this time. Finally, we evaluate the Shannon entropy of the pdf. The generalization of this procedure to the case where the data to examine are represented by a matrix is simple. The window of size $`l`$ to move through the sequence of data, is substituted by a square of size $`l`$ to be moved through the matrix. Fig. 1 illustrates how to apply this procedure to a square of size $`l=2`$ and, thus, to a matrix $`9\times 9`$. The sum of all the elements inside a square has to be considered as one of the possible positions that an imaginary walker can assume after a time $`l^2`$. With this modification it is possible to use the data contained in a matrix to build up a one-dimensional diffusion process. A digital RGB image stems from three different matrixes and we are naturally led to two possible ways of applying the DE method to the image. The first one is to create a one-dimensional diffusion process for each one of the three matrixes representing the intensity of the three fundamental colors, and to examine the dependence of the diffusion entropy on the color. We shall refer to this analysis as the “single color DE image analysis”. The second one is to use the three matrixes to create a three-dimensional diffusion process and to evaluate the change in time of its entropy. This is done using the three matrixes of an RGB image file, to determine the movement of the imaginary walker in the $`(x,y,z)`$ space, with the x, the y and the z-axis, referring to the red, green and blue color, respectively. This last technique will be referred to by us as the “global DE image analysis”.

## III Results

In order to establish, hopefully, the biogenicity of a given stromatolite through statistical analysis of the corresponding RGB images, the authors of Ref. michael  decided to compare the results of the compressibility of putative biotic and a-biotic stromatolites with the compressibility of the rock matrix surrounding the samples. Here, we shall follow the same strategy for the results of the single-color DE image analysis and global DE image analysis. We explore the same database of Ref. michael  and, for brevity, we report the results relative to just four images, a putative biotic target, the surrounding matrix of the biotic target, a putative a-biotic target and its surrounding matrix. Fig. 2 shows the results of the application of the single-color DE image analysis. For clarity, the curves relative to different images are shifted to different initial values. Moreover, another shifting procedure is applied to the three curves relative to the three different color matrixes of a single image, so that only the rates of increase of diffusion entropy are compared. We see that the three different colors, for all the images, produce, approximately, the same curve and that only the curves of the putative biotic image yield a quantitatively different rate of entropy increase, as indicated by the corresponding slopes, which are different from the others.

Fig. 3 shows the results of the global DE image analysis. Again, a procedure of shifting of the curves is adopted, so as to compare among themselves only the rates of entropy increase, in the linear-log representation. We see clearly that the diffusion process generated by the putative a-biotic sample and the one generated by its surrounding matrix yield, virtually, the same rate of entropy increase. It is evident, though, that the putative biotic sample yields a slope distinctly larger than that stemming from its surrounding matrix, a slope which, is, on the contrary, close to that of both a-biotic target and a-biotic surrounding. Fig. 3 shows that the biotic target has a slope close to $`\delta =2.2`$, while the other three curves yield a slope close to $`\delta =2`$. Note that an entropy increase with a slope $`\delta =1.5`$ is the result expected for an ordinary three-dimensional diffusion.

## IV Concluding Remarks

We see that the extension of the DE method to the analysis of two-dimensional images yields results supporting the conclusion of the paper of Ref.michael . The most compressible two-dimensional image yields the largest scaling. As to the relevance of this conclusion for the challenge posed by the search for a way to distinguish biotic from a-biotic stromatolites, we limit ourselves to the following remark. We see that, although the biotic target yields the highest scaling, also the scaling of both biotic and a-biotic surroundings are larger than the ordinary scaling. This means that complexity is a general property. It is not only a property of living systems, it is rather a property of the so called *living state of matter* marco ; gerardo . Thus, the fact that distinguishing biotic from a-biotic stromatolites is a challenging issue, is a way to answer a provocative question raised by the author of Ref. gunter . Pete Gunter gunter  writes: ” How odd it is that on this planet at least life emerged at virtually the same time as rocks.” We think that the field of Complexity is affording an answer to this question. Life and rocks are perceived as foreign the one to the others, if the vision of ordinary statistical mechanics is adopted. Ordinary statistical mechanics is not a fair representation of reality, but only a condition mirroring one of the two basic properties of nature: randomness, the other being order. The balance of randomness with order yields a condition intermediate between the dynamic and the thermodynamic state gerardo , with phenomena such as aging that according to the traditional wisdom seem to be peculiar to living systems. On the contrary, as proven in Ref. gerardo , these phenomena are manifested also by non-living systems. So, a new perspective, moving from Bergson gunter  , benefiting from the pioneering work of Prigogine gunter ; marco , and yielding, finally, the concept of Living State of Matter marco ; gerardo , can also be used to explain why the stromatolite problem is difficult, and so challenging, and much more research work is required to establish how general are the conclusion of this paper and of the companion paper of Ref. michael .
PG and MI acknowledge support from ARO, through Grant DAAD19-02-0037.