Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Laplacian of a graph is a useful tool in many kinds of graph decomposition problems. Since inspection of the eigenvector corresponding to the second smallest eigenvalue (the Fiedler vector) yields information about sparse cuts, it's often used to partition graphs or even cluster data. Of course the Laplacian on a graph can be viewed as a discrete analog of the Laplace-Beltrami operator on a general Riemannian manifold, and indeed much of the intuition for graph partitioning methods comes from this connection.

I recently heard a talk (based on this paper) (and found this paper) on the use of a Hermitian analog of the Laplacian to do graph partitioning. While the authors demonstrate the value of the method experimentally, for various graph partitioning problems, I was more interested in the underlying theory.

Is there any way to relate Hermitian structures on graphs to equivalent concepts on a manifold ? Maybe Hermitian manifolds, or Kahler manifolds ? Specifically, do the notions of sparse cuts (on graphs) and diffusion via the heat equation (on Riemannian manifolds) have parallels in the complex case ?

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.