Extremal hypergraphs, codes, designs, and combinatorial geometry

主要研究人员：Furedi，Zoltan提案编号：DMS-0901276机构：伊利诺伊大学香槟分校标题：极值超图、代码、设计和组合几何该奖项由2009年美国复苏和再投资法案(公共法律第111-5条)资助。PI研究了局部性质如何影响各种组合结构的全局参数。这是一个非常笼统的所谓图兰数问题的框架。PI计划继续他在这个主题上的工作，并从四个不同的方面进行研究：1.研究三重系和多重图的Turan数，作为实现r-图的一般理论的工具，例如，证明Kalai猜想。2.研究Turan问题的自然推广，如子结构的个数、稳定性问题，并考虑其他主图，如超立方体。3.研究一般编码理论、设计理论、组合几何问题、导致超图交集和其他Turan型问题的几何和代数图表示问题，如重叠和覆盖码，以及部分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.