CAREER:Methods and Challenges in Discrete Mathematics

这份提案概述了一个具有挑战性的职业发展计划，重点是离散数学中的几个有趣的问题。PI计划工作的具体领域包括拉姆齐理论、图着色、极值组合学以及随机和伪随机图。此外，作者还计划研究这些领域在理论计算机科学中的应用。本研究中将使用的主要工具结合了组合技术、概率方法、线性代数工具和谱技术等。这项提案中的第一组问题涉及拉姆齐数。对于稀疏图，即每个子图都有有界平均度的图，作者想要给出这些数的界。这里的目的是证明这样的图有拉姆齐数，这些拉姆齐数随着图的大小线性增长。另一个主题是研究各种极值问题。特别地，推广了经典的Turan定理，证明了含有禁子图的图的最大割的更好的界。其中一些问题是鄂尔多斯多年前提出的，尽管做出了所有努力，但仍然悬而未决。另一组问题主要涉及对图的色数和选择数的研究。通常这两个参数之间有一个巨大的差距，所以这个建议的目标之一是理解色数和选择数相等的图。最后，PI还打算研究随机图和伪随机图的渐近性质，这是概率组合学的中心课题之一。组合学的概念和问题自然而然地出现在数学的许多分支中，也在其他学科中得到了应用。这些课程包括在信息论和电子工程、统计物理和分子生物学以及最著名的计算机科学方面的应用。国际数学协会相信，他所讨论的问题的进展将是有趣和重要的，并将导致离散数学的新发展。他认为，该项目产生的新方法和新技术也将在其他领域适用和有用。作者还提出了与他的项目密切相关的广泛的教育措施。他计划为高年级本科生和研究生开发一系列课程，这些课程将温和地介绍现代组合学中各种强大的方法。这些课程的一部分将与本提案中的研究问题密切相关。在这门课程中，作者计划通过引入开放式问题来将研究活动融入教学中，这些问题将激励学生对这些引人入胜的主题进行研究，从而获得学士学位论文或博士学位论文。

This proposal outlines a challenging career developments plan focusing on several fascinating problems in Discrete Mathematics. Specific areas in which PI plans to work include Ramsey Theory, Graph colorings, Extremal Combinatorics and Random and pseudo-random graphs. Furthermore the author plan to study application of all these areas to Theoretical Computer Science. The main tools which are going to be used in this investigation combine combinatorial techniques, probabilistic methods, tools from Linear Algebra and spectral techniques amongst the others. First group of questions in this proposal deals with Ramsey numbers. The author wants to bound these numbers for sparse graphs, i.e., graphs in which every subgraph has bounded average degree. Here the goal is to show that such graphs have Ramsey numbers which grow linearly in the size of the graph. An additional topic is to study various extremal problems. In particular to obtain extensions of classical Turan's theorem and prove better bounds on the Max Cut in the graphs with forbidden subgraphs. Some of these problems were posed many years ago by Erdos, and despite all efforts are still open. Another set of questions deals mainly with the study of the chromatic and choice numbers of graphs. Usually there is a huge gap between these two parameters, so one of the goals in this proposal is to understand the graphs for which chromatic and choice numbers are equal. Finally the PI also intends to study the asymptotic properties of random and pseudo-random graphs which is one of the central topics in Probabilistic Combinatorics. Concepts and questions of Combinatorics appear naturally in many branches of mathematics, and have also found applications in other disciplines. These include applications in Information Theory and Electrical Engineering, in Statistical Physics and Molecular Biology, and most notably in Computer Science. The PI is convinced that progress in the problems he discusses will be interesting and significant, and will lead to new developments in Discrete Mathematics. He believes that the new approaches and techniques resulting from this project will be applicable and useful in other fields as well. The author also proposes a wide range of educational measures closely related to his project. He plans to develop a series of courses for senior undergraduate and starting graduate students, which will serve as a gentle introduction to the variety of powerful methods in modern Combinatorics. Part of these courses will be closely related to the research problems in this proposal. Along the course, the author plans to integrate research activities into the teaching by introducing open questions that will motivate the students to undertake research on these fascinating topics, which can lead to a B.A. thesis or Ph.D. dissertation.