Problems and Methods in Extremal Combinatorics

极值组合学研究满足规定的所需属性集的组合对象的最大或最小可能大小。这种类型的问题往往是由其他领域的应用，包括理论计算机科学，几何和信息理论的动机。这是现代组合数学中最活跃的领域之一，在过去的几十年里得到了长足的发展。在这个项目中，PI打算研究该领域的几个基本问题，包括那些由算法应用程序驱动的问题。一个典型的例子是找到一个图的最小可能大小的问题，该图包含给定家族的每个成员作为导出子图。这与在分布式系统中以经济的方式存储家庭成员的能力密切相关。预计就提案中所述问题开展的工作将产生新的方法和新的应用。预计该项目将通过指导研究这些主题的研究生以及向专家和研究生和本科生提供有关这些主题和相关主题的讲座，为通过教育促进数学做出贡献。该项目的目的是研究极值组合学中的几个重要问题，包括由算法应用引起的问题。第一个主题涉及泛图，泛图是包含给定家族的每个成员作为导出子图的图。对给定有趣族的泛图的最小可能顶点数的研究是由邻接标号方案的研究引起的，并受到了相当大的关注。在这一领域内，主要目标是获得最小可能大小的泛图或超图的严格估计，对于具有给定顶点数的所有图或超图的族，给定组的所有凯莱图的族，以及简单几何对象的相交图的几个族。第二个主题涉及超图的迹及其VC-维数和Littlestone维数的相关概念。PI希望证明一般极值问题的新界限，即估计给定大小的顶点集上的最大投影数，这可以在具有给定数量的顶点和边的任何hpergraph中得到保证。在这些问题和相关问题的研究中，PI计划应用和开发一系列方法，将组合、概率、代数和几何工具与编码理论的思想相结合。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Extremal Combinatorics investigates the maximum or minimum possible sizes of combinatorial objects satisfying prescribed sets of required properties. Questions of this type are often motivated by applications in other areas including theoretical computer science, geometry and information theory. This is one of the most active areas in modern Combinatorics and has developed spectacularly over the last decades. In this project the PI intends to investigate several fundamental problems in the area, including ones that are motivated by algorithmic applications. A representative example is the problem of finding the smallest possible size of a graph that contains every member of a given family as an induced subgraph. This is closely related to the ability to store members of the family in an economical way in distributed systems. It is expected that work on the problems addressed in the proposal will lead to new methods and new applications. It is also expected that the project will contribute to advancing mathematics through education by mentoring graduate students working on these topics and by giving lectures on these and related subjects to experts and to graduate and undergraduate students.The aim of the project is to study several important problems in Extremal Combinatorics, including ones motivated by algorithmic applications. The first topic addressed deals with universal graphs which are graphs that contain every member of a given family as an induced subgraph. The investigation of the smallest possible number of vertices of universal graphs for prescribed interesting families is motivated by the study of adjacency labeling schemes and received a considerable amount of attention. Within this area, the main goals are to obtain tight estimates for the smallest possible sizes of universal graphs or hypergraphs for the family of all graphs or hypergraphs with a given number of vertices, the family of all Cayley graphs of a given group, and several families of intersection graphs of simple geometric objects. The second topic proposed concerns traces of hypergraphs and the related notions of their VC-dimension and Littlestone dimension. The PI hopes to prove new bounds for the general extremal problem of estimating the maximum number of projections on a set of vertices of a given size that can be guaranteed in any hpergraph with a given number of vertices and edges. In the study of these problems and related ones the PI plans to apply and develop a range of methods combining combinatorial, probabilistic, algebraic and geometric tools with ideas from Coding Theory.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.