CAREER: Graph Profiles: Complexity and Computations

职业：图形配置文件：复杂性和计算

• 批准号: 2338532
• 负责人: Annie Raymond
• 金额: $ 45万
• 依托单位: University of Massachusetts Amherst
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-07-01 至 2029-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2338532&HistoricalAwards=false
• 关键词: CAREER; Graph; Profiles; Complexity; Computations

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.

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