This talk will consist in three parts. In the first part we will describe algorithms for the computation of lexicographic minimal chains in an abstract setting. Given a simplicial complex $K$, we consider the problem of finding a simplicial $d$-chain minimal in a given homology class.

This is sometimes referred to as the {\em Optimal Homologous Chain Problem} (OHCP).

We consider here simplicial chains with coefficients in $\Z/2 \Z$ and the particular situation where, given a total order on $d$-simplices$\sigma_1<\ldots<\sigma_n$, the weight of simplex $i$ is $2^i$. In this case,the comparison of chains is a {\em lexicographic ordering}.

Similarly, we consider the problem of {\em finding a minimal chain for a prescribed boundary}.

We show that, for both problems, the same matrix reduction algorithm used for the computation of homological persistence diagrams, applied to the filtration induced by the order on $d$-simplices, allows a $\BigO(n^3)$ worst case time complexity algorithm.

In the particular case where $K$ is a $(d+1)$-pseudo-manifold,there is a $\BigO(n \log n)$ algorithm which can be seen, by duality, as a {\em lexicographic minimum cut} in the dual graph of $K$.

The second part will show how a carefully chosen total order on simplices allows to retrieve regular triangulations in euclidean spaces, as well as the triangulation of positive reach $2$-manifolds as the support of lexicographic minimal chains.

We see that each part is motivated by the other.

In a last part we will consider two open questions suggested by the preceding results.

Results from a joined work with David Cohen-Steiner and Julien Vuillamy.

Thanks for ongoing works and discussions with:

Dominique Attali, Jean-Daniel Boissonnat, Mathijs Wintraecken