You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: |
    Let $\Pi^{(k)}_{(n-1)k+1}$ be the poset of partitions of $\{1,2,\dots,(n-1)k+1\}$ with block sizes congruent to $1$ modulo $k$. We prove that the order complex $\Delta(\Pi^{(k)}_{(n-1)k+1})$ is a subdivision of the complex of $k$-trees $\Tk$, thereby answering a question posed by Feichtner [@F 5.2].

    The result is obtained by an [*ad-hoc*]{} generalization of concepts from the theory of nested set complexes to non-lattices.
address: 'Department of Mathematics, ETH Zurich, 8092 Zurich, Switzerland'
author:
- Emanuele Delucchi
title: 'Subdivision of complexes of $k$-Trees'
---

[^1]

Introduction {#sect_intr .unnumbered}
============

The complex of $k$-trees $\Tk$ is the abstract simplicial complex whose faces correspond to combinatorial types of rooted trees with $m=(n-1)k+1$ labelled leaves and all outdegrees congruent to $1$ modulo $k$ (and larger than $k$). Face relations among these trees are such that $T_2$ is a face of $T_1$ if and only if $T_2$ is obtained from $T_1$ by contraction of internal edges. Complexes of $k$-trees are a generalization of complexes of trees [@Bo] defined by Hanlon in [@H]. The complexes $\Tk$ are pure simplicial complexes of dimension $n-3$. They were shown to be Cohen-Macaulay by Hanlon in [@H], and shellability was proven independently by Trappmann and Ziegler [@TZ] and Wachs [@W].

The symmetric group $S_m$ acts naturally on $\Tk$ by permutation of the leaves. In fact, the complex $\Tk$ was introduced by Hanlon because of the relation of its top homology group to the $1^m$ homogeneous component of the free Lie-$k$-algebra with $m$ odd generators, both as $S_m$-modules. Lie-$k$-algebras are a generalization of Lie algebras introduced by Hanlon and Wachs in [@HW]. Here, the poset $\Pk$ of partitions of $\{1,\dots , m\}$ with block sizes congruent to $1$ modulo $k$ enters our picture. This poset was shown to be Cohen-Macaulay by Björner [@Bj], and was studied by Calderbank, Hanlon and Robinson in [@CHR] from the point of view of representation theory. Combining the results of [@H] and [@HW] one finds that there is a $S_m$-module isomorphism between $\tilde{H}_{n-3}(\Tk)$ and $\tilde{H}_{n-3}(\Pk)$, since both are isomorphic to the $1^m$ homogeneous piece of the free Lie-$k$-algebra with $m$ odd generators.

This situation leads to the very natural question of the geometric relationship between the two complexes.

The case $k=1$ is interesting on its own right. The complex $\TT_n=\TT_n^1$ (called [*complex of trees*]{}) first appeared in [@B], in the context of homotopy theory. Its $S_m$-representation theory was studied by Robinson and Whitehouse [@RW], it figured in geometric group theory in work of Vogtmann [@V], and recently attracted interest again in the study of phylogenetic trees [@BHV]. In fact, the order complex of the partition lattice $\Pi_m$ is PL-homeomorphic to $\Tk$ [@AK]. More specifically, $\Delta(\Pi_m)$ is obtained from $\TT_n$ by a sequence of stellar subdivisions [@F]. This is shown by applying the theory of [*combinatorial nested set complexes*]{}, introduced by Feichtner and Kozlov in [@FK] as the combinatorial framework and counterpart of De Concini - Procesi models of subspace arrangements [@DP]. In [@F Question 5.2], Feichtner asks whether for general $k$ the complexes $\Pk$ and $\Tk$ are related by a subdivision.

In this note we answer this question positively. The direct approach via nested set complexes does not work: other than $\P$, $\Pk$ is not a lattice, which is an essential condition for the applicability of the theory of nested sets. However, in our context we can introduce analogous concepts that allow us to reduce the problem to a situation that can be handled by the existing theory.

In Section \[nsc\] we review the definition and some of the basic properties of nested set complexes. In Section \[combsub\] we set up the topological framework for subdivisions of simplicial complexes and, with Lemma \[lemma\], state the key tool that will enable us to prove our result. In Section \[terza\] the analogies with the classical framework of nested sets will be put to work, giving explicite subdivisions of each simplex of $\Tk$. By Lemma \[lemma\] we will then be able to construct a subdivision of the whole complex. Although our method is very much tailored to the specific situation of the partition posets, we have kept the notations and the arguments as close as possible to the original theory of nested sets, hoping that this may be a first step towards a generalization of the theory to non-semilattices.

Nested set complexes {#nsc}
====================

We recall the basic definitions and some useful facts about nested set complexes. For a more extensive account see [@FK].

[\[building\] Let $\LL$ be a meet-semilattice. A [**building set**]{} of $\LL$ is a subset $\GG\subseteq\LL\setminus\{\hat{0}\}$ such that for any $x\in\LL\setminus\hat{0}$ there is an isomorphism $$\varphi_x: {\Large\prod_{\scriptstyle{{z\in\textrm{\textup{max}}}\,\GG_{\leq x}}}} [\hat{0},z] \rightarrow [\hat{0},x]$$ with $\varphi_x(\0,\dots\0,z,\0,\dots,\0)=z$ for $z\in\textrm{\textup{max}}\,\GG_{\leq x}$.]{}

Given a building set $\GG$, the set $F_\GG(x):=\textrm{\textup{max}}\,\GG_{\leq x}$ is called the set of [*factors of $x$ in $\GG$*]{}. We may sometimes drop the suffix and write only $F(x)$ if no confusion can arise.\
[**Remarks:**]{}

-   Building sets can be defined as in [@FK 2.3, (2)], independently of the existence of a join operation, for any poset with a unique minimal element.

-   If a join operation exists in $\LL$, the isomorphism $\varphi_x$ can always be chosen such that $\varphi_x(z_1,\dots,z_n)=z_1\vee\dots\vee z_n$ [@FK Proof of 2.3].

[\[nested\] Let $\LL$ be a semilattice and $\GG$ a building set in $\LL$. We call a set $N\subseteq\GG$ [**nested**]{} ($\GG$-nested, if specification is needed) if, for any set $\{x_1,\dots,x_\ell\}\subseteq N$ ($\ell\geq 2$) of incomparable elements, the join $x_1\vee \dots\vee x_\ell$ exists and is not an element of $\GG$. The [**nested set complex**]{} of $\LL$ with respect to $\GG$, denoted $\NN(\LL,\GG)$, is the abstract simplicial complex of all nonempty $\GG$-nested sets (with the apex removed, if $\LL$ has a maximal element). ]{}

[**Remarks:**]{}

-   This definition implies that $F(x_1\vee\dots\vee x_\ell)=\{x_1,\dots,x_\ell\}$ for any set of incomparable elements $\{x_1,\dots,x_\ell\}\subseteq N$, see [@FK 2.8, (2)].

-   Consider the maximal building set $\GG=\LL$. In this case, a set is $\GG$-nested if and only if it is linearly ordered. Therefore we have $\NN(\LL,\LL)=\Delta(\LL)$, the order complex of (the proper part of) $\LL$.

If $\LL$ is atomic, then Feichtner and Yuzvinsky [@FY] give an explicit geometric realization of nested set complexes of $\LL$. If $\HH\subseteq\GG$ are building sets of $\LL$, Feichtner and Müller [@FM] prove that $\NN(\LL,\GG)$ arises from $\NN(\LL,\HH)$ by a sequence of stellar subdivisions.

Subdivisions of abstract simplicial complexes {#combsub}
=============================================

Let $K$ be an abstract simplicial complex on the vertex set $V(K)$. We denote its face poset by $\FF(K)$. Given $s\in\FF(K)$, we will write $K_s$ for the simplicial complex of all nonempty subsets of the vertex set $V(K_s)=s$.

Recall that the *realization* of a simplicial complex $K$ is the topological space $|K|$ whose points are the formal convex combinations $\Sigma t_v v$ of vertices (i.e., the coefficients $t_v$ are all nonnegative and $\sum_{v\in V(K)} t_v\! =\! 1$) such that the set $\{v \in V(K) |\, t_v \neq 0\}$ belongs to the family $K$. For any simplex $s\in K$ define $|s|:=|K_s|=\{\Sigma t_v v \in |K| |\, t_v \neq 0 \Rightarrow v\in s \}$. If $s\in K$ contains $n$ vertices there is a natural correspondence between $|s|$ and the standard Euclidean $n$-simplex $\Delta^n$. The topology on $|K|$ is such that $A\subseteq |K|$ is closed if and only if $A\cap |s|$ is closed (in the Euclidean topology induced by $\Delta^n$) for each simplex $s$ of $K$.

The interior of a simplex $s\in K$ is then $\langle s \rangle := |s|\setminus\partial |s|$, and for each point $x\in|K|$ we can now define the [*carrier*]{} of $x$ as $\tau(x):=\textrm{min}\{s\in K | x\in \langle s \rangle\}$.\
[ Let $P,Q$ be simplicial complexes. $P$ is a [**subdivision**]{} of $Q$ if there exists a poset map $\phi : \FF(P) \rightarrow \FF(Q)$ and an (injective) mapping $f^0: V(P)\rightarrow |Q|$ such that $f^0(V(P_p))\subseteq |Q_{\phi(p)}|$ for all simplices $p\in P$, and the linear extension $f:|P|\rightarrow |Q|$ of $f^0$ to $|P|$ is a homeomorphism. ]{}\
The map $\phi$ will be called the *carrier map*, and $f^0$ the *vertex map* of the subdivision.

Our point of view will be to take a given map between the face posets, and look for conditions under which this map is the carrier map of a subdivision (or, as we will say in the following: *is* a carrier map).

Suppose that we have a good candidate for $f^0$. The linear extension $f$ is continuous because it is linear -hence continuous- on every closed simplex. Realizations of simplicial complexes are compact, Hausdorff spaces. Therefore it suffices to check bijectivity of $f$ to conclude that $f$ is a homeomorphism. We summarize this in the following lemma for later reference.

[ Let $P,Q$ be simplicial complexes, and let a vertex map $f^0:V(P)\rightarrow |Q|$ be given. The linear extension $$\begin{array}{rccc}
f:& |P| &\rightarrow & |Q| \\
  & \Sigma t_vv & \mapsto & \Sigma t_vf^0(v) 
\end{array}$$ of $f^0$ to $|P|$ is a homeomorphism if and only if for every simplex $q$ of $Q$ the set $\{f(\langle p \rangle) | f^0(p)\subseteq |q|\}$ is a finite partition of $\langle q \rangle$.]{}\
We now define the concept of [*compatibility*]{} of carrier maps. This will lead to a lemma that will be one of the key tools in our argument.

[\[compatible carrier map\] Let $P,Q$ be simplicial complexes, $P_1,P_2$ and $Q_1,Q_2$ subcomplexes of $P$, resp. of $Q$. Two poset maps $\phi_1:\FF(P_1)\rightarrow \FF(Q_1)$, $\phi_2:\FF(P_2)\rightarrow \FF(Q_2)$ are called [**compatible carrier maps**]{} if for $i=1,2$ there are vertex maps $f^0_i:V(P_i)\rightarrow V(Q_i)$ so that $P_i$ is a subdivision of $Q_i$ with carrier map $\phi_i$, and moreover $f^0_1 = f^0_2$ on $V(P_1)\cap V(P_2)$.]{}

[\[lemma\] A poset map $\phi:\FF(P)\rightarrow\FF(Q)$ is the carrier map of a subdivision if the maps $\phi_q : \phi^{-1}(\FF(Q)_{\leq q})\rightarrow \FF(Q)_{\leq q}$ are compatible carrier maps for all $q \in \FF(Q)$. ]{}

\
The condition of compatibility may be hard to check, and therefore Lemma \[lemma\] does not give a handy tool in general. However, it becomes useful in our situation, where compatibility will emerge from an explicit description of ’partial’ subdivision processes.

$\Delta(\Pk)$ is a subdivision of $\Tk$ {#terza}
=======================================

Complexes of $k$-trees.
-----------------------

We recall the definition of complexes of $k$-trees from [@H] and view them in the context of a nested-set-like construction.

[ For positive integers $k,n$ let $\Tk$ denote the collection of all trees having $(n-1)k+2$ labelled leaves and having the property that every internal vertex has degree $rk+2$ for some $r>0$. We can partially order this set by saying that $T_1 > T_2$ if $T_2$ can be obtained from $T_1$ by contraction of some set of internal edges. ]{}

For us it will be convenient to work with simplicial complexes and rooted trees. We rewrite the previous definition, and let $\Tk$ denote the abstract simplicial complex of rooted trees on $m=(n-1)k+1$ leaves with all outdegrees larger than $1$ and congruent to $1$ modulo $k$. The face relations are such that $T_2$ is a face of $T_1$ if $T_2$ is obtained from $T_1$ by a contraction of a set of internal edges.

Let $\II$ denote the minimal building set of $\P$. It consists of all partitions with only one block of size bigger than $1$.

At this point it is worth to remind that $\Pk$ is not a lattice. For example, the join of the partitions $(123)4567$ and $1(234)567$, considered as elements of $\Pi_7$, is clearly $(1234)567$. But as elements of $\Pi_7^{(2)}$ they have three different minimal upper bounds: $(12345)67$, $(12346)57$ and $(12347)56$.

This is the reason why the theory of combinatorial nested sets cannot be directly applied here. Nevertheless, in the following we will reduce our problem, at least ’locally’, to a situation where the existing theory can be applied.

We define a subset of $\Pk$,

$\GG:=\{x\in\II \vert\; rk(x)\equiv 0 \pmod{k} \} \subseteq\Pk$.

It will serve as an analogue of the building set $\II$ in our non-lattice context.

[There is a bijective correspondence between the simplicial complex $\Tk$ and the family of sets $\{N\in \NN(\P,\II)\vert N\subseteq\GG\}$. In particular, the latter is a simplicial complex.]{}

We follow [@F proof of 3.1], where an explicit correspondence is given in the case of $k=1$.\
“$\subseteq$”: Let $T\in\Tk$ be a (rooted) tree with inner vertices $t_1,\dots,t_k$. The set of leaves below the vertex $t$ will be denoted by $\ell(t)$. For $N(T):=\{\ell(t_i) \vert i=1,\dots,k\}$ we have $N(T)\in \NN(\P,\II)$ [@F], and, by the condition on outdegrees, clearly $N(T)\in\GG$.\
“$\supseteq$”: To every $N=\{S_1,\dots,S_k\}\in\NN(\P,\II)$ we can construct a tree $T(N)$ as in [@F]. The set of internal vertices is $\tilde{N}=N\cup\{[m]\}$ (where $[m]$ corresponds to the root), and the covering relation is defined by $U_1<U_2$ if and only if $U_2\in\textrm{max} N_{<U_1}$ for all $U_1,U_2\in\tilde{N}$. The outdegree $out(U)$ of an internal vertex $U\in \tilde{N}$ is:

$out(U)=|U\setminus\bigcup_{S\in N, S<U} S|+|\{S\in N \vert S<U\}|=|U|-\sum_{S\in N, S<U} |S| +|\{S\in N \vert S<U\}|$.

Moreover, if $N\in\GG$, then $|S|\equiv 1 \pmod{k}$, and with $s:=|\{S\in N \vert S<U\}|$ we have $out(U)\equiv 1 -s +s \equiv 1 \pmod{k}$. $\square$

In the following we will consider $\Pk$ as a subset of $\P$. Given two elements $a,b \in \Pk$ we shall denote by $a\vee b$ the join of them as elements of $\P$, and by $a \veek  b$ we will mean the set of all minimal upper bounds of $a$ and $b$ in $\Pk$. In the example above we would then have $(123)4567 \vee 1(234)567 = (1234)567$, $(123)4567\vees 1(234)567 = \{(12345)67, (12346)57, (12347)56\}$. If it happens that $a$ and $b$ have a unique least upper bound we will write $\exists ! \; a\veek b$, and then denote by $a \veek b$ the (unique) element $x\in a\veek b$.

We write $F(x)$ for $F_{\II}(x)$, the set of factors of $x$ with respect to the building set $\II$ of $\P$ (see Definition \[building\]).

\[G\]

-   For all $x\in\Pk$, we have $F(x)=\textrm{max}\,\GG_{\leq x}$.

-   Let $A,B$ denote the non-singleton blocks of two partitions $a,b\in\GG$. Then we have:

    $A\cap B = \emptyset \;\; \Leftrightarrow \;\;\exists ! \; a\veek b \;\textrm{and}\; a\veek b \notin \GG$.

This Lemma suggests the following definition, which mimics Definition \[nested\].

[Let $\NN$ denote the family of all subsets $N\subseteq \GG$ such that for any set of more than two incomparable elements $ \{x_1,\dots , x_\ell\} \subseteq N$ we have that $\exists ! \; x_1\veek\dots\veek x_\ell$ and $ x_1\veek\dots\veek x_\ell \notin \GG $.]{}

The following statement can be viewed as the analogue of [@F Theorem 3.1] in our context. After the above preparations, the proof is an easy check of the definitions.

[With the identification of the elements of $\GG$ with the vertices of $\Tk$ given above, $\NN = \Tk$ as simplicial complexes. $\square$\[TN\] ]{}

We carry on the analogy. For $x\in\Pk$ let us now write $F^k(x):=\textrm{max}\;\GG_{\leq x}$, and given a chain $\omega\in\Delta(\Pk)$, let $F^k(\omega):=\bigcup_{x\in\omega} F^k(x)$. Then we have following suggestive corollary:

[For any $\omega \in \Delta(\Pk)$, $F^k(\omega)\in \NN$.]{}

The poset $\Sigma(N)$
---------------------

For $N \in \NN$ consider $$\Sigma(N):=\Big\{\bigvee_{x\in  X}\!\!{}^{\stackrel{\textstyle k}{}}\, x \vert \; X\subseteq N \Big\} \subseteq \Pk,$$ the set of all joins of subsets of $N$, with the induced order (the join over the empty set gives the minimal element). Note that $N\in\NN$ implies in particular that for every $A \subseteq N$ the join $\bigvee^k_{x\in A}x$ exists and is unique. The join in $\Sigma(N)$ will be denoted by $\vee$.

[\[rmk\] For all $a\in\Sigma(N)$ we have $a=\bigvee\!{}^{\stackrel{\scriptstyle k}{}} N_{\leq a}=\bigvee\textrm{max}\,N_{\leq a}$.]{}

[ The poset $\Sigma(N)$ is a lattice, and $N$ is a building set for $\Sigma(N)$. ]{}

Recall that, given a face $s$ of a simplicial complex $K$, we denote by $K_s$ the subcomplex of all faces of $s$.

[\[stellar\] $\Delta (\Sigma (N))$ is obtained from $\NN_{N}$ by a sequence of stellar subdivisions.]{}

[This is obtained as the main result of [@FM], because $\NN_{ N} =
  \NN(\Sigma(N), N)$. The atomicity condition - needed in [@FM] to construct an explicit realization of the complex - can here be dropped: $\NN_{N}$ is a simplex and we have a standard geometrical realization for it. The subdivisions can be still described as combinatorial blowups in the face poset. $\square$]{}

We have to take a closer look at the carrier maps of that subdivision.

[\[blowup\] Let $\LL$ be an atomic semi-lattice, $\HH\subseteq\GG$ two building sets of $\LL$. The carrier $\tau(N)$ of a simplex $N$ of the nested set complex $\NN(\LL,\GG)$ in the subdivision of $\NN(\LL,\HH)$ by $\NN(\LL,\GG)$ is given by $$\tau(N)=\bigvee_{x\in N} F_{\HH}(x) \; \in \FF(\NN(\LL,\HH)).$$]{}

Every linear extension $h_1,h_2,h_3,\dots, h_\ell$ of the order of $\LL$ on $\GG\setminus\HH$ gives a sequence of stellar subdivisions leading from $\NN(\LL,\HH)$ to $\NN(\LL,\GG)$ (see [@FM]). We proceed by induction on $k$.

If $\ell=1$, then $\NN(\LL,\GG)$ is obtained from $\NN(\LL,\HH)$ by stellar subdivision of the simplex $F_{\HH}(h_1)$, so that the vertex map $f^0: V(\NN(\LL,\GG))\rightarrow |\NN(\LL,\HH)|$ maps $h_1$ to the barycenter of $F_{\HH}(h_1)$, whereas $f^0(v)=|v|$ for all $v\neq h_1$. The carrier of $N\in\NN(\LL,\GG)$ is the smallest simplex $\tau(N)$ in $\NN(\LL,\HH)$ such that $f^0(N)\subseteq |\tau(N)|$. This is the same to say that $\tau(N)$ is the smallest simplex containing the carrier of every vertex of $N$, hence $\tau(N)=\bigvee_{x\in N} F_{\HH}(x)$.

Now let $\ell>1$, define $\HH_{\ell}:=\GG\setminus\{h_\ell\}$ and let $\tau_\ell(N)$ be the carrier of $N\in\NN(\LL,\GG)$ in $\NN(\LL,\HH_\ell)$. By the argument given in the case $\ell=1$, we have $\tau_\ell(N)=\bigvee_{x\in N} F_{\HH_\ell}(x)$.

Note that, with respect to $\NN(\LL,\HH)$, the carrier of $N\in\NN(\LL,\GG)$ is the same as the carrier of $\tau_\ell(N)\in\NN(\LL,\HH_\ell)$. Using the induction hypothesis we can now write:

$$\tau(N)=\bigvee_{y\in \tau_\ell(N)} F_\HH (y) = 
\left\{\begin{array}{ll}
\bigvee_{x\in N} F_\HH (x) & \textrm{if } h_\ell \not\in N, \\
\bigvee_{x\in N\setminus\{h_\ell\}} F_\HH(x) \vee F_\HH(F_{\HH_\ell}(h_\ell)) & \textrm{if } h_\ell \in N.
\end{array}\right.$$

Because $\HH \subset \HH_\ell$, we have $ F_\HH(F_{\HH_\ell}(h_\ell))=F_{\HH}(h_\ell)$. Hence in any case the claim follows.$\square$

As in the proof of Corollary \[stellar\], the atomicity condition is needed in the general statement to construct an explicit geometric realization of the nested set complex. We again note that, in our case, the lattice $\Sigma(N)$ is not atomic but the nested set complexes to which we apply the result of [@FM] are always simplices. We have then following application of Proposition \[blowup\]:

[\[carrmap\] For $N\in\NN$, the map $$\begin{array}{rccc}
\phi_N : & \FF(\Delta(\Sigma(N)))& \rightarrow& \FF(\NN_N) \\
         &    \omega     & \mapsto    &  F^{(k)}(\omega)
\end{array}$$ is the carrier map of the subdivision of $\NN_N$ by $\Delta(\Sigma(N))$ described in Corollary \[stellar\].]{}

Proposition \[blowup\] gives $\phi_N(\omega)=\bigvee_{x\in\omega} F^{(k)}(x)$. So we only have to show that the right hand side equals $F^{(k)}(\omega)$. For this, it is enough to show

[**Claim**]{}

:   [*Let $\LL$ be a semi-lattice and $\GG$ a building set in $\LL$. Then $x>y\in\LL$ implies $F(x)\vee F(y)= F(x) \cup F(y)$ in $\FF(\NN(\LL,\GG))$.* ]{}

Proof

:   We show that $F(x)\cup F(y)$ is nested. Since the set of factors of an element is nested, we only need to show that for two incomparable elements $z_1\in F(x)$ and $z_2\in F(y)$, the join $z_1\vee z_2$ is not in $\GG$. From $x>y$ we know that $z_1 \vee z_2 \leq x$ and there is exactly one $z\in F(x)$ such that $z_2\leq z$ (see [@FK 2.5]). Recall the isomorphism $\varphi_x$ in definition \[building\]: w.l.o.g. we can write $z_1\vee z_2 = \varphi_x(z_1,z_2,0,\dots,0)$, and this cannot be in $\GG$ because the preimage of any element of $\GG_{\leq x} = \bigcup_{z\in F(x)}[\hat{0},z]$ has only one nonzero entry.$\square$

The subdivision
---------------

After explicit study of the geometric structure of the subdivisions, we are now able to check the conditions of Lemma \[lemma\], and use it to prove our theorem.

[\[teorema\] $\Delta(\Pk)$ is a subdivision of $\Tk$]{}

Consider the map $$\begin{array}{rccc}
\phi : & \FF(\Delta(\Pk))& \rightarrow& \FF(\NN) \\
         &    \omega     & \mapsto    &  F^{(k)}(\omega).
\end{array}$$ It is easy to see that $\phi^{-1}(\FF(\NN)_{\leq N})=\FF(\Delta(\Sigma(N)))$, hence by Proposition \[carrmap\] the maps $\phi_N: \phi^{-1}(\FF(\NN)_{\leq N})\rightarrow \FF(\NN)_{\leq N}$ are carrier maps.

For compatibility note that $\Delta(\Sigma(N_1)) \cap \Delta(\Sigma(N_2)) = \Delta (\Sigma(N_1 \cap N_2))$ and that, for any $N$, $f^0_N (v)$ is the barycenter of $|F^{(k)}(v)|$. It is then clear that $f^0_{N_1}\!\!\upharpoonright_{V(\Delta(\Sigma(N_1))) \cap V(\Delta(\Sigma(N_2)))} = f^0_{N_1\cap N_2} = f^0_{N_2}\!\!\upharpoonright_{V(\Delta(\Sigma(N_1))) \cap V(\Delta(\Sigma(N_2)))}$.

With Lemma \[lemma\] we conclude that $\phi$ is a carrier map.$\square$

[$\;\!$]{} As in [@FM], we see that every linear extension of $\Sigma(N)\setminus N$ gives a valid sequence of stellar subdivisions leading from $\NN_{N}$ to $\Delta(\Sigma(N))$. By the compatibility checked in \[carrmap\] and \[teorema\] it is easy to see that a valid sequence of stellar subdivisions leading from $\Tk$ to $\Delta(\Pk)$ can be obtained from any linear extension of $\Pk\setminus \GG$.

To conclude this note let us consider the natural action of the symmetric group $S_m$ on the complex $\Tk$ (by permutation of leaves) and on the poset $\Pk$ (by permutation of elements). The correspondence of Lemma \[TN\] is obviously $S_m$-equivariant. One can check that the carrier maps of the (whole) subdivision are also $S_m$-equivariant, even if at some single subdivision step this may not be true. We then recover the result of [@H], [@HW]:

[The top degree homology modules of $\Tk$ and $\Pk$ are isomorphic as $S_m$-modules: $$\widetilde{H}_{n-3}(\Tk) \cong_{S_m} \widetilde{H}_{n-3}(\Pk).$$]{}

[WWW]{}

F. Ardila, C.Klivans; [*The Bergman complex of a matroid and phylogenetic trees.*]{} preprint, ArXiv math.CO/0311370, J. Combin. Theory Ser. B, to appear.

L. Billera, S. Holmes, K. Vogtmann; [*Geometry of the space of phylogenetic trees.*]{} Adv. in Appl. Math. [**27**]{} (2001), 733-767.

A. Björner; [*Shellable and Cohen-Macaulay partially ordered sets.*]{} Trans. Amer. Math. Soc. [**260**]{} (1980), 159-183.

A.Björner, M.Wachs; [*Shellable nonpure complexes and posets.*]{} Trans. Amer. Math. soc. [**348**]{} [*(part I)*]{}, 1299-1327 and [**349**]{}, 3945-3975 [*(part II)*]{}.

J. M. Boardman; [*Homotopy structures and the language of trees.*]{} Proc. Symp. Pure Math. [**22**]{} (1971), 37-58.

A. Calderbank, P. Hanlon, R. Robinson; [*Partitions into even and odd block size and some unusual characters of the symmetric groups.*]{} Proc. London Math. Soc. (3) [**53**]{} (1986), 288-320.

C. De Concini, C. Procesi; [*Wonderful models of subspace arrangements.*]{} Selecta Math. (N.S.) [**1**]{} (1995), no. 3, 495-535.

E. M. Feichtner; [*Complexes of trees and nested set complexes.*]{} ArXiv math.CO/0409235.

E. M. Feichtner, D. N. Kozlov; [*Incidence combinatorics of resolutions.*]{} Selecta Math. (N.S.) [**10**]{} (2004), no. 1, 37-60.

E. M. Feichtner, I. Müller; [*On the topology of nested set complexes.*]{} Proc. Amer. Math. Soc. [**133**]{} (2005), no.4, 999-1006.

E. M. Feichtner, S. Yuzvinsky; [*Chow rings of toric varieties defined by atomic lattices.*]{} Invent. Math. [**155**]{} (2004), no. 3, 515-536.

P. Hanlon; [*Otter’s method and the homology of homeomorphically irreducible $k$-trees.*]{} J. Combin. Theory Ser. A [**74**]{} (1996), no. 2, 301-320.

P. Hanlon, M. Wachs; [*On Lie $k$-algebras.*]{} Adv. Math. [**113** ]{} (1995), no. 2, 206-236.

A. Robinson, S. Whitehouse; [*The tree representation of $\Sigma\sb {n+1}$.*]{} J. Pure Appl. Algebra [**111**]{} (1996), no. 1-3, 245-253.

E. H. Spanier; [*Algebraic topology.*]{} Springer-Verlag, New York-Berlin, 1981.

H. Trappmann, G. M. Ziegler; [*Shellability of complexes of trees.*]{} J. Combin. Theory Ser. A [**82**]{} (1998), 168-178.

K. Vogtmann; [*Local structure of some ${\rm Out}(F\sb n)$-complexes.*]{} Proc. Edinburgh Math. Soc. (2) [**33**]{} (1990), no. 3, 367-379.

M. Wachs; talk at Banff International Research Station, May 2003, slides available at `http://www.math.miami.edu/~wachs/talks.html`.

G.M. Ziegler; [*Shellability of chessboard complexes.*]{} Israel J. of math. [**87**]{}, 97-110.

[^1]: [MSC 2000 Classification:]{} primary 05E25, secondary 57Q05.