nLab
product of simplices

Contents

Context

Limits and colimits

Homotopy theory

homotopy theory, (∞,1)-category theory, homotopy type theory

flavors: stable, equivariant, rational, p-adic, proper, geometric, cohesive, directed

models: topological, simplicial, localic, …

see also algebraic topology

Introductions

Definitions

Paths and cylinders

Homotopy groups

Basic facts

Theorems

Contents

Idea

This page describes aspects of the combinatorics of Cartesian products of simplicial sets, mostly by describing (Prop. ) the non-degenerate simplicices inside a Cartesian product Δ[p]×Δ[q]\Delta[p] \times \Delta[q] of basic n-simplices for n=p,qn = p,q. These are enumerate by the (p,q)(p,q) (un-)shuffles in a manner that for simplicial abelian groups is originally known from the Eilenberg-Zilber map.

Products of simplicial sets

Proposition

(cartesian product of simplicial sets)
For K,LK, L \,\in\, SimplicialSets, their Cartesian product,

K×LSimplicialSets K \times L \;\in\; SimplicialSets

is the simplicial set whose kkth component set is the Cartesian product of Sets of the components of the two factors

(1)(K×L) k=K k×L k, (K\times L)_k \;=\; K_k \times L_k \,,

and whose face- and degeneracy maps are, similarly, the image under the Cartesian product-functor of the face- and degeneracy maps of the factors:

(2)d i K×L(x,y)=(d i K(x),d i L(y)),s i K×L(x,y)=(s i K(x),s i L(y)) d^{K \times L}_i(x,y) \;=\; \big( d^K_i(x), \, d^L_i(y) \big) \,, \;\;\;\;\; s^{K \times L}_i(x,y) \;=\; \big( s^K_i(x), \, s^L_i(y) \big)

Proof


Since SimplicialSets is a category of presheaves, namely over the simplex category, this is a special case of the general fact that limits of presheaves are computed objectwise.

But it is also immediate to check that (2) with (1) satisfies the defining universal property of the Cartesian product.

Remark

