\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{product of simplices}

\hypertarget{context}{}\subsubsection*{{Context}}\label{context}

\hypertarget{limits_and_colimits}{}\paragraph*{{Limits and colimits}}\label{limits_and_colimits}

[[!include infinity-limits - contents]]

\hypertarget{homotopy_theory}{}\paragraph*{{Homotopy theory}}\label{homotopy_theory}

[[!include homotopy - contents]]

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{properties}{Properties}\dotfill \pageref*{properties} \linebreak
\noindent\hyperlink{shuffles_and_products_of_simplices}{Shuffles and products of simplices}\dotfill \pageref*{shuffles_and_products_of_simplices} \linebreak
\noindent\hyperlink{nondegenerate_simplices_in_a_product}{Non-degenerate simplices in a product}\dotfill \pageref*{nondegenerate_simplices_in_a_product} \linebreak
\noindent\hyperlink{illustrative_example}{Illustrative example}\dotfill \pageref*{illustrative_example} \linebreak
\noindent\hyperlink{simplices_of_the_product_and_partitions}{Simplices of the product and partitions}\dotfill \pageref*{simplices_of_the_product_and_partitions} \linebreak
\noindent\hyperlink{paths_in_the_product}{Paths in the product}\dotfill \pageref*{paths_in_the_product} \linebreak
\noindent\hyperlink{the_poset_of_shuffles}{The poset of $(p,q)$-shuffles}\dotfill \pageref*{the_poset_of_shuffles} \linebreak
\noindent\hyperlink{easy_examples}{Easy examples}\dotfill \pageref*{easy_examples} \linebreak
\noindent\hyperlink{summary}{Summary}\dotfill \pageref*{summary} \linebreak
\noindent\hyperlink{the_antilex_order}{The Anti-Lex order}\dotfill \pageref*{the_antilex_order} \linebreak


This page describes aspects of the combinatorics of [[product]]s of [[simplicial set]]s.

\hypertarget{properties}{}\subsection*{{Properties}}\label{properties}

\begin{udefinition}
For $X$ some [[simplicial set]] $x \in X_p$ some $p$-cell and for $\mu = (\mu_1 \lt  \mu_2, \lt \cdots \lt \mu_q)$ a sequence of natural numbers in $\{0, \cdots p+q\}$, write

\begin{displaymath}
s_\mu : X_p \to X_{p+q}
\end{displaymath}
for the map dual to the sequence

\begin{displaymath}
[p+q] 
    \stackrel{\sigma_{\mu_q}}{\to}
  [p+q-1]
    \stackrel{\sigma_{\mu_{q-1}}}{\to}
  \cdots
   \stackrel{\sigma_{\mu_1}}{\to}
   [p]
  \,,
\end{displaymath}
where $\sigma_i$ is the surjective monotone map that repeats the index $i$.

\end{udefinition}
\begin{uprop}
The non-degenerate simplices in the [[product]]

\begin{displaymath}
\Delta[p] \times\Delta[q]
\end{displaymath}
of [[simplices]] in [[sSet]] are precisely those of the form

\begin{displaymath}
(s_\mu x , s_\nu y) \in (\Delta[p] \times \Delta[q])_{p+q}
\end{displaymath}
for $(\mu,\nu)$ a $(p,q)$-[[shuffle]] and $x, y$ non-degenerate simplices in $\Delta[p]$ and $\Delta[q]$, respectively.

\end{uprop}
\hypertarget{shuffles_and_products_of_simplices}{}\subsection*{{Shuffles and products of simplices}}\label{shuffles_and_products_of_simplices}

[[shuffle|Shuffles]] are interesting combinatorial structures but the reason why they come into many constructions in [[homotopy theory]] and [[higher category theory]] is because of their relationship with the structure of [[product]]s.

