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的法定任务，并被认为是通过基金会的智力优点和广泛影响的评估来评估CRETERIA的评估。