Turan-type problems and probabilistic methods in extremal combinatorics

极值组合学中的图兰型问题和概率方法

• 批准号: 0800704
• 负责人: Jacques Verstraete
• 金额: $ 14.4万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-07-01 至 2012-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0800704&HistoricalAwards=false
• 关键词: Turan; type; problems; probabilistic; methods

This proposal concerns research in extremal and probabilistic combinatorics. Broadly speaking, extremal combinatorics addresses the existence of and theoretical bounds on the sizes of combinatorial objects with certain local restrictions imposed. Many of the important problems, while simple to state and attractive, are often representative of more general phenomena in mathematics, and lead to many unexpected and useful applications in other areas. For example, the topics of expander graphs and Ramanujan graphs have had a major impact on coding, complexity and information theory. These problems also lead to new theoretical methods, perhaps the most remarkable instance of which is the probabilistic method pioneered by the renowned mathematician Paul Erdos. Extremal combinatorial methods lead to the construction of new and more efficient codes for correcting errors in data transmission, the reduction of the number of bits required for Monte-Carlo algorithms, such as randomized algorithms for primality testing. In fact, the spectacular recent breakthrough of a deterministic algorithm for primality testing is highly connected to preceding randomized algorithms which were long known to exist. In my proposal I plan to study further theoretical and practical applications, including the problem of time-complexity of matrix multiplication, quadratic sieve-type integer factoring algorithms, and questions in other areas of mathematics. In mathematics, this work has implications in functional analysis, projective geometry, spectral graph theory, coding theory, and algorithms. While these open problems are important and clearly difficult, some major inroads are possible by combining probabilistic and combinatorial techniques with some new ideas.Combinatorial mathematics lies at the heart of many modern-day operations, such as digital security, web searching, and reliable data transmission. Examples include multiplication of large arrays of numbers for qualitative web searches -- these matrices tend to have billions of rows and columns; the RSA cryptosystem, which underpins much of modern digital security, and is based strongly on the belief that factoring integers is difficult; finally, transmission of data over noisy or unreliable channels is at the core of coding theory, where one attempts to design novel ways of encoding a message so that even if the message is perturbed in transmission, the receiver can still figure out with high probability what the original message was. One of the major ingredients for constructing such good error-correcting codes is the existence of combinatorial objects known as expander graphs. Using explicit constructions and variants of these objects, together with basic probabilistic arguments, one can compress a message in an optimal way such that the receiver has an excellent chance of figuring out what the original message was. Constructions of graphs with such extremal properties is fundamental to the proposed research. In addition, the researcher plans to use combinatorial and probabilistic techniques to approach the problems of matrix multiplication and integer factoring, both of which are central to the concrete examples listed above. The researcher plans to investigate both the practical and theoretical applications of the above-mentioned combinatorial and probabilistic methods.

该提案涉及极值和概率组合学的研究。 从广义上讲，极值组合学解决了施加某些局部限制的组合对象大小的存在性和理论界限。许多重要的问题虽然表述起来简单且有吸引力，但往往代表了数学中更普遍的现象，并在其他领域带来了许多意想不到的有用的应用。 例如，扩展图和拉马努金图的主题对编码、复杂性和信息论产生了重大影响。 这些问题也催生了新的理论方法，其中最引人注目的例子也许是著名数学家保罗·埃尔多斯（Paul Erdos）首创的概率方法。 极值组合方法导致构建新的、更有效的代码来纠正数据传输中的错误，减少蒙特卡罗算法所需的位数，例如用于素性测试的随机算法。事实上，素性测试的确定性算法最近取得的惊人突破与早已存在的先前随机算法密切相关。在我的提案中，我计划研究进一步的理论和实际应用，包括矩阵乘法的时间复杂度问题、二次筛式整数分解算法以及其他数学领域的问题。 在数学方面，这项工作对泛函分析、射影几何、谱图理论、编码理论和算法都有影响。 虽然这些开放问题很重要而且显然很困难，但通过将概率和组合技术与一些新想法相结合，一些重大进展是可能的。组合数学是许多现代操作的核心，例如数字安全、网络搜索和可靠的数据传输。 例子包括用于定性网络搜索的大量数字的乘法——这些矩阵往往有数十亿行和列； RSA 密码系统，它是现代数字安全的基础，并且强烈地基于整数分解是困难的信念；最后，通过嘈杂或不可靠的信道传输数据是编码理论的核心，人们试图设计新颖的消息编码方法，以便即使消息在传输过程中受到干扰，接收者仍然能够以很高的概率弄清楚原始消息是什么。 构造如此好的纠错码的主要成分之一是称为扩展图的组合对象的存在。 使用这些对象的显式构造和变体，以及基本的概率参数，可以以最佳方式压缩消息，以便接收者有很好的机会弄清楚原始消息是什么。具有这种极值特性的图的构造是所提出的研究的基础。此外，研究人员计划使用组合和概率技术来解决矩阵乘法和整数因式分解问题，这两者都是上面列出的具体示例的核心。 研究人员计划研究上述组合和概率方法的实际和理论应用。