## 2 Bypassing Matchings
To see why \(\phi\) achieves the infimum over all bijections between \(X\) and \(Y\), note that any other bijection \(\psi\) produces a death time for a point in \(Y\) matched to the diagonal that is at least as large as \(y_{N+1}/2\). Therefore \(\max_{x\in X}||x-\phi(x)||_{\infty}\leq\max_{x\in X}||x-\psi(x)||_{\infty}\). Lemma 2: _Let \(X\), \(Y\), \(Z\), \(N\), \(l\) and \(\phi\) be defined as above, and let \(\zeta\) be the second largest entry of \(Z\)._  
1. _If_ \(\max(Z)\leq\max(x_{l},y_{l})/2\)_, then_ \(d_{B}(X,Y)=\max(Z)\)_._
2. _If_ \(\zeta<\max(x_{l},y_{l})/2<\max(Z)\)_, then_ \(d_{B}(X,Y)=\max(x_{l},y_{l})/2\)_._
3. _If_ \(\zeta\geq\max(x_{l},y_{l})/2\) _and_ \(m\geq l\) _for every_ \(m\) _such that_ \(z_{m}\geq\max(x_{l},y_{l})/2\)_, then_ \(d_{B}(X,Y)=\max(x_{l},y_{l})/2\)_._
4. _If_ \(\zeta\geq\max(x_{l},y_{l})/2\) _and there exists_ \(m<l\) _such that_ \(z_{m}\geq\max(x_{l},y_{l})/2\)_, then there exists a bijection_ \(\tau\) _between_ \(X\) _and_ \(Y\) _such that one of the three preceding cases holds and where_ \[\max||x-\tau(x)||_{\infty}<\max||x-\phi(x)||_{\infty}.\]  
Proof. : 1. It follows from our remark immediately after (1) that \[\max||x-\phi(x)||_{\infty}=\max(Z)\leq\max(x_{l},y_{l})/2=\max||x-\phi^{\prime }(x)||_{\infty}\] where \(\phi^{\prime}\) is the bijection that matches both \(x_{l}\) and \(y_{l}\) to the diagonal, and coincides with \(\phi\) otherwise. Figure 2c illustrates this comparison between the two matchings. For any other bijection \(\psi\), if \(x^{\prime}\in X\) such that \(|x^{\prime}-\psi(x^{\prime})|\) is maximum among all non-trivial matchings, either \(\max(Z)\leq|x^{\prime}-\psi(x^{\prime})|\), or \(\max(x_{l},y_{l})\leq\max(x^{\prime},\psi(x^{\prime}))\). If \(N<length(Y)\), then a similar argument as that in Lemma 1 holds. The conclusion now follows. 2. In this case, the same bijection \(\phi^{\prime}\) in the previous case yields \[\max||x-\phi^{\prime}(x)||_{\infty}=\max(x_{l},y_{l})/2<\max(Z)=\max||x-\phi( x)||_{\infty}.\] The same argument in the previous case holds for any other bijection \(\psi\). Hence, the inequality above implies the conclusion. 3. For the bijection \(\phi^{\prime\prime}\) that sends \(x_{m}\) and \(y_{m}\) to the diagonal for all such \(m\), and coincides with \(\phi\) otherwise (see Figure 2d), we have that \[\max||x-\phi^{\prime\prime}(x)||_{\infty}=\max(x_{l},y_{l})/2<\max(Z)=\max||x- \phi(x)||_{\infty}.\] Again, since the same argument in the first case holds for any other bijection \(\psi\), the previous inequality implies the conclusion. Define the bijection \(\tau\) that sends \(x_{j}\) and \(y_{j}\) to the diagonal for all \(j\geq l\), and coincides with \(\phi\) otherwise. Then we have that \[\max||x-\tau(x)||_{\infty}<\max(Z)=\max||x-\phi(x)||_{\infty},\] Moreover, note that \(\max||x-\tau(x)||_{\infty}\) depends only on \(||x-\tau(x)||_{\infty}\) for non-trivially matched \(x\) and \(\tau(x)\). Therefore, we can consider only the subsets \(X^{\prime}\) and \(Y^{\prime}\) respectively of \(X\) and \(Y\) whose points are non-trivially matched by \(\tau\). In this case, \(length(X^{\prime})=length(Y^{\prime})\) and one of the three previous cases above holds. The proof is now complete. The two Lemmas above provide the theoretical basis for the bypass approach of the Lumawig algorithm. Together, they take advantage of the specific form of dimension zero persistence diagrams being considered, and the methodical approach to optimize norms induced by a specific matching. The complete pseudo code is given in Algorithm 1 below. ```
1:Input: Two dimension zero persistence diagrams \(X\) and \(Y\) such that \(X\
eq Y\) and where \(X\) has fewer than or as many points as \(Y\). 2:Output: The bottleneck distance between \(X\) and \(Y\).