Problems in Probabilistic Combinatorics

1. 提议的项目涵盖了概率组合学中的几个主题。第一组问题是关于图形着色的。主要研究满足一定局域条件的图的色数和选择数。研究人员将研究的一个开放问题是最大度为d的图G的色数边界，其中不包含固定图h的副本。这个问题的一个变体早在20年前就由komlos和Szemeredi提出了，到目前为止，它只在一些特殊情况下得到了解决。研究者还计划对图的顶点表着色和无环边着色等相关问题进行研究。另一组问题是关于随机图和随机正则图的渐近性质。在这里，研究者的目标是理解稀疏随机图中接近最优大小的独立集的分布，并用它来确定其选择数的渐近行为。有时，由概率方法提供的存在性证明是不够的，最好有一个明确的构造。该领域的主要开放问题之一是构造指数大的图，没有团或大小为k的独立集。在这个项目中，研究者打算考虑这个问题及其二部版本。他还计划研究伪随机图的性质及其应用。不要留下任何机会。这种陈词滥调体现了一种普遍的信念，即随机在精心规划的方法中没有一席之地。至少在现代组合学中，没有什么比这更偏离真理了。在这里，概率方法得到了广泛的发展，并成为最强大和最广泛使用的工具之一。事实证明，概率的使用有助于解决许多长期存在的开放性问题。发展这种方法的另一个主要原因是随机性在理论计算机科学中的重要作用。在执行过程中进行随机选择的算法被证明是最简单和最快的。

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.