NSF-BSF: The Global Geometry of Graphs

Princeton University, Princeton NJ

Investigators

Abstract

A graph consists of a collection of nodes, some pairs of which are deemed to be related to each other, in which case they are said to form an edge. The notion of a graph is extremely general and expressive, as it can model arbitrarily complicated pairwise interactions among any collection of objects. This makes graphs important for essentially all aspects of human interests (ranging from, for example, social interactions, to science, internet search, engineering, and pure mathematics). This also makes the world of graphs immensely rich and complicated. It is therefore highly desirable to develop methodologies that could enhance one’s ability to understand and utilize graphs. This joint research project is devoted to further elucidate the geometric perspective of graphs, which provides deep and often unexpected insights on their structure. A graph induces a geometry on its nodes by defining its associated notion of distance to be the minimum number of hops along edges of the graph that is required to reach one node to another. One of the main questions that will be investigated is how the local structure of a graph, namely how it looks near each of its nodes, imposes restrictions on the behavior of its global properties. For example, if the graph does not contain short cycles (a phenomenon that is common in many cases of interest), then near each node one sees a tree. However if the graph is finite, then these local trees cannot maintain their tree-like growth indefinitely, that is, they must somehow eventually merge. It is remarkable how little is presently known about how having a local tree-like structure influences the global structure of a graph. This joint research project will tackle the abundance of longstanding mysteries about the global ramifications of being locally a tree. There is a wealth of further local-global geometric mysteries about graphs, such as fundamental questions about codes (existence and limitations thereof), which are subsets of a high-dimensional graph called the discrete cube in which all nonzero pairwise distances are large. Other issues that will be studied in this joint research project include finding algorithms to efficiently partition graphs, low-dimensional representations, representation of the graph distance as a superposition of much simpler distance functions, etc. This joint NSF-BSF project will provide an opportunity to enhance the interaction between U.S. and Israeli researchers who have been attacking such questions separately from different angles. It will address specific questions in these directions, and will also develop overarching methodologies to understand graphs through the lens of the global geometry that they induce. The idea that geometry may provide deep and often unexpected insights in discrete mathematics has been immensely fruitful. Suffices it to mention how isoperimetric inequalities have evolved into sophisticated concepts such as expander graphs which play a fundamental role in areas ranging from group theory to theoretical computer science and many other topics in between. More specifically, this joint research project will investigate the global geometry of graphs. One of the main questions that will be investigated is to what extent a finite graph can look locally like an infinite regular tree. Such a finite graph clearly has no short cycles, i.e., it has a large girth. Also its diameter should be small. How large can the girth be? How small can the diameter be? Can a graph simultaneously have a large girth and a small diameter? To what extent can the metric on a large girth graph be approximated by a superposition of cut metrics or by a Euclidean metric? Arguably, the most important metric space for combinatorics is the discrete cube and its powers. Understanding the independence number of these graphs is a classical open question: The rate versus distance problem for binary codes. The best bounds that are presently available are nearly a half a century old. The most important codes both in theory in practice are linear codes. Strangely enough, no tighter upper bounds are known for linear codes. This joint research project will study a strengthening of Delsarte’s classical linear program that distinguishes linear from general codes. Major open questions on algorithmic graph partitioning will also be investigated in this joint research project, as well as fundamental issues in dimension reduction, spectral graph theory, and the search for a meaningful model of random metric spaces. 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.