Extremal hypergraphs, codes, designs, and combinatorial geometry

摘要 首席研究员：Furedi, Zoltan 提案编号：DMS - 0901276 机构：伊利诺伊大学厄巴纳-香槟分校 标题：极值超图、代码、设计和组合几何 该奖项根据 2009 年美国复苏和再投资法案（公法 111-5）提供资助。 PI 研究了局部属性如何影响各种组合结构的全局参数。这是所谓的图兰数问题的非常通用的框架。 PI 计划继续他在这个主题上的工作，并研究四个不同的方面： 1. 研究三元组和多重图的图兰数，作为实现 r 图一般理论的工具，例如证明 Kalai 猜想。 2. 研究图兰问题的自然概括，例如子结构的数量、稳定性问题，并考虑其他主图，例如超立方体。 3. 研究一般编码理论、设计理论、组合几何问题、几何和代数图表示，导致超图交集和其他图兰类型问题，例如叠加和覆盖代码以及部分G设计的完成问题。 4. 找到图兰数自然出现的几何/代数图表示，例如布拉格维数、交集和图的几何表示。 该提案的主题是局部属性对组合结构全局参数的影响，换句话说，就是极值组合。 PI 继续在理论计算机科学、编码理论和离散几何中寻找应用。组合数学处理计算机科学、数据挖掘和通信中产生的有限但非常大的问题。极值组合应用了其他数学领域的广泛工具和结果，另一方面，它在几何、整数规划、计算机科学、编码理论、偏序集维数论和密码学中也有许多有趣的应用。组合学是经济、快速、可靠的存储和获取数据结构的算法的理论基础。极值组合学和编码理论在计算机科学、计算机图形学和通信理论中的应用是不可或缺的。

ABSTRACTPrincipal Investigator: Furedi, Zoltan Proposal Number: DMS - 0901276 Institution: University of Illinois at Urbana-ChampaignTitle: Extremal hypergraphs, codes, designs, and combinatorial geometryThis award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5). The PI has studied how local properties affect the global parameters of various combinatorial structures. This is a very general framework of the so-called Turan number problems. The PI plans to continue his work on this topic and investigates four different aspects: 1. To study the Turan numbers of triple systems and multigraphs, as a tool to achieve a general theory for r-graphs, e.g., to prove Kalai's conjecture. 2. To investigate natural generalizations of Turan's question, like the number of substructures, stability questions, and consider other host-graphs, like the hypercube. 3. To study general coding theory, design-theory, combinatorial geometry problems, geometric and algebraic graph representations, which lead to hypergraph intersection and other Turan type problems, e.g., superimposed and covering codes, and the completion problem of partial G-designs. 4. To find geometric/algebraic graph representations where Turan numbers naturally emerge, e.g., Prague-dimension, intersection and geometric representations of graphs. The subject of this proposal is the effect of local properties on global parameters of combinatorial structures, in other words, extremal combinatorics. The PI continue to find applications in theoretical computer science, coding theory and discrete geometry. Combinatorics deals with finite but very large problems arising from computer science, data mining, and communications. Extremal combinatorics applies a broad array of tools and results from other fields of mathematics, on the other hand, it has a number of interesting applications in in geometry, integer programming, computer science, coding theory, dimension theory of partially ordered sets, and cryptography. Combinatorics is the theoretical basis of the economical, fast and reliable algorithms to store and reach data structures. Applications of extremal combinatorics and coding theory in computer science, computer graphics and in communication theory are indispensable.