CAREER: Graph Profiles: Complexity and Computations

工程、科学、经济和社会科学中的许多问题都涉及可以用图形表示的复杂系统。例如，道路网络、人脑、社会网络以及蛋白质之间的相互作用都可以用图表来表示。计算这些图的不同性质可以获得有关原始问题的有价值的信息，但由于图的大小，这样做很困难。研究这种大图的一种技术是通过确定某些小的子结构有多普遍来局部地理解它们，例如通过同态密度。这个项目的目标是加深我们对图形轮廓的理解，图形轮廓是记录这些局部模式之间所有可能关系的对象。该项目还试图通过一项以三大支柱为基础的教育计划，使更多的人能够接触到更高层次的数学，特别是离散数学：多样性、监狱教育和基于研究的课程。这个项目的研究部分将集中在四个方向上：(1)计算图轮廓，包括一些超过两维的图轮廓；(2)研究不同技术(例如，(有理)平方和，非负回路和)在证明图轮廓上的不等式方面的优势和局限性；(3)更好地了解图轮廓上的哪类不等式证明是(不可)确定的；(4)建立理论和计算图形轮廓的热带化，它更简单，但捕捉到所有有效的纯二项式不等式，并使用这些计算来解决极值图论中的问题。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Many problems in engineering, science, economics, and social sciences involve complicated systems that can be represented as graphs. For example, road networks, the human brain, social networks, and interactions between proteins can all be represented as graphs. Computing different properties of these graphs yields valuable information about the original problems, but it is difficult to do so because of the size of the graphs. One technique to study such large graphs is to understand them locally by determining how prevalent certain small substructures are, for example through homomorphism densities. The objective of this project is to further our understanding of graph profiles, objects that record all possible relationships between these local patterns. This project also seeks to make higher-level math, in particular discrete mathematics, accessible to a greater segment of the population through an educational plan resting on three pillars: diversity, prison education, and research-based courses. The research component of this project will focus on four directions: (1) to compute graph profiles, including some in more than two dimensions; (2) to study the strengths and limitations of different techniques (e.g., (rational) sums of squares, sums of nonnegative circuits) in proving inequalities over graph profiles; (3) to better understand for which classes of inequalities certification over graph profiles is (un)decidable; (4) to build theory and compute tropicalizations of graph profiles, which are simpler and yet capture all valid pure binomial inequalities, and to use these computations to resolve problems in extremal graph 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.