Problems in Extremal Combinatorics
极值组合问题
基本信息
- 批准号:0401147
- 负责人:
- 金额:$ 10.5万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2004
- 资助国家:美国
- 起止时间:2004-08-01 至 2007-07-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
This project has two parts: an investigation of the independence numbers of the powers of fixed graphsand a study of the emergence of a giant component in `guided' versions of the classical random graph. The first part is motivated by the many open questions regarding the Shannon capacities of graphs and focuses on the possible behaviors of the sequence given by the independence numbers of the powers of a fixed graph. The odd cycles and their complements are particularlyimportant examples and play a central role in this partof the project. While a wide range of techniques -- including algebraic methods -- may be useful here, recent progress has come through the interplay of novel constructions for, and structural conditions imposed onlarge independent sets in these graph powers. In the second part of this project we study the component structure in the random graph processes known as Achlioptas processes, processes in which a pair of random edges is presented in each round and an on-linealgorithm chooses between them. Here we are interested in the existence, timing and nature of a phase transition in the size of the largest component. A principle tool here is the differential equations method for establishing concentration in random graph processes.This research is in the area of extremal combinatorics.Questions considered in this field are of the form: `How large (or small) can an object that lies in a particulardiscrete mathematical system and satisfies a certain condition be?' We are often concerned with the behavior of the size of the extremal objects as the size of the underlying system goes to infinity. Interest in such questions grew extensively during the twentieth century. Pioneers of the field, such as Paul Erd\H{o}s, posed many fascinating questions of this form and devised powerful methods for solving them even before the close connections between extremal combinatorics and various other fields (including theoretical computer science, statistical physics and information theory) were discovered. The Shannon capacities of graphs are a classic example of the close interaction between extremal combinatorics and the theory of communication. The Shannon capacity gives a measure of the optimal zero-error performance of a noisy communication channel and is centrally important in information theory. At the same time, it gives rise to natural questions in extremal combinatorics and graph theory. Some of thesequestions are addressed in this research project.
这个项目包括两个部分:一个是关于固定图的幂的独立数的调查,另一个是关于经典随机图的“有向导”版本中出现一个巨型分量的研究。第一部分是由许多关于图的Shannon容量的公开问题引起的,并集中于由固定图的幂的独立数给出的序列的可能行为。奇数周期和它们的补充是特别重要的例子,在项目的这一部分中发挥着核心作用。虽然许多技术--包括代数方法--在这里可能是有用的,但最近的进展是通过这些图的幂中的大的独立集的新颖构造和施加在其上的结构条件的相互作用而来的。在这个项目的第二部分,我们研究了称为Achlioptas过程的随机图过程的分量结构,即在每一轮中呈现一对随机边并在它们之间进行选择的在线算法的过程。在这里,我们感兴趣的是最大分量大小的相变的存在、时间和性质。这里的一个主要工具是在随机图过程中建立集中度的微分方程式方法。这项研究是在极值组合学领域进行的。这一领域考虑的问题是这样的:位于特定离散数学系统中并满足一定条件的对象能有多大(或多小)?随着底层系统的大小变得无限大,我们经常关心极端物体的大小行为。在二十世纪,人们对这类问题的兴趣广泛增长。在极值组合学与其他领域(包括理论计算机科学、统计物理和信息论)之间的密切联系被发现之前,该领域的先驱,如保罗·埃德·S,就提出了许多有趣的问题,并设计了强有力的方法来解决这些问题。图的Shannon容量是极值组合学与传播学之间密切互动的经典例子。香农容量给出了噪声通信信道的最佳零差错性能的度量,并且在信息论中具有重要意义。同时,它也引发了极值组合学和图论中的自然问题。其中一些问题在本研究项目中得到了解决。
项目成果
期刊论文数量(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 }}
Tom Bohman其他文献
Vertex Covers by Edge Disjoint Cliques
- DOI:
10.1007/s004930100017 - 发表时间:
2001-04-01 - 期刊:
- 影响因子:1.000
- 作者:
Tom Bohman;Alan Frieze;Miklós Ruszinkó;Lubos Thoma - 通讯作者:
Lubos Thoma
A critical probability for biclique partition of <em>G</em><sub><em>n</em>,<em>p</em></sub>
- DOI:
10.1016/j.jctb.2023.12.005 - 发表时间:
2024-05-01 - 期刊:
- 影响因子:
- 作者:
Tom Bohman;Jakob Hofstad - 通讯作者:
Jakob Hofstad
How many random edges make a dense graph Hamiltonian ?
有多少条随机边构成稠密图哈密顿量?
- DOI:
- 发表时间:
2001 - 期刊:
- 影响因子:0
- 作者:
Tom Bohman - 通讯作者:
Tom Bohman
Game chromatic index of graphs with given restrictions on degrees
- DOI:
10.1016/j.tcs.2008.05.026 - 发表时间:
2008-11-06 - 期刊:
- 影响因子:
- 作者:
Andrew Beveridge;Tom Bohman;Alan Frieze;Oleg Pikhurko - 通讯作者:
Oleg Pikhurko
Preventing Bullying and Sexual Harassment in Elementary Schools
防止小学欺凌和性骚扰
- DOI:
- 发表时间:
2001 - 期刊:
- 影响因子:0
- 作者:
E. Sanchez;T. Robertson;C. M. Lewis;Barri Rosenbluth;Tom Bohman;D. Casey - 通讯作者:
D. Casey
Tom Bohman的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Tom Bohman', 18)}}的其他基金
Probabilistic and Extremal Combinatorics
概率和极值组合学
- 批准号:
2246907 - 财政年份:2023
- 资助金额:
$ 10.5万 - 项目类别:
Continuing Grant
Conference: 21st International Conference on Random Structures & Algorithms
会议:第21届国际随机结构会议
- 批准号:
2309068 - 财政年份:2023
- 资助金额:
$ 10.5万 - 项目类别:
Standard Grant
17th International Conference on Random Structures and Algorithms
第十七届随机结构与算法国际会议
- 批准号:
1506338 - 财政年份:2015
- 资助金额:
$ 10.5万 - 项目类别:
Standard Grant
Extremal and Probabilistic Combinatorics via Regularity and Graph Limits
通过正则性和图极限的极值和概率组合
- 批准号:
1100215 - 财政年份:2011
- 资助金额:
$ 10.5万 - 项目类别:
Standard Grant
Probabilistic and Extremal Combinatorics
概率和极值组合学
- 批准号:
1001638 - 财政年份:2010
- 资助金额:
$ 10.5万 - 项目类别:
Continuing Grant
Probabilistic and Extremal Combinatorics
概率和极值组合学
- 批准号:
0701183 - 财政年份:2007
- 资助金额:
$ 10.5万 - 项目类别:
Continuing Grant
Mathematical Sciences Postdoctoral Research Fellowships
数学科学博士后研究奖学金
- 批准号:
9627408 - 财政年份:1996
- 资助金额:
$ 10.5万 - 项目类别:
Fellowship Award
相似国自然基金
带奇点的extremal度量和toric流形上的extremal度量
- 批准号:10901160
- 批准年份:2009
- 资助金额:10.0 万元
- 项目类别:青年科学基金项目
相似海外基金
Extremal Combinatorics: Themes and Challenging Problems
极值组合学:主题和挑战性问题
- 批准号:
2401414 - 财政年份:2023
- 资助金额:
$ 10.5万 - 项目类别:
Continuing Grant
Extremal Combinatorics: Themes and Challenging Problems
极值组合学:主题和挑战性问题
- 批准号:
2246641 - 财政年份:2023
- 资助金额:
$ 10.5万 - 项目类别:
Continuing Grant
Extremal Combinatorics: Problems and Algorithmic Aspects
极值组合学:问题和算法方面
- 批准号:
2154082 - 财政年份:2022
- 资助金额:
$ 10.5万 - 项目类别:
Continuing Grant
CAREER: Problems in Extremal and Probabilistic Combinatorics
职业:极值和概率组合问题
- 批准号:
2146406 - 财政年份:2022
- 资助金额:
$ 10.5万 - 项目类别:
Continuing Grant
Problems in Extremal Combinatorics with Applications to Statistical Physics
极值组合问题及其在统计物理中的应用
- 批准号:
574977-2022 - 财政年份:2022
- 资助金额:
$ 10.5万 - 项目类别:
University Undergraduate Student Research Awards
Problems in Extremal and Geometric Combinatorics
极值和几何组合问题
- 批准号:
2154063 - 财政年份:2022
- 资助金额:
$ 10.5万 - 项目类别:
Continuing Grant
Problems in Extremal Combinatorics and Finite Geometry
极值组合学和有限几何问题
- 批准号:
1855723 - 财政年份:2019
- 资助金额:
$ 10.5万 - 项目类别:
Standard Grant
Problems and Methods in Extremal Combinatorics
极值组合学中的问题和方法
- 批准号:
1855464 - 财政年份:2019
- 资助金额:
$ 10.5万 - 项目类别:
Continuing Grant
Problems in additive and extremal combinatorics
加法和极值组合问题
- 批准号:
2114524 - 财政年份:2018
- 资助金额:
$ 10.5万 - 项目类别:
Studentship