Grant: Discovery Grants Program - Individual

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.