d-Matching Polynomials and Families of Graphs

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

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.