NSF-BSF: The Global Geometry of Graphs

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

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.