2004/08/12 by Joel Friedman, Jean-Pierre Tillich, Friedman, Joel +1 · 1 voice
Computer Science · Mathematics · #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.cs/0408028
63 pages, LaTeX
arxiv created 2004/08/12 · arxiv updated 2009/12/01
The purpose of this paper is to develop a "calculus" on graphs that allows graph theory to have new connections to analysis. For example, our framework gives rise to many new partial differential equations on graphs, most notably a new (Laplacian based) wave equation; this wave equation gives rise to a partial improvement on the Chung-Faber-Manteuffel diameter/eigenvalue bound in graph theory, and the Chung-Grigoryan-Yau and (in a certain case) Bobkov-Ledoux distance/eigenvalue bounds in analysis. Our framework also allows most techniques for the non-linear p-Laplacian in analysis to be easily carried over to graph theory.