The definition of the product, $K\times L$, of [[simplicial set]]s $K$ and $L$ gives that $(K\times L)_k$ is defined to be $K_k\times L_k$ with face and degeneracy maps defined `componentwise' so, for instance, $d_i(x,y) = (d_i x,d_i y)$. This means that a [[simplex]] $(s_\alpha x, s_\beta y)$ can be non-degenerate even though its two components are degenerate. Of course, this happens exactly when $\alpha \cap \beta = \emptyset$. (Here we mean by $s_\alpha$ the composite, in order, of the $s_i$ for $i \in \alpha$.)

In particular, take $K = \Delta[p]$ and $L= \Delta[q]$ with $x_p \in \Delta[p]_p$, $y_q \in \Delta[q]_q$, the `identity' simplices that generate them. (We will use an \emph{ad hoc} notation here, since the more obvious, $\iota_p$, and $\iota_q$, would not distinguish the two simplices sufficiently in some formulae.) There are, then, non-degenerate simplices of dimension $p+q$, but none of higher dimension in $\Delta[p]\times \Delta[q]$. These are of the form $(s_\alpha x_p,s_\beta y_q)$, where $\#\alpha = q$, $\#\beta = p$.

\hypertarget{nondegenerate_simplices_in_a_product}{}\subsubsection*{{Non-degenerate simplices in a product}}\label{nondegenerate_simplices_in_a_product}

If we represent a vertex of a product by a `column vector' rather than the more usual `row vector' for the moment, then any non-degenerate $(p+q)$-simplex of $\Delta[p]\times \Delta[q]$ can be represented in the form of an ordered list of vertices,

\begin{displaymath}
\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),
\end{displaymath}
with $p + q + 1$ columns. The top row, which is a simplex in $\Delta[p]$, changes at exactly those positions at which the bottom row repeats. The top row gives a degenerate $p+q$ simplex of $\Delta[p]$, whilst the bottom row one of $\Delta[q]$, i.e., the array gives $(s_\alpha x_p, s_\beta y_q)$ for some $(\alpha, \beta)$ as above.

\hypertarget{illustrative_example}{}\subsubsection*{{Illustrative example}}\label{illustrative_example}

The usual illustrative example is of the three 3-simplices of $\Delta[2]\times \Delta[1]$:

\begin{enumerate}%
\item $\left(\begin{array}{cccc}0&1&2&2\\0&0&0&1\end{array}\right)$,


\item $\left(\begin{array}{cccc}0&1&1&2\\0&0&1&1\end{array}\right)$,


\item $\left(\begin{array}{cccc}0&0&1&2\\0&1&1&1\end{array}\right)$



\end{enumerate}
with, for 1), $\alpha = (2)$, $\beta = (1,0)$; for 2) $\alpha = (1)$, $\beta = (2,0)$; and, for 3), $\alpha = (0)$, $\beta = (2,1)$.

\hypertarget{simplices_of_the_product_and_partitions}{}\subsubsection*{{Simplices of the product and partitions}}\label{simplices_of_the_product_and_partitions}

Each such simplex yields a partition of $\{0, \ldots, p+q-1\}$ into two disjoint sets, $\mu_1\lt\ldots \lt\mu_p$, and $\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

\begin{displaymath}
\left(\begin{array}{cccc}
i_0& i_1&\ldots & i_{p+q}\\
j_0& j_1 & \ldots & j_{p+q}
\end{array}\right),
\end{displaymath}
with $0= i_0 \leq i_1 \leq \ldots \leq i_{p+q}= p$, then if $i_k = i_{k+1}$, we put $k$ into the second set, otherwise $k$ is put in the first set. This, of course, leads to an operation that preserves order. For instance, in the above example 2., the $i$-sequence is $(0,1,1,2)$, so there is the single repeat with $k = 1$, and $\nu = \{1\}$.

We likewise require $0= j_0 \leq j_1 \leq \ldots \leq j_{p+q}= p$, and put $k$ into the first set if $j_k = j_{k+1}$. For the example, we have the $j$-sequence is $(0,0,1,1)$, so $\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_{\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,\ldots, p+q-1 \}$. Let us write $\iota_0 : \{ 0, \ldots, q-1\}\to \{0, \ldots, p+q-1\}$ for the order preserving function $\iota_0 (r)= p+r$, whilst $\iota_1 : \{ 0, \ldots, p-1\}\to \{0, \ldots, p+q-1\}$ will denote the inclusion, so $\iota_1(r) = r$. There will be a permutation $\sigma$ of $\{0,\ldots, p+q-1 \}$ such that $\sigma \iota_0(r) = \nu_{r+1}$ and $\sigma\iota_1(r) = \mu_{r+1}$. This means that the permutation looks like

