Sparse random combinatorial structures
稀疏随机组合结构
基本信息
- 批准号:517012267
- 负责人:
- 金额:--
- 依托单位:
- 依托单位国家:德国
- 项目类别:Research Grants
- 财政年份:
- 资助国家:德国
- 起止时间:
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
Wider research contextProbabilistic combinatorics is a mathematical discipline concerned with the study of random combinatorial structures such as random graphs, networks or matrices. Such random structures play a pivotal role in randomised constructions in computer science and other areas of application. Over the past two decades probabilistic combinatorics has received impulses from statistical physics, where a heuristic method called the "cavity method" has been developed to put forward intriguing conjectures on numerous long-standing problems. The aim of this project is to provide a rigorous mathematical basis for the techniques upon which the cavity method is based.Research questions / objectivesThe focus will be on sparse random combinatorial structures. Specifically, the project concentrates on three prominent, closely related challenges:1. random combinatorial matrices and random equations over discrete algebraic structures2. weighted matchings on sparse random graphs3. Hamilton cycles in sparse random graphs.The objective in each topic will be to seize upon statistical physics intuition to develop new mathematical techniques, and to rigorously investigate the conjectures put forward in the physics community.Specifically, we aim to derive tight necessary and sufficient conditions for a sparse random combinatorial matrix to be of full rank. Additionally, we are going to investigate random systems of equations over finite groups.The second topic will be the weighted matching problem on sparse random graphs. Physics Nobel laureate Giorgio Parisi and co-authors recently posited remarkably preicse conjectures as to the expected minimum weight of a perfect matching on a random graph that we aim to investigate rigorously.Concerning the third topic, we are going to utilise physics intuition to tackle the long-standing Hamilton cycle problem on sparse but irregular random graphs.Approach / methodsIn this project we aim to harness the intuition developed in the statistical physics community to develop new methods for the study of sparse srandom combinatorial structures. In particular, we aim to devise a rigorous mathematical basis for the heuristic methods used in the physics community, such as the Belief Propagation message passing algorithm.Level of originality / innovationBy comparison to prior work, the three topics that we investigate lack of crucial symmetry properties. For instance, inherent symmetry properties make it easy to find and count Hamilton cycles in random regular graphs. But in irregular random graphs, the existence of Hamilton cycles remains wide open.Primary researchers involvedThis is a joint FWF-DFG project conducted by the combinatorics group at TU Graz (Prof. Mihyun Kang) and the efficient algorithms and complexity group at TU Dortmund (Prof. Amin Coja-Oghlan).
更广泛的研究背景概率组合学是一门研究随机组合结构的数学学科,如随机图、网络或矩阵。这种随机结构在计算机科学和其他应用领域的随机结构中起着关键作用。在过去的二十年里,概率组合学受到了统计物理学的推动,在统计物理学中,一种叫做“空腔法”的启发式方法已经发展起来,对许多长期存在的问题提出了有趣的猜想。该项目的目的是为空腔法所依据的技术提供严格的数学基础。研究问题/目标研究重点是稀疏随机组合结构。具体而言,该项目集中在三个突出的,密切相关的挑战:1。离散代数结构上的随机组合矩阵和随机方程。稀疏随机图的加权匹配[j]。稀疏随机图中的Hamilton环。每个主题的目标都是抓住统计物理的直觉来发展新的数学技术,并严格调查物理学界提出的猜想。具体地说,我们的目的是得到一个稀疏随机组合矩阵是满秩的严格的充要条件。此外,我们将研究有限群上的随机方程组。第二个主题是稀疏随机图上的加权匹配问题。诺贝尔物理学奖得主乔治·帕里西(Giorgio Parisi)和他的合作者最近提出了一个非常精确的猜想,即我们旨在严格研究的随机图上完美匹配的预期最小权重。关于第三个主题,我们将利用物理直觉来解决稀疏但不规则随机图上长期存在的汉密尔顿循环问题。在这个项目中,我们的目标是利用统计物理学界发展起来的直觉来开发研究稀疏随机组合结构的新方法。特别是,我们的目标是为物理社区中使用的启发式方法设计一个严格的数学基础,例如信念传播消息传递算法。原创性/创新水平与之前的工作相比,我们研究的三个主题缺乏关键的对称性。例如,固有的对称性使得在随机正则图中查找和计数汉密尔顿圈变得容易。但在不规则随机图中,哈密顿环的存在性仍有待进一步研究。这是由格拉茨工业大学组合学小组(Mihyun Kang教授)和多特蒙德工业大学高效算法和复杂性小组(Amin Coja-Oghlan教授)共同开展的FWF-DFG项目。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Professor Dr. Amin Coja-Oghlan其他文献
Professor Dr. Amin Coja-Oghlan的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Professor Dr. Amin Coja-Oghlan', 18)}}的其他基金
Random graphs: cores, colourings and contagion
随机图:核心、着色和传染
- 批准号:
397269007 - 财政年份:2018
- 资助金额:
-- - 项目类别:
Research Grants
Message passing algorithms, information-theoretic thresholds and computational barriers
消息传递算法、信息论阈值和计算障碍
- 批准号:
393689644 - 财政年份:
- 资助金额:
-- - 项目类别:
Research Grants
Reconstruction and Learning in Complex Networks
复杂网络中的重构和学习
- 批准号:
438574637 - 财政年份:
- 资助金额:
-- - 项目类别:
Research Units
相似国自然基金
大Peclect数多粒径分布球形多孔介质内流动、传质和反应特性的研究
- 批准号:21276256
- 批准年份:2012
- 资助金额:80.0 万元
- 项目类别:面上项目
基于Riemann-Hilbert方法的相关问题研究
- 批准号:11026205
- 批准年份:2010
- 资助金额:3.0 万元
- 项目类别:数学天元基金项目
不经意传输协议中的若干问题研究
- 批准号:60873041
- 批准年份:2008
- 资助金额:30.0 万元
- 项目类别:面上项目
面向Web信息检索的随机P2P拓扑模型及语义网重构技术研究
- 批准号:60573142
- 批准年份:2005
- 资助金额:20.0 万元
- 项目类别:面上项目
利用逆转录病毒siRNA随机文库在Hela细胞中批量获得TRAIL凋亡通路相关功能基因的研究
- 批准号:30400080
- 批准年份:2004
- 资助金额:8.0 万元
- 项目类别:青年科学基金项目
相似海外基金
Pharmacogenomic effects of scavenger B1 in cardiovascular disease prevention
清除剂 B1 在心血管疾病预防中的药物基因组学效应
- 批准号:
10541892 - 财政年份:2022
- 资助金额:
-- - 项目类别:
Pharmacogenomic effects of scavenger B1 in cardiovascular disease prevention
清除剂 B1 在心血管疾病预防中的药物基因组学效应
- 批准号:
10347622 - 财政年份:2022
- 资助金额:
-- - 项目类别:
Discovery of autoimmune antigens from non-coding sequences
从非编码序列发现自身免疫抗原
- 批准号:
10286063 - 财政年份:2021
- 资助金额:
-- - 项目类别:
Discovery of autoimmune antigens from non-coding sequences
从非编码序列发现自身免疫抗原
- 批准号:
10450060 - 财政年份:2021
- 资助金额:
-- - 项目类别:
Cell-specific nanocarrier with endocytic and endosomolytic activities for therapeutic genome editing
具有内吞和内体溶解活性的细胞特异性纳米载体,用于治疗性基因组编辑
- 批准号:
10227681 - 财政年份:2019
- 资助金额:
-- - 项目类别:
Cell-specific nanocarrier with endocytic and endosomolytic activities for therapeutic genome editing
具有内吞和内体溶解活性的细胞特异性纳米载体,用于治疗性基因组编辑
- 批准号:
9810930 - 财政年份:2019
- 资助金额:
-- - 项目类别:
Cell-specific nanocarrier with endocytic and endosomolytic activities for therapeutic genome editing
具有内吞和内体溶解活性的细胞特异性纳米载体,用于治疗性基因组编辑
- 批准号:
10001068 - 财政年份:2019
- 资助金额:
-- - 项目类别:
Combinatorial Optimization, Spin Models, and the Geometry of Sparse Random Graphs
组合优化、自旋模型和稀疏随机图的几何形状
- 批准号:
1613091 - 财政年份:2016
- 资助金额:
-- - 项目类别:
Continuing Grant