Extremal Combinatorics

极值组合学

• 批准号: 9701211
• 负责人: Jerrold Griggs
• 金额: $ 13.5万
• 依托单位: University of South Carolina at Columbia
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-07-15 至 2001-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9701211&HistoricalAwards=false
• 关键词: Extremal; Combinatorics

Griggs 9701211 This award funds further research in extremal combinatorics. In extremal set theory, one can replace the old questions, ``how many sets can one have under the following restrictions'', by new ones, ``how many families of sets can one have under the following restrictions''. The investigators will advance projects in this area of research, which was started by R. Ahlswede et al. with strong motivation from information theory. The investigators will study subset sum distributions of vectors and abelian group elements. This area of knowledge started with the Littlewood-Offord problem and became dependent on extremal set theory. Extensions to higher dimensions suggest tantalizing new problems of fundamental interest. Problems from extremal graph theory the investigators will investigate include: (1) Bounds for the independence ratio in degree-bounded graphs, with restricted maximum clique size, and algorithms for independent sets guaranteed to achieve the bounds. (2) The maximum size of bipartite graphs with given parts under excluded cycle conditions. (3) The maximum size of n-vertex graphs such that no k vertices have more than m edges, continuing work (by Griggs et al.) on generalizations of theorems of Turan and Dirac Szekely recently discovered a connection between crossing numbers of graphs and the Szemeredi-Trotter theorems in combinatorial geometry. The investigators will build on this progress by considering these problems from extremal topological graph theory: (4) Bounds for crossing numbers of graphs. (5) Further investigation of the connection between crossing numbers and combinatorial geometry. (6) Graph drawings, where many pairwise crossing edges are excluded. This is research in extremal combinatorics, a subject at the very core of our understanding of how discrete structures work and how to use them optimally. Significant longstanding open problems are abundant in extremal combinatorics, and new problems frequently come from nearby rapidly d eveloping fields such as information theory, computer science, computational biology, or number theory. Certain database security models require the solution of certain extremal combinatorics problems in order to optimize their performance.

格里格斯9701211该奖项为极值组合数学的进一步研究提供资金。在极值集合论中，人们可以用“在下列限制下可以有多少个集合”的旧问题，用“在下列限制下一个人可以有多少个集族”的新问题来代替。研究人员将推进这一研究领域的项目，该领域由R.AhlSwede等人启动。拥有来自信息论的强大动力。研究人员将研究向量和阿贝尔群元素的子集和分布。这一领域的知识始于Littlewood-Offord问题，后来依赖于极值集合论。向更高维度的延伸表明，涉及根本利益的新问题令人着迷。研究人员将研究的极值图论问题包括：(1)有限度有界图的独立比的界，以及保证达到这个界的独立集的算法。(2)在圈排除条件下，给定部分的二部图的最大长度。(3)n-顶点图的最大长度，使得没有k个顶点有超过m条边，继续工作(Griggs等人)。关于Turan和Dirac的定理的推广，Szekely最近发现了图的交叉数与组合几何中的Szmeredi-Trotter定理之间的联系。研究人员将在这一进展的基础上，考虑极值拓扑图理论中的以下问题：(4)图的交叉数的界限。(5)进一步研究了交叉数与组合几何的关系。(6)图的绘制，其中不包括许多两两交叉的边。这是对极值组合学的研究，这是我们理解离散结构如何工作以及如何最佳使用它们的核心主题。在极值组合数学中，长期存在的重大公开问题比比皆是，而新的问题往往来自附近迅速发展的领域，如信息论、计算机科学、计算生物学或数论。某些数据库安全模型需要解决某些极值组合问题，以优化其性能。