\begin{displaymath}
\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).
\end{displaymath}
We can thus assign a sign, $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) $\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) $\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.

\hypertarget{paths_in_the_product}{}\subsubsection*{{Paths in the product}}\label{paths_in_the_product}

A final useful interpretation of $(p,q)$ shuffles is of ascending paths through a $p$ by $q$ integer lattice from $(0,0)$ to $(p,q)$. This is quite well illustrated by our example. The vertices are the integer pairs, $(i,j)$ with $0\leq i\leq p$ and $0\leq j\leq q$, so in our case we get

\begin{displaymath}
\begin{matrix}
(0,1) & - & (1,1) & - & (2,1) \\
| & & | & & | \\
(0,0) & - & (1,0) & - & (2,0)
\end{matrix}
\end{displaymath}
The path corresponding to a $(p,q)$-shuffle just follows the list of (transposed pairs of) vertices, so, for instance, 2) goes

\begin{displaymath}
\begin{matrix}
 &  & (1,1) & - & (2,1) \\
 & & | & &  \\
(0,0) & - & (1,0) && 
\end{matrix}
\end{displaymath}
\hypertarget{the_poset_of_shuffles}{}\subsubsection*{{The poset of $(p,q)$-shuffles}}\label{the_poset_of_shuffles}

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

\hypertarget{easy_examples}{}\paragraph*{{Easy examples}}\label{easy_examples}

We will start by giving some elementary examples. (This section can be skipped if you want to move on to the more theoretical analysis of these posets.)

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

\begin{displaymath}
\begin{matrix} (0\lt 1)&-&(0\lt 2)&-&(1\lt 2)\end{matrix}
\end{displaymath}
(This [[Hasse diagram]] has been laid out horizontally to save space. The bottom is to the left. The vertex $(0\lt 1)$ corresponds to the shuffle with $\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 $\mu_1\lt\ldots \lt \mu_p$. (Of course, this determines the $\nu$-signature as that is the complement of $\mu$.)

\begin{udefn}
Given two $(p,q)$-shuffles, represented by $(\mu, \nu)$ and $(\mu\prime,\nu\prime)$, we set

\begin{displaymath}
(\mu, \nu) \leq (\mu\prime,\nu\prime)
\end{displaymath}
if, for each $i$ in the range $1\leq i\leq p$, $\mu_i \leq \mu_i\prime.$ We refer to this poset as $(Shuff(p,q),\leq)$.

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

\begin{displaymath}
\begin{matrix}
(0 \lt 1 \lt 2) &-& (0 \lt 1 \lt 3)& - &(0 \lt 2 \lt 3)& - &(1 \lt 2 \lt 3)
\end{matrix}
\end{displaymath}
This is true in general:

\begin{ulemma}
If $p = 1$ or $q = 1$, then $(Shuff(p,q),\leq)$ is a linear poset.

\end{ulemma}
\begin{proof}
If $p = 1$, $\mu = (\mu_1)$ is a singleton, and the poset will be:

\begin{displaymath}
\begin{matrix}
(0) & - & (1) & - & \ldots & - & (q).
\end{matrix}
\end{displaymath}
For $q = 1$, $\nu = (\nu_1)$, and the poset is

\begin{displaymath}
\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}
\end{displaymath}
where at each stage one misses out the single $\nu$-value.

\end{proof}
In all cases, each position is obtained from the one immediately to its `left' by increasing \emph{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.

\begin{displaymath}
\begin{matrix}
(0,2) & - & (1,2) & - & (2,2) \\
| & & | & & | \\
(0,1) & - & (1,1) & - & (2,1) \\
| & & | & & | \\
(0,0) & - & (1,0) & - & (2,0)
\end{matrix}
\end{displaymath}
We can then look at the shuffle poset, noting again that it is not linear:

\begin{displaymath}
\begin{matrix}
&&&&(1\lt 2)&&&&\\
&&& \nearrow &&\searrow &&&\\
(0\lt 1)&-&(0\lt 2)&&&&(1\lt 3)&-&(2\lt 3)\\
&&& \searrow && \nearrow &&&\\
&&&&(0\lt 3)&&&&\\
\end{matrix}
\end{displaymath}
(Arrows have been used where itex does not seem to have an `headless arrow'! What follows is produced via presheaf.com.)

