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 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。