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 ( naor@cims.nyu.edu) is a professor of
mathematics in the courant Institute of mathematical
Sciences at new york university.