Graph Homomorphisms, Stochastic Networks, Discrete Mass Transport

图同态、随机​​网络、离散质量传输

• 批准号: 0401239
• 负责人: Prasad Tetali
• 金额: $ 14.84万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-06-01 至 2008-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0401239&HistoricalAwards=false
• 关键词: Graph; Homomorphisms; Stochastic; Networks; Discrete

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.

这项建议有三个组成部分。第一个描述了最近与Kavita Ramanan（麦基-梅隆大学）和大卫高尔文（博士后，微软）在吉布斯测度上的合作，以及对随机网络的应用。动机从这些和相关的网络提出了新的和定性不同的问题，有关地区的相位唯一性和共存，这是正在调查。 第二部分描述了正在进行的研究与谢尔盖Bobkov（明尼苏达大学）关于对数Sobolev不等式的修改版本和有限马尔可夫链收敛到平稳性的应用。这项工作被带到最近的研究活动与研究生Marcus Sammer和同事Wilfrid Gangboon离散运输问题。特别是，最后一部分是发展离散演算研究方面的质量运输，里奇曲率，并了解各种相关的不等式之间的联系-运输不等式，塔拉格兰德不等式，熵不等式和Sobolev型不等式。在连续设置中（如在R^n上或在黎曼流形上），上述第二和第三主题之间有着密切的联系;然而，在有限度量测度空间的离散情形下，这些问题还没有得到满意的解决。由于应用的丰富性，我们发现这种类似理论的发展是有价值和富有成效的。该建议旨在探讨电信的行为和绩效（和其他数据）网络在最近建议的多播和单播模型下的大网格状结构。PI和合作者的初步调查表明，单播呼叫的引入给系统带来了一定的对称性破缺，并让系统在系统由于可能施加在大的边界上的影响而屈服于呼叫阻塞之前承载更高的多播呼叫负载。相关的问题涉及理解信息的传播（遗传学或其他）和疾病在树状和网格状环境中的传播。本提案中概述的这些和其他研究目标对分析，组合学，概率论、信息论、统计物理学和计算理论。PI的主要动机之一来自组合数学和离散概率的计算和应用问题。该提案的一个主要主题也是深入探讨信息理论技术在离散概率和计算中的作用。PI完全希望他与这些不同研究主题的合著者的广泛合作有助于数学思想，建模和技术的交叉施肥，同时促进研究的教育成分。