KAIST Discrete Math Seminar

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.

One of the most fundamental properties of a connected graph is the existence of a spanning tree. Also the number τ(G) of spanning trees is an important graph invariant. It plays a crucial role in Kirchhoff’s classical theory of electrical networks, for example in computing driving point resistances. More recently, τ(G) is one of the values of the Tutte polynomial which now plays a central role in statistical mechanics. So are a(G), the number of acyclic orientations, and c(G), the number of orientations in which every edge is in a directed cycle. As a first step towards convexity properties of the Tutte polynomial, Merino and Welsh conjectured that

for every loopless and bridgeless multigraph G. We shall here prove that τ(G) ≤ c(G) for all loopless and bridgeless multigraphs with n vertices and at least 4n edges and that τ(G) ≤ a(G) for all loopless multigraphs with n vertices and at most 16n/15 edges. We also verify the conjecture for cubic graphs (which are in between these two bounds).

A rendezvous number for a metric space M is a number a such that, for every finite subset Q of M, there is an element p in M, such that the average distance from p to the elements in Q is a.

O. Gross showed in 1964 that every compact connected metric space has precisely one rendezvous number. This result is a consequence of von Neumann’s min-max theorem in game theory.

In an article in the American Math. Monthly 93(1986) 260-275, J. Cleary and A. A. Morris asked if a (more) elementary proof of Gross’ result exists.

In this talk I shall formulate a min-max result for real matrices which immediately implies these results of Gross and von Neumann.

The proof is easy and involves only mathematical induction.

We discuss how to efficiently compute shortest and approximate shortest paths in graphs, thereby focusing on shortest path query processing. The algorithm computing (approximate) shortest path queries is allowed to access a pre-computed data structure (often called distance oracle) in order to improve the query time. Several questions regarding such data structures are of particular interest: How can they be computed efficiently? What amount of storage is necessary? How much improvement of the query time is possible? How good is the approximation quality of the query result? What are the tradeoffs between pre-computation time, storage, query time, and approximation quality?

For general dense graphs, the tradeoff between the storage requirement and the approximation quality is known up to constant factors. We discuss both the lower and the upper bound (by Thorup and Zwick). For specific types of sparse graphs, however, the exact tradeoff is not known; the general tradeoff can be improved: there are special data structures of a certain size that enable query algorithms to return distances of higher quality than what the general tradeoff would predict. We outline the state of the art of distance oracles for planar graphs and other classes of sparse graphs. We then prove that this improvement for some classes of sparse graphs cannot be extended to all sparse graphs: there is a three-way relationship between space, query time, and approximation quality for general sparse graphs. If time permits, we also cover space- and time-efficient data structures for certain complex networks with power-law degree sequences.

Joint work with Wei Chen, Shinichi Honiden, Michael Houle, Ken-ichi Kawarabayashi, Shang-Hua Teng, Elad Verbin, Yajun Wang, Martin Wolff, and Wei Yu.

Polytope numbers for a polytope are a sequence of nonnegative integers which are defined by the facial information of a polytope. This is a higher dimensional generalization of polygonal number. It is well known that every polygon can be decomposed into triangles. A higher dimensional analogue of this fact states that every polytope has a triangulation, namely, it can be decomposed into simplices. Thus it may be possible to represent polytope numbers as sums of simplex numbers, which gives another way of calculating polytope numbers.

In this talk, we define polytope numbers and calculate polytope numbers for several polytopes, and we introduce decomposition theorem, which is a way of representing polytope numbers as sums of simplex numbers. We also suggest further problems in the study of polytope numbers and possible approaches to these problems.

Joint work with Prof. Hyun Kwang Kim, POSTECH, Korea.