Problems in Extremal and Probabilistic Combinatorics

极值和概率组合学问题

• 批准号: 0355497
• 负责人: Benjamin Sudakov
• 金额: $ 11.99万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-07-01 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0355497&HistoricalAwards=false
• 关键词: Problems; Extremal; Probabilistic; Combinatorics

The proposed project covers several important topics in Extremal andProbabilistic Combinatorics. The first group of questions concerns theRamsey and Turan numbers of sparse graphs. More precisely, the authorwants to study degenerate graphs, i.e., graphs in which every subgraph hasbounded average degree. Here one goal is to show that such graphs haveRamsey numbers which grow linearly in the size of the graph. An additionalgoal is to obtain tight estimates for the Turan numbers of degeneratebipartite graphs. Both problems were posed many years ago by Erdos, anddespite all efforts are still open. Another set of questions deals mainlywith the study of the chromatic and choice numbers of graphs. The authorplans to study two conjectures about graphs whose choice number is equalto their chromatic number. Since usually there is a huge gap between thesetwo parameters, cases in which equality holds are extremely interesting.Another set of questions is about asymptotic properties of random graphs.Here investigators goal is to understand the distribution of independentsets of nearly optimal size in sparse random graphs, and use this todetermine the asymptotic behavior of its choice number. It is sometimesthe case that an existence proof, supplied by the probabilistic method, isnot sufficient and it is better to have an explicit construction. One ofthe major open problems in this field is to construct exponentially largegraphs, without a clique or an independent set of size k. In this projectinvestigator intends to consider this problem together with its bipartiteversion.Leave nothing to chance. This cliche embodies the common belief thatrandomness has no place in carefully planned methodologies. In modernCombinatorics at least, nothing can be further from the truth. Here theProbabilistic Method has been developed intensively and become one of themost powerful and widely used tools. Use of probability proved to behelpful in tackling many long standing open problems. Another major reasonfor the development of this method is the important role of randomness inTheoretical Computer Science. Here algorithm which make random choicesduring its execution proved to be simplest and fastest for manyapplications. The PI plans to develop new probabilistic tools andtechniques and apply them to various combinatorial problems. Some of theseproblems and conjectures have been open for few decades.

拟议的项目涵盖极值和概率组合学的几个重要主题。第一组问题涉及稀疏图的Ramsey数和Turan数。更准确地说，作者想研究退化图，即，图中每个子图的平均度有界。这里的一个目标是表明，这样的图haveRamsey数的线性增长的大小的图。另一个目标是得到退化二部图的Turan数的紧估计。这两个问题都是鄂尔多斯多年前提出的，尽管付出了一切努力，但仍然没有解决。另一组问题主要涉及图的色数和选择数的研究。本文研究了两个选择数等于图的色数的图.由于这两个参数之间通常存在巨大的差距，因此等式成立的情况非常有趣。另一组问题是关于随机图的渐进性质。这里研究人员的目标是了解稀疏随机图中几乎最佳大小的独立集的分布，并利用它来确定其选择数的渐进行为。有时候，由概率方法提供的存在性证明是不够的，最好有一个明确的结构。这一领域的主要问题之一是构造指数大数图，而不存在团或大小为k的独立集。在这个项目中，研究者打算把这个问题连同它的两个版本一起考虑。这种陈词滥调体现了一种普遍的信念，即随机性在精心计划的方法中没有地位。至少在现代组合数学中，没有什么比这更远离真理了。在这里，概率方法得到了深入的发展，并成为最强大和最广泛使用的工具之一。使用概率被证明有助于解决许多长期悬而未决的问题。这种方法发展的另一个主要原因是随机性在理论计算机科学中的重要作用。这里的算法在执行过程中进行随机选择，对于许多应用程序来说是最简单、最快的。PI计划开发新的概率工具和技术，并将其应用于各种组合问题。其中一些问题和建议已经公开了几十年。