(degenerate simplices in product of simplicial sets) Prop. means in particular that a simplex of the form (s α(x),s β(y)K×L(s_\alpha(x), s_\beta(y) \in K \times L may be non-degenerate even though its two components are each degenerate (see the archetypical Example below).

Indeed, the proposition says that the degenerate simplices in K×LK \times L are precisely those such that their two simplex-components in KK and LL, respectively, are in the image of the same degeneracy map α=β\alpha = \beta.

Non-degenerate cells in a product of simplices

Characterization

Proposition

(non-degenerate (p+q)(p+q)-simplices in Δ[p]×Δ[q]\Delta[p] \times \Delta[q])
For p,qp,q \,\in\, \mathbb{N}, the non-degenerate simplices in the Cartesian product (Prop. )

Δ[p]×Δ[q] \Delta[p] \times \Delta[q]

of standard simplices in sSet correspond, under the Yoneda lemma, to precisely those morphisms of simplicial sets

(3)Δ[p+q]σΔ[p]×Δ[q] \Delta[p+q] \xrightarrow{\;\; \sigma \;\;} \Delta[p] \times \Delta[q]

which satisfy the following equivalent conditions:

(e.g. Kerodon 2.5.7.2: 00RH)

Such morphisms may hence be represented by paths

  • on a (p+1)×(q+1)(p+1)\times(q+1)-lattice,

  • from one corner to its opposite corner,

  • consisting of p+qp+q unit steps,

  • each either horizontally or vertically:

Proof

From Prop. it is clear (Rem. ) that a simplex σ\sigma (3) is degenerate precisely if, when regarded as a path as above, it contains a constant step, i.e. one which moves neither horizontally nor vertically. But then – by degree reasons, since we are looking at paths of p+qp + q steps in a lattice of side length pp and qq – it must be that the path proceeds by p+qp + q unit steps.

Remark

(sequence-notation for simplices in a product of simplices)
Written as a pair of (p+q)(p+q)-simplices, one in Δ[p]\Delta[p] and one in Δ[q]\Delta[q], the non-degenerate simplex (3) is a pair of monotone lists of natural numbers

(0 0 1 1 2 p 0 i i j j q), \left( \begin{array}{ccccccccc} 0& \ldots & 0 & 1 & \ldots & 1 & 2 & \ldots & p \\ 0& \ldots & i & i & \ldots & j & j & \ldots & q \end{array} \right) \,,

such that one row has a constant step precisely where the other has not.

Here is a slightly alternative way to think of these non-degenerate simplices:

Definition

For XX some simplicial set xX px \in X_p some pp-cell and for μ=(μ 1<μ 2,<<μ q)\mu = (\mu_1 \lt \mu_2, \lt \cdots \lt \mu_q) a sequence of natural numbers in {0,p+q}\{0, \cdots p+q\}, write

s μ:X pX p+q s_\mu \colon X_p \to X_{p+q}

for the map dual to the sequence

[p+q]σ μ q[p+q1]σ μ q1σ μ 1[p], [p+q] \stackrel{\sigma_{\mu_q}}{\to} [p+q-1] \stackrel{\sigma_{\mu_{q-1}}}{\to} \cdots \stackrel{\sigma_{\mu_1}}{\to} [p] \,,

where σ i\sigma_i is the surjective monotone map that repeats the index ii.

Proposition

The non-degenerate simplices in the Cartesian product (Prop. )

Δ[p]×Δ[q] \Delta[p] \times \Delta[q]

of simplices in sSet are precisely those of the form

(s μx,s νy)(Δ[p]×Δ[q]) p+q (s_\mu x , s_\nu y) \in (\Delta[p] \times \Delta[q])_{p+q}

for (μ,ν)(\mu,\nu) a (p,q)(p,q)-shuffle and x,yx, y non-degenerate simplices in Δ[p]\Delta[p] and Δ[q]\Delta[q], respectively.

Examples

Example

(cylinders of simplices)

The non-degenerate (n+1)-simplices in the cylinder of the n-simplex

Δ[1] × Δ[n]sSet \begin{aligned} & \Delta[1] \\ \times & \Delta[n] \end{aligned} \;\in\; sSet

are, according to Prop. and in the notation of Remark , as follows:

([0 1 1 1 1 1 1] [0 0 1 2 3 n1 n]), \left( \;\, \array{ \mathllap{[} 0 & 1 & 1 & 1 & 1 & \cdots & 1 & 1 \mathrlap] \\ \mathllap[ 0 & 0 & 1 & 2 & 3 & \cdots & n-1 & n \mathrlap] } \;\, \right) \,,


([0 0 1 1 1 1 1] [0 1 1 2 3 n1 n]) \left( \;\, \array{ \mathllap{[} 0 & 0 & 1 & 1 & 1 & \cdots & 1 & 1 \mathrlap] \\ \mathllap[ 0 & 1 & 1 & 2 & 3 & \cdots & n-1 & n \mathrlap] } \;\, \right)


([0 0 0 1 1 1 1] [0 1 2 2 3 n1 n]), \left( \;\, \array{ \mathllap{[} 0 & 0 & 0 & 1 & 1 & \cdots & 1 & 1 \mathrlap] \\ \mathllap[ 0 & 1 & 2 & 2 & 3 & \cdots & n-1 & n \mathrlap] } \;\, \right) \,,


([0 0 0 0 1 1 1] [0 1 2 3 3 n1 n]), \left( \;\, \array{ \mathllap{[} 0 & 0 & 0 & 0 & 1 & \cdots & 1 & 1 \mathrlap] \\ \mathllap[ 0 & 1 & 2 & 3 & 3 & \cdots & n-1 & n \mathrlap] } \;\, \right) \,,

and so on.

Example

(non-degenerate simplices in simplicial square)
The complete set of non-degenerate simplices in Δ[1]×Δ[1]\Delta[1] \times \Delta[1] is, in specialization of Example , according to Prop. and in the notation of Remark , the following:

See also Friedman 2008, Fig. 20.

Example

The non-degenerate simplices in

Δ[2] × Δ[1] \begin{aligned} & \Delta[2] \\ \times & \Delta[1] \end{aligned}

are, in specialization of Example , according to Prop. and in the notation of Remark , the following three:

([0 1 2 2] [0 0 0 1]),([0 1 1 2] [0 0 1 1]),([0 0 1 2] [0 1 1 1]) \left( \;\, \array{ \mathllap{[} 0 & 1 & 2 & 2 \mathrlap] \\ \mathllap[ 0 & 0 & 0 & 1 \mathrlap] } \;\, \right) \,, \;\;\;\;\;\;\; \left( \;\, \array{ \mathllap{[} 0 & 1 & 1 & 2 \mathrlap] \\ \mathllap[ 0 & 0 & 1 & 1 \mathrlap] } \;\, \right) \,, \;\;\;\;\;\;\; \left( \;\, \array{ \mathllap{[} 0 & 0 & 1 & 2 \mathrlap] \\ \mathllap[ 0 & 1 & 1 & 1 \mathrlap] } \;\, \right)

In terms of partitions

Each such simplex yields a partition of {0,,p+q1}\{0, \ldots, p+q-1\} into two disjoint sets, μ 1<<μ p\mu_1\lt\ldots \lt\mu_p, and ν 1<<ν q\nu_1 \lt \ldots \lt \nu_q, and vice versa, any such partition yields a simplex. Suppose that we have an array, as above, written

(i 0 i 1 i p+q j 0 j 1 j p+q), \left( \begin{array}{cccc} i_0& i_1&\ldots & i_{p+q} \\ j_0& j_1 & \ldots & j_{p+q} \end{array} \right) \,,

with 0=i 0i 1i p+q=p0= i_0 \leq i_1 \leq \ldots \leq i_{p+q}= p, then if i k=i k+1i_k = i_{k+1}, we put kk into the second set, otherwise kk is put in the first set. This, of course, leads to an operation that preserves order. For instance, in the above example 2., the ii-sequence is (0,1,1,2)(0,1,1,2), so there is the single repeat with k=1k = 1, and ν={1}\nu = \{1\}.

We likewise require 0=j 0j 1j p+q=p0= j_0 \leq j_1 \leq \ldots \leq j_{p+q}= p, and put kk into the first set if j k=j k+1j_k = j_{k+1}. For the example, we have the jj-sequence is (0,0,1,1)(0,0,1,1), so μ={0,2}\mu = \{ 0,2\}. Of course, from the partition you can get the sequences and conversely. The attentive reader will, of course, have noted that, for example 2., the α\alpha, we specified was exactly the ν\nu, and the β\beta was the μ\mu. This is general with the simplex corresponding to a partition, (μ,ν)(\mu,\nu), being given by (s ν qs ν 1x p,s μ ps μ 1y q)(s_{\nu_q}\ldots s_{\nu_1}x_p,s_{\mu_p}\ldots s_{\mu_1}y_q).

Each such partition defines a permutation of {0,,p+q1}\{0,\ldots, p+q-1 \}. Let us write ι 0:{0,,q1}{0,,p+q1}\iota_0 : \{ 0, \ldots, q-1\}\to \{0, \ldots, p+q-1\} for the order preserving function ι 0(r)=p+r\iota_0 (r)= p+r, whilst ι 1:{0,,p1}{0,,p+q1}\iota_1 : \{ 0, \ldots, p-1\}\to \{0, \ldots, p+q-1\} will denote the inclusion, so ι 1(r)=r\iota_1(r) = r. There will be a permutation σ\sigma of {0,,p+q1}\{0,\ldots, p+q-1 \} such that σι 0(r)=ν r+1\sigma \iota_0(r) = \nu_{r+1} and σι 1(r)=μ r+1\sigma\iota_1(r) = \mu_{r+1}. This means that the permutation looks like

σ=(0 1 2 p1 p p+1 p+q1 μ 1 μ 2 μ 3 μ p ν 1 ν 2 ν q).\sigma =\left(\begin{array}{ccccccccc}0&1&2& \ldots & p-1&p&p+1& \ldots & p+q-1\\ \mu_1&\mu_2&\mu_3&\ldots & \mu_p&\nu_1&\nu_2&\ldots &\nu_q\end{array}\right).

We can thus assign a sign, sgn(σ)sgn(\sigma), to each such shuffle, namely the sign of the corresponding permutation.

For our standard examples, we have : 1) σ\sigma is the identity, 2) σ=(0 1 2 0 2 1)\sigma = \left(\begin{array}{ccc}0&1&2\\0&2&1\end{array}\right), i.e. the transposition exchanging 1 and 2, and for 3) σ=(0 1 2 1 2 0)\sigma = \left(\begin{array}{ccc}0&1&2\\1&2&0\end{array}\right), a 3-cycle. We thus have, in this case, the signs are +1, -1, and + 1, respectively.