\}

The left hand shuffle, labelled $(0\lt1)$, corresponds to $\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\lt 2)$ and gives a path with 2 steps,



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



going horizontally across the square, and the shuffle, $\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: $\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 \lt 2)$ or $(0\lt3)$, there is only one way to go, namely to $(1 \lt 3)$ and a 2-step path (left to you), and, finally it is just one step from $(1 \lt 3)$ to $(2 \lt 3)$ and the other extremal path.

\hypertarget{summary}{}\paragraph*{{Summary}}\label{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.

\hypertarget{the_antilex_order}{}\subsection*{{The Anti-Lex order}}\label{the_antilex_order}

There is a total order on $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 \textbf{anti-lexicographic order.}

We represent a $(p,q)$-shuffle $(\mu,\nu)$ by an increasing $\mu$-sequence $\mu_1\lt \ldots \lt \mu_p$, (so with complementary $\nu$-sequence $\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 $p$, we set

\begin{displaymath}
\mu = (\mu_1,\ldots, \mu_p)\prec \mu\prime = (\mu\prime_1,\ldots, \mu\prime_p),
\end{displaymath}
(i) if $\mu_p\lt \mu\prime_p$,

or

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

\begin{displaymath}
(\mu_1,\ldots, \mu_{p-1})\prec (\mu\prime_1,\ldots, \mu\prime_{p-1}),
\end{displaymath}
whilst if $\mu_p = \mu\prime_p$ and $\mu_p$ is even,

\begin{displaymath}
(\mu_1,\ldots, \mu_{p-1})\succ (\mu\prime_1,\ldots, \mu\prime_{p-1}),
\end{displaymath}
where we adopt the notation $(\mu_1,\ldots, \mu_p)$ instead of $(\mu_1\lt\ldots \lt \mu_p)$.

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

\begin{displaymath}
(0,1) - (1,2) - (0,2) - (0,3) - (1,3) - (2,3).
\end{displaymath}
We note the lexicographic order on the sector with $\mu_2 = 2$ is reversed.

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

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

\begin{displaymath}
(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)
\end{displaymath}
as, at each position, there is only one transposition that can be applied. The anti-lex total order will correspond \emph{exactly} to this if $p-1$ is odd, but, if $p-1$ is even, it will reverse the order on the last $p-1$ positions giving

\begin{displaymath}
(0,\ldots , p-2) - (1, \ldots , p-1) - (0,2, \ldots, p-1) -  \ldots  - (0,\ldots, p-3,p-1).
\end{displaymath}
There are various points to note. Firstly that if $p$ is even, the permutation corresponding to $(1, \ldots , p-1)$ is odd. Secondly, the geometric picture is simply a prism, $\Delta[p]\times \Delta[1]$, and we can easily interpret the above order as a filling scheme for the simplices of $(\Delta[p]\times \Delta[1])\times \Delta[1]$, starting with the empty shell of

\begin{displaymath}
(\Delta[p]\times \Delta[1])\times \{0\} \cup \partial(\Delta[p]\times \Delta[1])\times \Delta[1],
\end{displaymath}
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)$ instead of $i\lt j\ltk$ in order to save confusion over the various different orders being considered. The shuffle poset, $\mathrm{Shuff}(3,2)$, has Hasse diagram given below:



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

\begin{displaymath}
(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),
\end{displaymath}
which is

\begin{displaymath}
Shuff(3,1)\oplus Shuff(2,2)^{op}\times \{4\},
\end{displaymath}
the ordinal sum, or join, of the anti-lex ordered shuffle sets. This sort of decomposition is quite general.

[[!redirects product of simplices]] [[!redirects products of simplices]]



\end{document}