The n-Category Café

Quick Recap

It’s been a while since my last post on this and I don’t want to a big recap but certainly a small recap is in order! I’m interested in transporting goods from a set $\{S_i\}_{i=1}^s$ of suppliers to a set $\{R_j\}_{j=1}^r$ of receivers. (Think of transporting loaves of bread from bakeries to cafés.) We have a supply of $\sigma_i$ units of good at supplier $S_i$ and a demand of $\rho_j$ at receiver $R_j$ and the cost of transporting one unit of goods from $S_i$ to $R_j$ is $k_{ij}\in [0,\infty)$.

We saw that in the dual problem we want to find prices $v=(v_1,\dots,v_s)$ and $u=(u_1,\dots, u_r)$ at the suppliers and receivers respectively that maximize the total revenue $$\sum_j u_j\rho_j -\sum_i v_i\sigma_i$$ subject to the competitivity constraint $k_{ij}\ge u_j-v_i$ for all $i,j$.

I’ll model this is the language of $\bar{\mathbb{R}}_+$-categories. Recall that an $\bar{\mathbb{R}}_+$-category is a generalization of a metric space: in an $\bar{\mathbb{R}}_+$-category $X$ we have a ‘hom-object’ $X(a,b)\in [0,\infty]$ between each pair of objects $a,b\in X$. This hom-object should be thought of as a distance which does not have to be finite, nor symmetric, and you can have distinct objects having zero distance between them. The right notion of ‘functor’ here is that of ‘distance non-increasing map’; the term ‘short map’ is used for short.

I model the situation in the following way.

Suppliers:	$\mathcal{S}$,	a discrete $\bar{\mathbb{R}}_+$-category
Receivers:	$\mathcal{R}$,	a discrete $\bar{\mathbb{R}}_+$-category
Transport cost:	$k\colon \mathcal{S}\rightsquigarrow \mathcal{R}$,	an $\bar{\mathbb{R}}_+$-profunctor
Prices at suppliers:	$v\colon \mathcal{S}\to \bar{\mathbb{R}}_+$,	an $\bar{\mathbb{R}}_+$-functor
Prices at receivers:	$u\colon \mathcal{S}\to \bar{\mathbb{R}}_+$,	an $\bar{\mathbb{R}}_+$-functor

Note that I didn’t mention how to model the supply and demand. That is not of immediate interest to us, so I won’t say anything about that now.

We also saw that in finding prices which maximize total revenue we can restrict our attention to ‘tight price plans’, that is pairs of prices $(v; u)$ which lie in the centre $Z_{\mathrm{K}}(k)$ of the following Kan-type adjunction.

The Kan centre is the full subcategory of $\bar{\mathbb{R}}_+^\mathcal{S}\times \bar{\mathbb{R}}_+^\mathcal{R}$ consisting of objects $(v,u)$ such that $k\circ v = u$ and $v=k\triangleright u$; in the notation of previous posts I would write $\hat{v} =u$ and $v=\tilde{u}$.

Note that the Kan-type adjunction is not the same as the Isbell-type (*) adjunction I’ve discussed in previous posts on profunctor nuclei and Isbell tight-spans. I will discuss a relationship between them in a future post.

(*) I don’t like using the terms ‘Kan’ and ‘Isbell’ for these adjunctions, I’d much rather use more descriptive adjectives. It anyone has any ideas…

In this post I want to visualize the Kan centre $Z_{\mathrm{K}}(k)$ for you, and as the Kan centre is a subset of $\bar{\mathbb{R}}_+^\mathcal{S}\times \bar{\mathbb{R}}_+^\mathcal{R}\cong \bar{\mathbb{R}}_+^{\mathcal{S}\sqcup\mathcal{R}}$, it would be wise to start in a case with a very small number of suppliers and receivers, namely where $\left | \mathcal{S}\sqcup\mathcal{R}\right|\le 3$. We will see that we can in fact visualize, in a certain way, higher dimensional cases, but we will start with a slightly silly example — from an optimal transport perspective — to illustrate some basic features.

A first example

Let’s start with two suppliers and one receivers, $|\mathcal{S}|=2$ and $|\mathcal{R}|=1$. I will think of these as bakeries and cafés and I’ll pick some simpler numbers than I did in the old café example I used. The numbers on the arrows represent the cost of transporting one loaf of bread. The numbers in circles represent the supply and demand in loaves of bread.

The profunctor in this situation can be represented by the matrix $k=\left(\begin{smallmatrix}3\\2\end{smallmatrix}\right)$. (I might be regretting my choice of conventions and I might have preferred to have the transpose of this matrix.)

It is clear what the solution to the optimal transport problem is in this case as there’s only one feasible solution, namely both bakeries send all their bread to the one café. But this should be a useful example none-the-less.

We have the adjunction

