We will present recent progress in spectral theory of the 1-Laplacian on graphs as well as its applications in graph cut.The localization property of the eigenvectors is explored. The Courant nodal domain theorem for graphs is extended to graph 1-Laplacian for strong nodal domains, but for weak nodal domains it is false. The notion of algebraic multiplicity is introduced in order to provide a more precise estimate of the number of independent eigenvectors. The first eigenvalue of the signless 1-Laplacian precisely characterizes the bipartiteness of a graph and naturally connects to the maxcut problem. A set-pair version of the Lov ́asz extension, which aims at the equivalence between discrete combination optimization and continuous function optimization, is established to recover the connection. A local analysis of the associated functional yields an inverse power method and then produces an efficient implementation of the recursive spectral cut algorithm for the maxcut problem.

海报