Graph Homomorphisms, Stochastic Networks, Discrete Mass Transport

这项建议有三个组成部分。第一个描述了最近与Kavita Ramanan（卡内基梅隆大学）和David Galvin（微软博士后）在Gibbs测度上的合作，并将其应用于随机网络。来自这些和相关网络的动机提出了关于相独特性和共存区域的新的和定性不同的问题，这些问题正在研究中。第二部分描述了sergey Bobkov（明尼苏达大学）正在进行的关于对数Sobolev不等式的改进版本和有限Markov链收敛平稳的应用的研究。这项工作延续到最近与研究生Marcus Sammer和同事Wilfrid Gangboon的离散运输问题的研究活动中。特别是，最后一个组成部分是发展离散微积分来研究质量传输、里奇曲率的各个方面，并理解各种相关不等式之间的联系——传输不等式、塔拉格兰不等式、熵不等式和对数索博列夫型不等式。在连续的情况下（比如在R^n或黎曼流形上），上述第二和第三个主题之间有密切的联系；然而，在有限度量空间的离散集中，这些还没有得到满足。由于应用的丰富性，我们发现这种类似理论的发展是值得的和富有成效的。该提案旨在探索电信（和其他数据）网络在最近提出的大型网格结构上的多播和单播模型下的行为和性能。PI和合作者的初步调查表明，单播调用的引入给系统带来了一定的对称性破坏，并使系统在由于可能施加在大（网格状）区域边界的影响而屈服于调用阻塞之前承载更高的多播调用负载。相关问题涉及理解信息的传播（遗传或其他）和疾病在树状和网格状环境中的传播。本提案中概述的这些和其他研究目标是分析学、组合学、概率论、信息论、统计物理学和计算理论的研究人员感兴趣的。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.