Discrete-to-continuous extensions: Lovász extension and Morse theory (Q6559433)

Amongst others, in this paper the authors present an equivalence between Forman's discrete Morse theory on a simplicial complex and the continuous (metric, topological or PL) Morse theory on the associated order complex. The main tool to achieve it is the Lovász extension, a basic tool in discrete mathematics especially helpful in combinatorial optimization problem [\textit{F. Bach}, Found. Trends Mach. Learn. 6, No. 2--3, 145--373 (2013; Zbl 1280.68001); \textit{L. Lovász}, in: Mathematical programming. The state of the art. Berlin, Heidelberg: Springer. 235--257 (1983; Zbl 0566.90060)].\N\NThe connection between the geometric data of a discrete Morse function and the geometric information of its Lovász extension is established in Theorems 3.7 and 3.9. In particular, Theorem 3.7 shows that for any injective discrete Morse function \(f\colon K\to \mathbb{R}\) on a simplicial complex \(K\), the critical cells of \(f\) bijectively correspond to critical points (with the same index) of its Lovász extension (suitably restricted to the geometric realization of the order complex of \(K\)). The full equivalence between the discrete and continuous Morse theories is then formalized in Theorem 3.9.\N\NUsing the described approach, and in particular PL-Morse theory in conjunction with the Lovász extension, the authors provide in the paper a new definition of a \textit{discrete} Lusternik-Schnirelmann category, together with a general definition of critical points of a function on the edge-set of a hypergraph; finally, they establish a discrete Morse theory on hypergraphs, and provide some examples. A dictionary between the different analogs of Morse theories is provided in the paper, which is complemented with some open questions.