technical Perspective
Every Graph is
Essentially sparse
By Assaf Naor

Doi: 10.1145/2492007.2492028

the following paper by Batson, Spielman, Srivastava, and Teng surveys one of the most important recent intellectual achievements of theoretical computer science, demonstrating that every weighted graph is close to a sparse graph. As is often the case in key mathematical discoveries, a major part of the new contribution is a definition rather than just a theorem: here the authors describe an appropriate notion of “closeness” between graphs, called spectral similarity. This notion is fine enough so that graphs that are close to each other share certain properties which are crucial for a variety of algorithmic tasks, yet at the same time it can be argued that every graph is close to a graph which has few edges.

In the present (very general) context, an n-vertex weighted graph is nothing more than an n by n symmetric matrix G = ( gij) consisting of nonnegative real entries, that is, gij = gji ≥ 0 for every i, j ∈ { 1, . . . , n}. The underlying combinatorial graph induced by G corresponds to its support: simply draw an edge joining a pair of vertices i, j ∈ { 1, . . . , n} if and only if the entry gij is strictly positive. This is a general template for modeling pairwise interactions between n items, where the quantity gij measures the intensity of the interaction between the ith item and the jth item.

A new structural paradigm for graphs
would potentially impact numerous
areas of research, since clearly graphs
permeate computer science, math-
ematics, and the sciences in general.
Therefore, at this level of generality, can
it be possibly true that not all the impor-
tant structural results for weighted
graphs have already been discovered
decades ago? The authors demonstrate
through their remarkable work over the
past years that the answer to this ques-
tion is a resounding “yes.”
Consider a graph G as a template
for computing a certain “energy”: when-
ever one assigns a real value xi to each
vertex i, the graph outputs the quantity
. As one ranges over
all possible choices of real numbers
x1, . . . , xn, this quantity encodes a lot of
useful information about the structure
of the graph G. For example, by restrict-
ing to the special case when the xi are
either 0 or 1, one recovers the entire cut
structure of the graph, that is, for every
subset S of the vertices, this quantity
is nothing more than the total weight
of the edges joining S and its comple-
ment (the size of the boundary of S in
the graph G).

Assaf naor ( [e-mail]) is a professor of mathematics in the courant Institute of mathematical Sciences at new york university.