Phase transitions in random graphs and random graph processes

随机图和随机图过程中的相变

• 批准号: 191445217
• 负责人: Professorin Dr. Mihyun Kang
• 金额: --
• 依托单位: Institut für Diskrete Mathematik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2011
• 资助国家: 德国
• 起止时间: 2010-12-31 至 2014-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/191445217?language=en
• 关键词: Phase; transitions; random; graphs; graph

Combinatorial structures have been extensively studied during the last few decades and have become one of the central themes of contemporary mathematics. The study of random graphs in particular has brought together different fields such as discrete mathematics, probability theory, theoretical computer science and statistical physics. The objectives of this project are to study the phase transitions in random graphs and random graph processes with constraints such as degree distribution, forbidden substructures, genus. The phase transition is a phenomenon observed in many fundamental problems from statistical physics, mathematics and theoretical computer science, including Potts models, graph colourings and satisfiability problem. The phase transition observed in the plethora of different random graph models refers to a phenomenon that there is a critical value of edge density such that adding a small number of edges around the critical value results in a dramatic change in the size of the largest components. It is our aim to further develop and apply new analytic approaches combined with counting and probabilistic methods, e.g. singularity analysis, differential equations method, to the study of the phase transitions in random graphs and random graph processes.

组合结构在过去的几十年中得到了广泛的研究，并已成为当代数学的中心主题之一。特别是随机图的研究汇集了不同的领域，如离散数学，概率论，理论计算机科学和统计物理。本项目的目标是研究随机图和随机图过程在度分布、禁止子结构、亏格等约束条件下的相变。相变是统计物理、数学和理论计算机科学中许多基本问题中观察到的现象，包括Potts模型、图着色和可满足性问题。在大量不同的随机图模型中观察到的相变是指存在边缘密度的临界值的现象，使得在临界值周围添加少量的边缘导致最大组件的大小的急剧变化。我们的目标是进一步发展和应用新的分析方法，结合计数和概率方法，如奇异性分析，微分方程方法，随机图和随机图过程中的相变的研究。

项目成果

On the connectivity of random graphs from addable classes

关于可添加类的随机图的连通性

• DOI: 10.1016/j.jctb.2012.12.001
• 发表时间: 2013
• 期刊: J. Comb. Theory, Ser. B
• 作者: M. Kang;K. Panagiotou
• 通讯作者: K. Panagiotou

On the connectivity threshold of Achlioptas processes

关于 Achlioptas 进程的连接阈值

• DOI: 10.4310/joc.2014.v5.n3.a2
• 发表时间: 2014
• 期刊: The Journal of Combinatorics
• 作者: M. Kang;K. Panagiotou
• 通讯作者: K. Panagiotou

Local Limit Theorems for the Giant Component of Random Hypergraphs†

随机超图巨分量的局部极限定理

• DOI: 10.1017/s0963548314000017
• 发表时间: 2014
• 期刊: Combinatorics, Probability and Computing
• 作者: M. Behrisch;A. Coja-Oghlan;M. Kang
• 通讯作者: M. Kang

The Asymptotic Number of Connected d-Uniform Hypergraphs†

连通d-一致超图的渐近数

• DOI: 10.1017/s0963548314000029
• 发表时间: 2014
• 期刊: Combinatorics, Probability and Computing
• 作者: M. Behrisch;A. Coja-Oghlan;M. Kang
• 通讯作者: M. Kang