Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Some simplicial combinatorics

Brendan Murphy (Sep 29 2023 at 20:11):

Let $\Delta$ be the category of finite ordinals $\mathbf{n} = \{ 0,\ldots,n-1 \}$ and montone functions and $\mathsf{Fin}$ the category of finite ordinals and all functions. We then have a forgetful functor $U : \Delta \to \mathsf{Fin}$ which is the identity on objects and is the set-theoretic inclusion on hom sets. Fix $n, m \in \mathbb{N}$ and let $X = \operatorname{Hom}_{\Delta}(\mathbf{n}, \mathbf{m}) \times S_n$. We then have a (surjective) function $\pi : X \to \operatorname{Hom}_{\mathsf{Fin}}(\mathbf{n}, \mathbf{m})$ defined by $\pi(f, \sigma) = f \circ \sigma$. I think I have a proof that $\pi(f, \sigma) = \pi(g, \tau)$ only if $f = g$, but it's very messy. Does anyone see a way of proving this which is either (1) very direct or (2) abstract enough that the proof becomes simple?

Patrick Nicodemus (Sep 29 2023 at 20:22):

I think there's missing context as to how $f,g,\sigma,\tau$ are related. Did you forget to mention something?

Brendan Murphy (Sep 29 2023 at 20:46):

@Patrick Nicodemus I don't think so? The only relationship is that f, g are maps in Δ with the same domain and codomain, and σ, τ live in the same symmetric group

Brendan Murphy (Sep 29 2023 at 20:47):

Oh wait

Brendan Murphy (Sep 29 2023 at 20:47):

I forgot to mention the conclusion, sorry lol

Brendan Murphy (Sep 29 2023 at 20:47):

Fixed, thank you Patrick

Patrick Nicodemus (Sep 29 2023 at 20:49):

not a proof but maybe a helpful reformulation - S_n acts on Hom(n, m). You're asking if there are any two distinct monotonic maps in the same orbit. correct? (WLOG tau can be absorbed into sigma)

Patrick Nicodemus (Sep 29 2023 at 21:32):

Here's my proof. A map $f:n\to m$ partitions $n$ into a family of fibers; let $S = n/\sim$ where $a\sim b$ iff $f(a)=f(b)$ . Given $\sigma$ a permutation of $n$, I construct a directed graph $G_\sigma$. Formally $G_\sigma$ is a function $S\times S\to \mathbb{N}$.
The edge from A to B is weighted by number of elements of A that $\sigma$ sends into B, the cardinality of $A\cap \sigma^-1(B)$. The cardinality of A is equal to the sum of all edge weights for arrows leaving A, and also equal to the sum of edge weights for arrows entering A, so if arrows entering A are weighted negatively then the net flow into a node is zero. (I. e. if $G_\sigma$ is viewed as a matrix the sum of any row is equal to the sum of its transpose column. $G_\sigma \mathbf{1}=G_\sigma^\top \mathbf{1}$.

The nodes of the graph are totally ordered in the obvious way.

Note that if there is an edge from A to B with positive weight and B<A, f\circ \sigma is not monotonic. So we assume that if B<A, the edge from A to B has zero weight. The matrix $G_\sigma$ is upper triangular.
It is now easy to see by induction on rows that $G_\sigma 1=G_\sigma^\top 1$ forces $G_\sigma$ to be lower triangular as well, i. e. concentrated along the diagonal. So $f\sigma =f$.