External Combinatorics and Codes

外部组合数学和代码

• 批准号: 0140692
• 负责人: Zoltan Furedi
• 金额: $ 12.3万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-05-15 至 2005-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0140692&HistoricalAwards=false
• 关键词: External; Combinatorics; Codes

The investigator studies how local properties affect the global parameters of different combinatorial structures. This is a very general framework of the so called Turan number problems. The investigator emphasizes four different aspects 1. To study the Turan numbers of triple systems and multigraphs, as a tool to achieve a general theory for hypergraphs. 2. To study covering radius problems, especially concerning constant weight codes where Turan numbers naturally emerge. 3. To study more general coding theory problems, like superimposed codes, identifying codes which lead to hypergraph intersection problems. 4. To find geometrical, and algebraic representations, like Lovasz' Shannon capacity bound, Ramanujan graphs, polarity graphs, Prague dimension of graphs, where Turan numbers naturally emerge.Most finite problems can be formulated as extremal graph or hypergraph problems. Extremal combinatorics applies a broad array of tools and results from other fields of mathematics like number theory, linear and commutative algebra, probability theory, geometry, and information theory. On the other hand it has a number of interesting applications in all parts of combinatorics, and in geometry, integer programming, computer science, coding theory, dimension theory of partially ordered sets, encryptions.Applications of extremal combinatorics and coding theory in computer science and communication theory are indispensable.

研究人员研究局部属性如何影响不同组合结构的全局参数。这是所谓的图兰数问题的非常通用的框架。研究者强调四个不同的方面： 1. 研究三元组和多重图的图兰数，作为实现超图一般理论的工具。 2. 研究覆盖半径问题，特别是图兰数自然出现的恒重码。 3. 研究更一般的编码理论问题，例如叠加编码、识别导致超图相交问题的编码。 4. 找到几何和代数表示，例如 Lovasz 的香农容量界、拉马努金图、极性图、图的布拉格维数，其中图兰数自然出现。大多数有限问题可以表述为极值图或超图问题。极值组合学应用了其他数学领域的广泛工具和结果，如数论、线性和交换代数、概率论、几何和信息论。另一方面，它在组合学的各个部分以及几何、整数规划、计算机科学、编码理论、偏序集维数论、加密中都有许多有趣的应用。极值组合学和编码理论在计算机科学和通信理论中的应用是不可或缺的。