with

$$k\circ(v_1, v_2)=(\min\{3+v_1, 2+v_2\}) \qquad k\triangleright(u_1) = (u_1\,\dot{{}-{}}\,3, u_1\,\dot{{}-{}}\,2).$$

You can check that the centre is

$$\{((\lambda\,\dot{{}-{}}\,1, \lambda), (2+\lambda))\mid \lambda\in [0,\infty]\} \subset \bar{\mathbb{R}}_+^2\times \bar{\mathbb{R}}_+^1$$

and this (or at least a finite portion of it) can be drawn as follows.

You can observe that this is the union of two closed line segments, or, as might be more useful, that this is the union of two open line segments (one bounded, one unbounded) and two points. In fact, in general the Kan centre is a cell complex of open, piece-wise affine cells.

Another thing to observe here is that if $(v,u)$ is a pair in the Kan centre then $v$ determines $u$ and $u$ determines $v$, so we can project onto $\bar{\mathbb{R}}_+^2$ or $\bar{\mathbb{R}}_+^1$ without losing any information. Here are the projections, I’ve drawn the boundary of the view box that I’ve picked, but the picture should be unbounded.

 

Here they are, drawn in a more standard way.

 

Some generalities

Projecting in this way gives us two views of the Kan centre and will allow us to visualize some higher dimensional examples. You need to bear in mind, however, that neither picture is the ‘true’ centre as this naturally sits in the higher dimensional space. For instance, the total revenue function can be restricted to the tight price plans, i.e. the centre, this is the restriction of a linear function when the centre is considered as a subset of $(v,u)$-space, but it is not the restriction of a linear function when the centre is considered as a subset of $v$-space or $u$-space. Remember that we are hoping to maximize the total revenue function on the Kan centre.

There’s a very general statement about adjunctions when enriching over commutative quantales like $\bar{\mathbb{R}}_+$. I won’t go into the details, many of which can be found in my Legendre-Fenchel transform paper. Anyway, roughly speaking, for an adjunction $L\dashv R$ between $\bar{\mathbb{R}}_+$-categories we have a counit $L R\Rightarrow\mathrm{id}$ and a unit $\mathrm{id}\Rightarrow R L$, thus we have $R L R\Rightarrow R$ and $R\Rightarrow R L R$ (which means $0\ge \mathcal{C}(R L R(d), R(d))$ and $0\ge \mathcal{C}(R(d), R L R(d))$ for all $d\in \mathcal{D}$) and so $R \cong R L R$. Similarly $L \cong L R L$. We saw that manifested earlier as $\tilde{\hat{\tilde{v}}}= \tilde{v}$. This gives us that any monad on an $\bar{\mathbb{R}}_+$-category is idempotent and also the following.

Lemma 1. For an adjunction $L\dashv R$ between $\bar{\mathbb{R}}_+$-categories $\mathcal{C}$ and $\mathcal{D}$ there is the following identification of categories where $\mathrm{Im}$ denotes the image of a functor and $\mathrm{Fix}$ denotes the fixed category of an endofunctor.

So in our case this means that the left-hand view or the space of tight price plans on the suppliers can be thought of as the image of the functor $k\triangleright{-}$, or as the fixed space of the monad $k\triangleright(k\circ{-})$.

Examples

Here are some more examples. In each case I’ll give the profunctor and then pictures of the two views of the Kan-type centre, or, if you prefer, the tight price plans.

I computed these (as cell complexes) using some rather inefficient SageMath code; however, having seen what they look like I now realise there will be better algorithms out there. I’ll maybe say more on this next time.

$\begin{pmatrix}2&1\\3&5\end{pmatrix}$

 

$\begin{pmatrix}2&7\\3&5\end{pmatrix}$

 

$\begin{pmatrix} 4 & 6 \\ 10 & 5 \\ 11 & 11 \\ 8 & 14 \end{pmatrix}$

 

In the above example I couldn’t actually show you the picture of the left-hand view as I’m not good at putting 4d objects on the the screen. However in the next example, by the magic of three.js, I can (hopefully!) put some fairly basic 3d objects on the screen which you can navigate and move with your mouse/touchpad/fingers. By clicking on the border you should be able to open models in fullscreen if you desire.

Due to laziness on my part, I’ll only show the one-cells; however, the two-cells and three-cells fill in the obvious holes (or at least I think they are obvious).

$\begin{pmatrix} 1 & 4 & 6 \\ 2 & 7 & 1 \\ 8 & 7 & 8 \end{pmatrix}$

 

So there’s some examples to get one thinking.

Next time

I hope that next time I will explain some of the structure of these examples and relate these to the notion of the semi-tropical convex hull. (The tropically aware amongst you might have noticed something convex hully going on.) And later on I would like to compare and contrast these with Isbell-type centres.