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)建立理论和计算图轮廓的热带化，这是更简单的，但捕获所有有效的纯二项式不等式，并使用这些计算来解决极值图理论中的问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。