Extremal Combinatorics

格里格斯9701211 该奖项为极值组合学的进一步研究提供资金。在极值集合论中，人们可以用新的问题“有多少个集合”来代替旧的问题“在下面的限制下可以有多少个集合”。 在以下限制下可以具有集合族。 研究人员将推进这一研究领域的项目，这是由R。Ahlswede等，从信息论的强烈动机。 研究者将研究向量和阿贝尔群元素的子集和分布。 这一领域的知识开始与利特尔伍德-奥福德问题，并成为依赖于极值集理论。向更高维度的扩展提出了具有根本利益的诱人的新问题。研究人员将研究的极值图论问题包括：（1）度有界图中独立比的界，限制最大团大小，以及保证达到界的独立集算法。 (2)在排除圈条件下具有给定部分的二部图的最大尺寸。 (3)n-顶点图的最大尺寸，使得没有k个顶点有超过m条边，继续工作（由Griggs等人）。关于Turan和Dirac Szekely定理的推广，Szekely最近发现了图的交叉数与组合几何中的Szemeredi-Trotter定理之间的联系。 在此基础上，研究者将从极值拓扑图论的角度考虑以下问题：（4）图的交叉数的界。 (5)交叉数与组合几何关系的进一步研究。 (6)图，其中排除了许多成对交叉的边。 这是极值组合学的研究，这是我们理解离散结构如何工作以及如何最佳使用它们的核心主题。在极值组合学中有大量重要的长期未决问题，而新的问题经常来自附近快速发展的领域，如信息论、计算机科学、计算生物学或数论。某些数据库安全模型需要解决某些极值组合问题，以优化其性能。

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.