Extremal hypergraphs, codes, designs, and combinatorial geometry

极值超图、代码、设计和组合几何

• 批准号: 0901276
• 负责人: Zoltan Furedi
• 金额: $ 51.86万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-06-15 至 2013-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0901276&HistoricalAwards=false
• 关键词: Extremal; hypergraphs; codes; designs; combinatorial

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.

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