Monoidal Posets for 1D-Interleavings

Before we defined interleavings of join trees we introduced the poset \(D^{\perp}\) and the two weightings \(\epsilon'\) and \(\epsilon''\) on \(D^{\perp}\). Morozov, Beketayev, and Weber (2013) used a more ad hoc approach and we justified our approach by also introducing the relative interleaving distance. With Reeb graphs we will do something similar and we introduce more formalism than de Silva, Munch, and Patel (2016). The reason for this is two fold. Starting from the approach by de Silva, Munch, and Patel (2016) the author added one layer of formalism to define the relative interleaving distance and then another layer of formalism, which may help with the computation of these interleaving distances. The nice thing about join trees is that we can get both benefits with just one additional layer of formalism whereas here we need two layers, so that a dedicated section is required. In other words we beg the reader to bear with us for one more section until we get to the absolute and relative interleaving distances of Reeb graphs.

  • Definition. Let \(D := {\{(a, b) \in [-\infty, \infty) \times (-\infty, \infty] ~|~ a \leq b\}}\) then \(D\) is a monoid by component-wise addition. Moreover we set \(\mathbf{o} := (0, 0)\) and we define a partial order \(\preceq\) on \(D\) by \((x, y) \preceq (x', y') : \Leftrightarrow x \geq x' \wedge y \leq y' .\)

A set augmented with a partial ordering and a monotone monoid structure like \(D\), we call a monoidal poset. Moreover \(D \times D\) is a monoidal poset with the product ordering and component-wise addition. With some abuse of notation we write \((a, b; c, d)\) for points \(((a, b), (c, d)) \in D \times D\). Next we define three monoidal sub-posets of \(D \times D\).

  • Definition. We set
    \(\mathcal{D} := {\{(a, b; c, d) \in D \times D ~|~ a + c \leq 0 \leq b + d\}}\),
    \(\triangledown := {\{(a, b; c, d) \in \mathcal{D} ~|~ c + b = 0 = a + d\}}\), and
    \(\blacktriangledown := {\{(a, b; c, d) \in \triangledown ~|~ a + b = 0\}}\).

So now we have the chain of monoidal posets \(\blacktriangledown \subset \triangledown \subset \mathcal{D}\). For each of the two inclusions we aim to describe a monotone subadditive map in the other direction.

  • Definition. For \((a, b; c, d) \in \mathcal{D}\) we set \(\delta((a, b; c, d)) := (-d', b'; -b', d')\) where \(b' = \max \{-c, b\}\) and \(d' = \max \{-a, d\}\). And for \((a, b; c, d) \in \triangledown\) we set \(\gamma((a, b; c, d)) := (-\varepsilon, \varepsilon; -\varepsilon, \varepsilon)\) where \(\varepsilon = \max \{b, d\}\).

  • Lemma. For all \(\mathbf{A} \in \mathcal{D}\) and \(\mathbf{B} \in \triangledown\) with \(\mathbf{A} \preceq \mathbf{B}\) we have \(\delta(\mathbf{A}) \preceq \mathbf{B}\).

    Similarly we have \(\gamma(\mathbf{A}) \preceq \mathbf{B}\) for all \(\mathbf{A} \in \triangledown\) and \(\mathbf{B} \in \blacktriangledown\) with \(\mathbf{A} \preceq \mathbf{B}\).

In other words \(\delta\) and \(\gamma\) are lower adjoints to the corresponding inclusions in the sense of monotone Galois connections. Now we will first describe a weighting on \(\triangledown\) and then we will harness these two maps to describe two weightings on \(\mathcal{D}\).

  • Definition. We set \(\epsilon \colon \triangledown \rightarrow [0, \infty], (a, b; c, d) \mapsto \frac{1}{2} (b + d)\).

We note that \(\epsilon\) is monotone and additive. Moreover the restriction \(\epsilon |_{\blacktriangledown}\) is an isomorphism of monoidal posets. The two different weightings on \(\mathcal{D}\) are now \(\epsilon \circ \gamma \circ \delta\) and \(\epsilon \circ \delta\). Next we provide explicit formulas for these two weightings.

  • Lemma. For all \((a, b; c, d) \in \mathcal{D}\) we have \[ (\epsilon \circ \gamma \circ \delta)((a, b; c, d)) = \max \{-a, b, -c, d\} \] and \[ (\epsilon \circ \delta)((a, b; c, d)) = \frac{1}{2} (\max \{-c, b\} + \max \{-a, d\}) . \]