The poset of (p,q)(p,q)-shuffles

Any pair (p,q)(p,q) yields a poset relating the various (p,q)(p,q)-shuffles.

Our (2,1)(2,1)-example is really too simple and small to illustrate this well, but the two cases (3,1)(3,1) and (2,2)(2,2) do a much better job, but, even so, we first look at the (2,1) example:

(0<1) (0<2) (1<2)\begin{matrix} (0\lt 1)&-&(0\lt 2)&-&(1\lt 2)\end{matrix}

(This Hasse diagram has been laid out horizontally to save space. The bottom is to the left. The vertex (0<1)(0\lt 1) corresponds to the shuffle with μ 1=0,μ 1=1\mu_1 = 0, \mu_1 = 1, and so on.)

We need here to explain the partial order. We take the ‘μ\mu-signature’ of the shuffle, that is, the ordered set μ 1<<μ p\mu_1\lt\ldots \lt \mu_p. (Of course, this determines the ν\nu-signature as that is the complement of μ\mu.)

Definition

Given two (p,q)(p,q)-shuffles, represented by (μ,ν)(\mu, \nu) and (μ,ν)(\mu\prime,\nu\prime), we set

(μ,ν)(μ,ν)(\mu, \nu) \leq (\mu\prime,\nu\prime)

