NSF-BSF: The Global Geometry of Graphs

图由节点的集合组成，其中一些节点对被认为是相互关联的，在这种情况下，它们被称为形成一条边。图的概念是非常通用和富有表现力的，因为它可以对任何对象集合之间任意复杂的两两交互进行建模。这使得图形在人类兴趣的所有方面都很重要（例如，从社会互动到科学、互联网搜索、工程和纯数学）。这也使得图的世界非常丰富和复杂。因此，开发能够提高人们理解和利用图形能力的方法是非常可取的。这个联合研究项目致力于进一步阐明图形的几何视角，这为他们的结构提供了深刻的和经常意想不到的见解。图通过定义其相关的距离概念，即从一个节点到达另一个节点所需的沿图边缘的最小跳数，在其节点上归纳出几何形状。将要研究的主要问题之一是图的局部结构，即它在每个节点附近的样子，如何对其全局属性的行为施加限制。例如，如果图不包含短周期（这种现象在许多感兴趣的情况下很常见），那么在每个节点附近可以看到树。然而，如果图是有限的，那么这些局部树就不能无限期地保持它们的树形生长，也就是说，它们最终必须以某种方式合并。值得注意的是，对于具有局部树状结构如何影响图的全局结构，目前所知甚少。这个联合研究项目将解决大量长期存在的关于当地树木在全球范围内的影响的谜团。关于图还有大量的局部-全局几何奥秘，例如关于码的基本问题（存在性和局限性），码是称为离散立方体的高维图的子集，其中所有非零的对向距离都很大。在这个联合研究项目中将研究的其他问题包括寻找有效划分图的算法，低维表示，将图距离表示为更简单的距离函数的叠加等。这个NSF-BSF联合项目将提供一个机会，加强美国和以色列研究人员之间的互动，他们一直在从不同的角度分别研究这些问题。它将解决这些方向上的具体问题，并且还将开发总体方法，通过它们诱导的全局几何透镜来理解图形。几何学可以为离散数学提供深刻的、常常是意想不到的见解，这一想法已经取得了巨大的成果。只要提到等周不等式是如何演变成复杂的概念就足够了，比如扩展图，它在从群论到理论计算机科学以及两者之间的许多其他主题的领域中发挥着重要作用。更具体地说，这个联合研究项目将研究图的全局几何。要研究的一个主要问题是有限图在多大程度上可以局部看起来像无限规则树。这样的有限图显然没有短周期，也就是说，它有很大的周长。而且它的直径应该小。周长能有多大？直径能有多小？一个图形能同时有大的周长和小的直径吗？在多大程度上，大周长图上的度规可以用切度规的叠加或欧几里得度规来近似？可以说，组合学中最重要的度量空间是离散立方体及其幂。理解这些图的独立数是一个经典的开放问题：二进制码的速率与距离问题。目前可用的最佳边界是近半个世纪前的。在理论和实践中最重要的码是线性码。奇怪的是，线性码没有更严格的上界。这个联合研究项目将研究加强Delsarte的经典线性程序，以区分线性与一般代码。在这个联合研究项目中，还将研究算法图划分的主要开放性问题，以及降维、谱图理论和寻找有意义的随机度量空间模型的基本问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.