Graph Homomorphisms, Stochastic Networks, Discrete Mass Transport

这项提议有三个组成部分。第一个描述了最近与卡内基-梅隆大学的Kavita Ramanan和微软博士后David Galvin在Gibbs度量方面的合作，以及对随机网络的应用。来自这些网络和相关网络的运动提出了关于相位唯一性和共存区的新的和质的不同的问题，正在进行研究。第二部分描述了与明尼苏达大学的谢尔盖·博布科夫(Sergey Bobkov)正在进行的关于对数Sobolev不等式的修改版本以及应用于收敛到有限马尔可夫链的平稳性的研究。这项工作是与研究生Marcus Sammer及其同事WilFrid Gangboon最近的研究活动继续进行的。特别是，最后一部分是发展离散微积分，研究质量传输、Ricci曲率的各个方面，并了解各种相关不等式之间的联系--运输不等式、TALAGRAND不等式、熵不等式和对数Sobolev型不等式。在连续的环境中(如在R^n或黎曼流形上)，上述第二和第三主题之间存在着密切的联系；然而，在有限度量空间的离散集合中，这些联系还没有得到令人满意的建立。由于应用的丰富性，我们发现这种类似理论的发展是值得的和富有成效的。PI和合作者的初步调查表明，单播呼叫的引入带来了某种对称性的破坏，并使系统在系统由于可能施加在大(网格)区域的边界上的影响而屈服于呼叫阻塞之前承载更高的组播呼叫负载。相关问题涉及理解信息的传播(遗传或非遗传)和疾病在树状和网格状环境中的传播。这些和本方案中概述的其他研究目标是分析、组合学、概率、信息论、统计物理和计算理论的研究人员感兴趣的。PI的主要动机之一来自于组合学和离散概率的计算和应用问题。该提案的一个主要主题也是深入探讨信息理论技术在离散概率和计算中的作用。国际和平研究所完全希望他与合著者在这些不同的研究主题上的广泛合作有助于促进数学思想、建模和技术的交叉培养，同时促进研究的教育部分。

This proposal has three components. The firstdescribes recent collaboration with Kavita Ramanan (Carnegie-Mellon University) and David Galvin (postdoc, Microsoft) on Gibbs measures, with applications to stochastic networks. Motivationfrom these and related networks raises new and qualitatively differentquestions concerning regions of phase uniqueness and coexistence, whichare being investigated. The second component describes ongoing research withSergey 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 activitywith graduate student, Marcus Sammer and colleague, Wilfrid Gangboon discrete transportation problems.In particular, the final component is on developing discrete calculusto study aspects of mass transport, Ricci curvature, and understanding connections between variousrelavant inequalities -- the transportation inequality, Talagrand's inequality, the entropy inequality and logarithmicSobolev type inequalities. In continuous settings(such as on R^n or on Riemannian manifolds), there are intimateconnections between the above-mentioned 2nd and 3rd topics; howeverthese are yet to be established to satisfaction in the discretesettings of finite metric measure spaces.Due to the richness in applications, we find developmentof such an analogous theory worthwhile and fruitful.The proposal intends to explore the behavior and performanceof telecommunication (and other data) networks under recently-suggested models of multicasting and unicastingon large grid-like structures. Preliminary investigations of the PI and collaborators demonstrate that the introduction of unicast calls bringsin a certain symmetry breaking into the system, andlets the system carry a higher load of multicast callsbefore the system succumbs to call-blocking due to the influenceof what might be imposed on the boundary of the large (grid-like) region.Related questions address understanding the spread of information (geneticor 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 appliedproblems of combinatorics and discrete probability. An overarchingtheme of the proposal is also to explore in depththe role of information theoretic techniques in discrete probabilityand computing. The PI fully hopes his extended collaboration with his coauthors in these disparate research topics contributes to thecross-fertilization of mathematical ideas, modeling, and techniques,while promoting the educational component of research.