if, for each ii in the range 1ip1\leq i\leq p, μ iμ i.\mu_i \leq \mu_i\prime. We refer to this poset as (Shuff(p,q),)(Shuff(p,q),\leq).

Going to (Shuff(3,1),)(Shuff(3,1),\leq), the poset for (3,1)(3,1)-shuffles, the fact that q=1q = 1 will mean that this poset is again linear:

(0<1<2) (0<1<3) (0<2<3) (1<2<3)\begin{matrix} (0 \lt 1 \lt 2) &-& (0 \lt 1 \lt 3)& - &(0 \lt 2 \lt 3)& - &(1 \lt 2 \lt 3) \end{matrix}

This is true in general:

Lemma

If p=1p = 1 or q=1q = 1, then (Shuff(p,q),)(Shuff(p,q),\leq) is a linear poset.

Proof

If p=1p = 1, μ=(μ 1)\mu = (\mu_1) is a singleton, and the poset will be:

(0) (1) (q).\begin{matrix} (0) & - & (1) & - & \ldots & - & (q). \end{matrix}

For q=1q = 1, ν=(ν 1)\nu = (\nu_1), and the poset is

(0<1<<p1) (0<1<<p2<p) (1<<p),\begin{matrix} (0 \lt 1 \lt \ldots \lt p-1) & - & (0 \lt 1 \lt \ldots \lt p-2 \lt p) & - & \ldots & - & (1 \lt \ldots \lt p), \end{matrix}

where at each stage one misses out the single ν\nu-value.

In all cases, each position is obtained from the one immediately to its ‘left’ by increasing one value, yet remaining with a shuffle. This is more clearly seen in the (2,2) example, which is no longer linear. First we display the grid in which things are happening.

