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.