Problems in Probabilistic Combinatorics

概率组合学问题

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

1. The proposed project covers several topics in ProbabilisticCombinatorics. The first group of questions is about graph colorings.It mainly deals with the study of chromatic and choice numbers ofgraphs satisfying certain local conditions. One of the open problemwhich investigators will study is bounding the chromatic number of agraph G with maximum degree d, which contains no copy of a fixed graphH. A variant of this problem was posed already twenty years ago byKomlos and Szemeredi and so far it was solved only for some specialcases. Investigator also plans to work on a few related questionsabout vertex list coloring and acyclic edge coloring of graphs.Another set of questions is about asymptotic properties of random graphsand random regular graphs. Here investigators goal is to understandthe distribution of independent sets of nearly optimal size in sparserandom graphs, and use this to determine the asymptotic behavior ofits choice number. It is sometimes the case that an existence proof,supplied by the probabilistic method, is not sufficient and it isbetter to have an explicit construction. One of the major openproblems in this field is to construct exponentially large graphs,without a clique or an independent set of size k. In this projectinvestigator intends to consider this problem together with itsbipartite version. He also plans to study the properties ofpseudo-random graphs and their applications.2. Leave nothing to chance. This cliche embodies the common beliefthat randomness has no place in carefully planned methodologies.In modern Combinatorics at least, nothing can be further from thetruth. Here the Probabilistic Method has been developed intensivelyand become one of the most powerful and widely used tools.Use of probability proved to be helpful in tackling many longstanding open problems. Another major reason for the development ofthis method is the important role of randomness in TheoreticalComputer Science. Here algorithm which make random choices during itsexecution proved to be simplest and fastest for many applications.

1.拟议项目涉及概率组合学的几个主题。第一组问题是关于图的着色，它主要研究满足某些局部条件的图的色数和选择数。图G的最大度为d的色数不包含固定图H的副本，这是研究人员将要研究的公开问题之一。二十年前，Komlos和Szmeredi已经提出了这个问题的一个变体，到目前为止，它只在一些特殊情况下得到了解决。研究者还计划研究与图的顶点列表染色和非圈边染色相关的几个问题。另一组问题是关于随机图和随机正则图的渐近性质。在这里，研究者的目标是了解稀疏随机图中大小接近最优的独立集的分布，并利用这一分布来确定其选择数的渐近行为。有时，由概率方法提供的存在性证明是不够的，最好是有一个明确的构造。在这个领域中的一个主要的公开问题是构造指数大的图，而不需要团或大小为k的独立集。在这个项目中，研究者打算结合它的二部版本来考虑这个问题。他还计划研究伪随机图的性质及其应用。不留任何侥幸心理。这种陈词滥调体现了一种普遍的信念，即随机在精心设计的方法论中是没有立足之地的。至少在现代组合学中，没有什么比这更离谱了。在这里，概率方法得到了大力发展，成为最强大、最广泛使用的工具之一。概率的使用被证明有助于解决许多长期悬而未决的问题。发展这种方法的另一个主要原因是随机性在理论计算机科学中的重要作用。在这里，在执行过程中进行随机选择的算法被证明是许多应用程序中最简单、最快的算法。