Extremal graph theory, graph limits, and algebraic invariants

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

In this project, the PI aims to study very large networks using algebraic and analytic tools. Large networks like the Internet, molecular lattices and social networks (such as Facebook) naturally arise in many different areas of real life. The PI aims to look at these from a new perspective: we consider them as approximations of an infinite object. For molecular lattices this is a very natural approach, but via a recently developed theory of sparse graph convergence we can tackle a much broader class of problems, creating new links between mathematics, statistical physics and computer science. The PI will investigate two essentially different, but still related topics. The first one is the study of extremal values of algebraic invariants of graphs with a special emphasis on those problems where the conjectured extremal graphs are not finite. Despite the lack of finite extremal solutions, using the recently emerging language of Benjamini--Schramm convergence, one can find and analyze the extremal solutions. This then leads to new asymptotic results on finite graphs. The second topic is the study of certain special infinite graphs and lattices via graph limit theory and analytic and algebraic combinatorics. The general theme is to consider a graph invariant of algebraic nature and analyze its limiting behaviour using analytic tools. Often the invariants come from graph polynomials like the matching, chromatic and independence polynomials and have various ties to statistical mechanics.