KAIST Discrete Math Seminar

Combinatorial Laplacians provide important enumeration methods in topological combinatorics. For a finite chain complex , combinatorial Laplacians on are defined by

We will review applications of in computing the tree numbers for graphs and in solving discrete Laplace equations for networks. In general, the boundary operators are used to define high-dimensional trees as a generalization of spanning trees for graphs. We will demonstrate an intriguing relation between high-dimensional tree numbers and for acyclic complexes, based on combinatorial Hodge theory. As an application, a formula for the top-dimensional tree-number of matroid complexes will be derived. If time permits, an important role of combinatorial Laplacians in topological data analysis (TDA) will be briefly discussed.

In 1989, Stephenson and Zelen derived an elegant formula for the information I_ab contained in all possible paths between two nodes a and b in a network, which is described as follows. Given a finite weighted graph G and its Laplacian matrix L, the combinatorial Green’s function , of G is the inverse of L+J, where J is the all 1’s matrix. Then, it was shown that I_ab=(g_aa+g_bb-2g_ab)^-1, where g_ij is the (i,j)-th entry of . In this talk, we prove an intriguing combinatorial formula for I_ab:

where is the complexity, or tree-number, of G, and G_a*b is obtained from G by identifying two vertices a and b. We will discuss several implications of this new formula, including the equivalence of I_ab and the effective conductance between two nodes in electrical networks.