Graph Homomorphisms, Stochastic Networks, Discrete Mass Transport

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This proposal has three components. The first describes recent collaboration with Kavita Ramanan (Carnegie-Mellon University) and David Galvin (postdoc, Microsoft) on Gibbs measures, with applications to stochastic networks. Motivation from these and related networks raises new and qualitatively different questions concerning regions of phase uniqueness and coexistence, which are being investigated. The second component describes ongoing research with Sergey Bobkov (University of Minnesota) on modified versions of logarithmic Sobolev inequalities and applications to convergence to stationarity of finite Markov chains. This work is carried over to more recent research activity with graduate student, Marcus Sammer and colleague, Wilfrid Gangbo on discrete transportation problems. In particular, the final component is on developing discrete calculus to study aspects of mass transport, Ricci curvature, and understanding connections between various relavant inequalities -- the transportation inequality, Talagrand's inequality, the entropy inequality and logarithmic Sobolev type inequalities. In continuous settings (such as on R^n or on Riemannian manifolds), there are intimate connections between the above-mentioned 2nd and 3rd topics; however these are yet to be established to satisfaction in the discrete settings of finite metric measure spaces. Due to the richness in applications, we find development of such an analogous theory worthwhile and fruitful. The proposal intends to explore the behavior and performance of telecommunication (and other data) networks under recently-suggested models of multicasting and unicasting on large grid-like structures. Preliminary investigations of the PI and collaborators demonstrate that the introduction of unicast calls brings in a certain symmetry breaking into the system, and lets the system carry a higher load of multicast calls before the system succumbs to call-blocking due to the influence of what might be imposed on the boundary of the large (grid-like) region. Related questions address understanding the spread of information (genetic or otherwise) and the spread of disease in tree-like and grid-like environment. These and other research objectives outlined in this proposal are of interest to researchers in analysis, combinatorics, probability, information theory, statistical physics and the theory of computing. One of the main motivations for the PI comes from computational and applied problems of combinatorics and discrete probability. An overarching theme of the proposal is also to explore in depth the role of information theoretic techniques in discrete probability and computing. The PI fully hopes his extended collaboration with his coauthors in these disparate research topics contributes to the cross-fertilization of mathematical ideas, modeling, and techniques, while promoting the educational component of research.