d-Matching Polynomials and Families of Graphs

d 匹配多项式和图族

• 批准号: RGPIN-2018-06429
• 负责人: Hall, Christopher
• 金额: $ 1.31万
• 依托单位: University of Western Ontario
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=652839
• 关键词: Matching; Polynomials; Families; Graphs

This is a proposal to study some variational problems for graphs. A graph is a collection of "nodes" and of "edges" between the nodes, and they play a fundamental role in many areas of Mathematics and other disciplines. For example, in Computer Science, one can use graphs to represent the Internet and other networks: computers are "nodes" and ethernet/wifi connections are "edges". Also, in Epidemiology and Sociology, can use graphs to represent a population of people and their social relationships. For some applications in these areas, it is natural to speak of a "random" graph and then to ask about properties of various averages. Making a precise definition of "random" is a fundamental problem in graph theory, and finding "interesting" averages one can explicitly calculate is an important area of research.******In this proposal we focus on theoretically motivated calculations. We consider mainly two types of "random" graph. For each type, we start with a "base graph" G, and then we apply two different recipes from constructing a new collection of graphs all sharing a common relationship with G. Using these collections one can formulate variation questions for graphs which resemble well-known and important variational questions in geometry. Previous work two coauthors and I did, we showed this resemblance reflects a deep genuine relationship between the two areas. More recently, two other coauthors and I showed how to calculate an average with very interesting properties, and that enabled us to find a significant generalization of a spectacular (mathematical) result of A. Markus, D. Spielman, and N. Srivastava. We also defined a new polynomial associated to a graph --- the d-matching polynomial --- and showed it satisfes remarkable properties. We propose to continue studying these polynomials. We also propose to study the variation of other mathematical objects one can associated to each "random" graph (e.g., a finite abelian group called the Jacobian). In particular, insight into our variational problems for graphs may offer insight into the analogous problems for geometry.******We propose four objectives and projects for four PhD students. I will supervise each of the students as they complete a PhD, training can be individualized to take the students career aspirations into account. To solve the problems I have chosen will require each to develop a broad skill set and knowledge base, and this will strengthen their ability to find common ground with researchers in the field and in other insitutions.*****

这是一个关于研究图的一些变分问题的建议。图是“节点”和节点之间的“边”的集合，它们在数学和其他学科的许多领域中扮演着基本的角色。例如，在计算机科学中，人们可以用图形来表示互联网和其他网络：计算机是“节点”，而以太网/WiFi连接是“边”。此外，在流行病学和社会学中，可以使用图表来表示人群及其社会关系。对于这些领域中的一些应用程序，很自然地会先提到一个“随机”图，然后再询问各种平均值的属性。给“随机”下一个精确的定义是图论中的一个基本问题，而找到一个可以显式计算的“有趣的”平均值是一个重要的研究领域。我们主要考虑两种类型的“随机”图。对于每一种类型，我们从一个“基图”G开始，然后我们应用两种不同的方法来构造一个新的图集合，这些图都与G有共同的关系。使用这些集合，我们可以为图制定变分问题，这些问题类似于几何中众所周知的重要变分问题。我和两位合著者之前所做的工作，我们表明这种相似之处反映了这两个领域之间深刻的真实关系。最近，我和另外两位合著者展示了如何用非常有趣的性质计算平均值，这使我们能够找到A.Markus、D.Spielman和N.Sriastava的一个壮观(数学)结果的重要推广。我们还定义了一个与图相关的新的多项式-d-匹配多项式-并证明了它满足显著的性质。我们建议继续研究这些多项式。我们还建议研究与每个“随机”图相关的其他数学对象的变化(例如，称为雅可比的有限阿贝尔群)。特别是，我们对图的变分问题的洞察可能会提供对几何的类似问题的洞察。*我们为四名博士生提出了四个目标和项目。我会监督每个学生完成博士学位，培训可以个性化的考虑到学生的职业抱负。要解决我选择的问题，每个人都需要发展广泛的技能和知识基础，这将增强他们与该领域和其他机构的研究人员找到共同点的能力。