(0,2) (1,2) (2,2) | | | (0,1) (1,1) (2,1) | | | (0,0) (1,0) (2,0)\begin{matrix} (0,2) & - & (1,2) & - & (2,2) \\ | & & | & & | \\ (0,1) & - & (1,1) & - & (2,1) \\ | & & | & & | \\ (0,0) & - & (1,0) & - & (2,0) \end{matrix}

We can then look at the shuffle poset, noting again that it is not linear:

The left hand shuffle, labelled (0<1)(0\lt1), corresponds to (0 1 2 2 2 0 0 0 1 2)\left(\begin{array}{ccccc}0&1&2&2&2\\0&0&0&1&2\end{array}\right), so gives the path along the bottom of the square and then up the right hand side.

The first change goes to (0<2)(0\lt 2) and gives a path with 2 steps,

and corresponds to the shuffle, (0 1 1 2 2 0 0 1 1 2)\left(\begin{array}{ccccc}0&1&1&2&2\\0&0&1&1&2\end{array}\right), so at this position, (0<2)(0\lt2), there is a choice, either increase 0 by 1 to get (1<2)(1\lt 2) or increase 2 by 1 to get (0<3)(0\lt3). In the first case, we get the path

going horizontally across the square, and the shuffle, (0 0 1 2 2 0 1 1 1 2)\left(\begin{array}{ccccc}0&0&1&2&2\\0&1&1&1&2\end{array}\right), and in the second case, we get the shuffle: (0 1 1 1 2 0 0 1 2 2)\left(\begin{array}{ccccc}0&1&1&1&2\\0&0&1&2&2\end{array}\right), and the obvious path up the middle of the square:

From (1<2)(1 \lt 2) or (0<3)(0\lt3), there is only one way to go, namely to (1<3)(1 \lt 3) and a 2-step path (left to you), and, finally it is just one step from (1<3)(1 \lt 3) to (2<3)(2 \lt 3) and the other extremal path.


In summary, each path corresponds to a simplex of maximal dimension in the product. The poset encodes the simplest relationships between those paths with the links in the Hasse diagram corresponding to simple changes in the path, and adjacency of the two simplices in the product, but note that the poset is usually not linear.

The Anti-Lex order

There is a total order on Shuff(p,q)Shuff(p,q) related to the above partial order and which is useful when checking cancellation of terms in non-commutative contexts, as occurs in the Whitehead product formula given by Curtis and attributed to Kan. This is the anti-lexicographic order.

We represent a (p,q)(p,q)-shuffle (μ,ν)(\mu,\nu) by an increasing μ\mu-sequence μ 1<<μ p\mu_1\lt \ldots \lt \mu_p, (so with complementary ν\nu-sequence ν 1<<ν q\nu_1\lt \ldots \lt \nu_q).

We order the (μ,ν)(\mu,\nu) using just the μ\mu-sequence as, of course, that determines the ν\nu-sequence completely. Inductively in pp, we set

μ=(μ 1,,μ p)μ=(μ 1,,μ p),\mu = (\mu_1,\ldots, \mu_p)\prec \mu\prime = (\mu\prime_1,\ldots, \mu\prime_p),

(i) if μ p<μ p\mu_p\lt \mu\prime_p,

or

(ii) if μ p=μ p\mu_p = \mu\prime_p and μ p\mu_p is odd,

(μ 1,,μ p1)(μ 1,,μ p1),(\mu_1,\ldots, \mu_{p-1})\prec (\mu\prime_1,\ldots, \mu\prime_{p-1}),

whilst if μ p=μ p\mu_p = \mu\prime_p and μ p\mu_p is even,

(μ 1,,μ p1)(μ 1,,μ p1),(\mu_1,\ldots, \mu_{p-1})\succ (\mu\prime_1,\ldots, \mu\prime_{p-1}),

where we adopt the notation (μ 1,,μ p)(\mu_1,\ldots, \mu_p) instead of (μ 1<<μ p)(\mu_1\lt\ldots \lt \mu_p).

For example, on our (2,2)-shuffles, the total order is

