CAREER:Methods and Challenges in Discrete Mathematics

职业：离散数学的方法和挑战

• 批准号: 0546523
• 负责人: Benjamin Sudakov
• 金额: $ 40.88万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-07-01 至 2008-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0546523&HistoricalAwards=false
• 关键词: CAREER; Methods; Challenges; Discrete; Mathematics

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.

该提案概述了一个具有挑战性的职业发展计划，重点关注离散数学中的几个迷人问题。PI计划工作的具体领域包括拉姆齐理论，图着色，极值组合学和随机和伪随机图。此外，作者还计划研究这些领域在理论计算机科学中的应用。主要的工具，这将被用于这项调查结合联合收割机组合技术，概率方法，工具，从线性代数和频谱技术等。第一组问题是关于Ramsey数的。作者希望将这些数字绑定到稀疏图，即，每个子图的平均度有界的图。在这里，我们的目标是表明，这样的图有拉姆齐数的线性增长的大小的图。另一个主题是研究各种极值问题。特别是推广了经典的Turan定理，证明了具有禁止子图的图的最大割的较好界。其中一些问题是由鄂尔多斯多年前提出的，尽管所有的努力仍然开放。另一组问题主要涉及图的色数和选择数的研究。通常这两个参数之间存在巨大的差距，因此本提案的目标之一是理解色数和选择数相等的图。最后，PI还打算研究随机和伪随机图的渐近性质，这是概率组合学的中心课题之一。组合数学的概念和问题自然地出现在数学的许多分支中，并且在其他学科中也有应用。这些应用包括信息理论和电气工程，统计物理学和分子生物学，最值得注意的是计算机科学。PI相信，他所讨论的问题的进展将是有趣和重要的，并将导致离散数学的新发展。他认为，该项目产生的新方法和技术也将适用于其他领域。作者还提出了一系列与其项目密切相关的教育措施。他计划为高年级本科生和刚开始的研究生开发一系列课程，这些课程将作为现代组合学中各种强大方法的温和介绍。这些课程的一部分将与本建议书中的研究问题密切相关。沿着课程，作者计划通过引入开放性问题将研究活动融入教学，这些问题将激励学生对这些迷人的主题进行研究，这可能会导致BidoA。论文或博士学位论文