(0,1)(1,2)(0,2)(0,3)(1,3)(2,3).(0,1) - (1,2) - (0,2) - (0,3) - (1,3) - (2,3).

We note the lexicographic order on the sector with μ 2=2\mu_2 = 2 is reversed.

For illustrative purposes, we will look at two other examples.

First a generic (p,1)(p,1) case: the shuffle poset for (p,1)(p,1) is, more or less,

(0,,p2)(0,,p4,p3,p1)(0,,p4,p2,p1)(1,,p1)(0,\ldots , p-2) - (0,\ldots, p-4,p-3,p-1) - (0, \ldots, p-4,p-2,p-1) - \ldots - (1, \ldots , p-1)

as, at each position, there is only one transposition that can be applied. The anti-lex total order will correspond exactly to this if p1p-1 is odd, but, if p1p-1 is even, it will reverse the order on the last p1p-1 positions giving

(0,,p2)(1,,p1)(0,2,,p1)(0,,p3,p1).(0,\ldots , p-2) - (1, \ldots , p-1) - (0,2, \ldots, p-1) - \ldots - (0,\ldots, p-3,p-1).

There are various points to note. Firstly that if pp is even, the permutation corresponding to (1,,p1)(1, \ldots , p-1) is odd. Secondly, the geometric picture is simply a prism, Δ[p]×Δ[1]\Delta[p]\times \Delta[1], and we can easily interpret the above order as a filling scheme for the simplices of (Δ[p]×Δ[1])×Δ[1](\Delta[p]\times \Delta[1])\times \Delta[1], starting with the empty shell of

(Δ[p]×Δ[1])×{0}(Δ[p]×Δ[1])×Δ[1],(\Delta[p]\times \Delta[1])\times \{0\} \cup \partial(\Delta[p]\times \Delta[1])\times \Delta[1],

together with part of the top of the ‘canister’. (In general the total order seems to correspond to some sort of filling scheme although this is not always as clear as here.)

Our second case will be (3,2). Again we will write (i,j,k)(i,j,k) instead of i<jltki\lt j\ltk in order to save confusion over the various different orders being considered. The shuffle poset, Shuff(3,2)\mathrm{Shuff}(3,2), has Hasse diagram given below:

The subgraph of those with μ 3=4\mu_3 = 4, of course, is a copy of our earlier (2,2)(2,2)-example, whilst that with μ 3=3\mu_3 = 3, is a copy of Shuff(3,1)Shuff(3,1). Within that we have, on deleting the 3s from the final positions, a copy of Shuff(2,1)Shuff(2,1) and so on. Taking Shuff(2,1)×{3}Shuff(2,1) \times \{3\}, we can match it with a Shuff(2,1)×{4}Shuff(2,1) \times \{4\} within the μ 3=4\mu_3 = 4 block, the matching being given by, for instance, (0,1,3)(0,1,4)(0,1,3)\leftrightarrow(0,1,4), etc. The anti-lex order gives

(0,1,2)(0,1,3)(1,2,3)(0,2,3)(2,3,4)(1,3,4)(0,3,4)(0,2,4)(1,2,4)(0,1,4), (0,1,2)-(0,1,3) - (1,2,3)-(0,2,3)-(2,3,4)-(1,3,4)-(0,3,4) - (0,2,4) - (1,2,4) - (0,1,4),

which is

Shuff(3,1)Shuff(2,2) op×{4},Shuff(3,1)\oplus Shuff(2,2)^{op}\times \{4\},

the ordinal sum, or join, of the anti-lex ordered shuffle sets. This sort of decomposition is quite general.

References

The shuffle-formula is due (in terms of simplicial abelian groups of chains on a simplicial set, see at Eilenberg-Zilber map) to:

following:

The streamlined perspective of strictly monotonic morphisms Δ[p+q]Δ[p]×Δ[q]\Delta[p+q] \to \Delta[p] \times \Delta[q] is highlighted in

Exposition:

Textbook accounts:

Last revised on August 30, 2021 at 06:04:23. See the history of this page for a list of all contributions to it.