The strange geometries of computer science
Goal: to link problems in computer science to more classical mathematics. I will list problems. In the course of it, we shall encounter recurrent themes.
1. Spectral geometry of graphs
Questions were raised by Spielman and Teng, Gromov.
1.1. Discrete isoperimetry
Definition 1 For , , , idem with edge boundary replaced by vertex boundary . A balanced separator is a subset such that every component of has size .
Here is a classical theorem.
Theorem 2 (Lipton-Tarjan 1979) Every planar graph has a balanced separator of size .
Motivation: when staring at data, one wants to single out a significant piece. One way to do it is to separate into smaller pieces in a manner guided by the graph structure, i.e. by cutting a small number of edges.
Definition 3 The discrete Laplacian is where is the (diagonal) degree matrix and the adjacency matrix.
By definition, for every function on vertices,
Indeed, where is the Laplacian of the one edge graph .
is an eigenvalue (the constant function is an eigenvector), and the other ones are denoted by . Note that is connected iff (use piecewise constant functions as test functions). Also, has a variational characterization,
Pisier: beware, your notation means sum over all edges (each edge appears only once).
1.3. Cheeger’s inequality
Born in Riemannian geometry, rediscovered in the world of graphs by Alon and Milman.
Theorem 4 Let denote the maximum degree of vertices. Then
This can be used to compute a rather sparse cut of .
Spectral algorithm. Compute the second eigenvector, i.e. such that . Sort by increasing order of values. This gives a family of cuts. Pick the cut that has minimum edge expansion . We have an -guarantee on , not , whence the square in Cheeger’s bound.
Theorem 5 (Spielman and Teng 1996) For every planar graph with maximum degree ,
Thus there exists such that .
Let us use this to prove the Lipton-Tarjan theorem, [ST2]. The difficulty is that the set provided by Spielman and Teng could be very small. If so, remove it and start again with the remainder of the graph. This gives a splitting of into small pieces, with pieces.
Moral: As soon as one can cut out a set with small expansion, we can repeat and win.
Remark 1 Lipton and Tarjan’s proof implies that the separator can be taken to be a simple closed curve. Spielman and Teng’s proof does not give info on the topology of separators.
Here is the proof of Spielman and Teng’s estimate, [ST1]. It imitates (independantly) an argument discovered in Riemannian geometry, by Joseph Hersch in 1970.
Theorem 6 (Koebe-Andreev) Every plane graph is the tangency graph of a collection of disjoint disks on the round -sphere.
This is a discrete analog of Riemann’s conformal mapping theorem.
Map to . Define map as centers of disks. Let be the radius of the disk corresponding to . Then
since of an -disk is , disks are disjoint, sum of areas is . On the other hand, the denominator is . One can arrange that . Indeed, moving the disk packing around using circle preserving mappings of the -sphere turns the center of gravity into a continuous map of the -ball to itself, which is the identity on the boundary. So Brouwer’s fixed point theorem applies. The conclusion is
Kelmer extend Spielman and Teng’s eigenvalue estimate to higher genus: . GHT prove that genus graphs have a separator of size . Gromov proves, using conformal mapping, something similar (I do not exactly remember).
1.5. Beyond planar: minor-free families
Theorem 7 (Alon, Seymour and Thomas) For every proper minor closed (see Linial’s first course, this morning) family of graphs , there exists a constant such that every has a balanced separator of size .
Gromov asks wether conformal mapping can help for this generalization.
Theorem 8 (Biswas, Lee and Rao 2008) If does not have as a minor, then
Proof: Like in the local theory of Banach spaces, let us get rid of the orthogonality condition.
where we minimize over all pseudo-metrics embeddable in Hilbert space. According to Bourgain’s embedding theorem, up to loosing a factor of , we can drop the -embeddability restriction. We use metrics of the following form. Given weights , minimise total weights of paths between points. Then
Substitute this into previous inequality,
Now we optimize the choice of weight. Goal is an upper bound of . We would like to show that there exists which minimizes the above quantity. This is not convex enough, so we use Cauchy-Schwarz once
to make the constraints linear. Pass to the dual problem.
Definition 10 Flows. Let be the set of paths in , be the set of paths joinong to . A flow is a function . For every vertex , the congestion is the amount of flow passing through ,
The flow between and is
LP Duality tells us that
Next goal: For all flows such that ,
Step 1. We can assume takes integer values. Indeed, pick at random one path between and according to distribution and give it all the flow….analysis shows that the sum of expected congestions does not change.
Step 2. If graph is planar, one can arrange so that all intersections of paths occur only at vertices. The number of crossings is . The following theorem gives a lower bounds on the number of crossings.
Theorem 11 (Leighton, Ajtai-Newborn-Oswald-Szemeredi) For any graph with , every drawing of in the plane incurs crossings.
This implies that the number of crossings when is mapped to the plane is . This follows from the probabilistic method and the classical fact that does not embed in the plane. A similar method applies to other minor-free families. This is due to Terry Tao (see his blog ), and has important applications in additive combinatorics.
Example 1 On the square grid, the optimal weight is constant. On a binary tree, put weight at the root and elsewhere, this is nearly optimal.
Question: Is there a weight such that
and is doubling ?
If so, an argument of Nick Korevaar would provide upper bounds for all eignevalues, not just .
Next time, Robi will speak about embeddings into Banach spaces. In particular, he will explain how the loss in the proof of the Theorem 9 can be avoided.
[ST2] Spielman, Daniel A.; Teng, Shang-Hua; Spectral partitioning works: planar graphs and finite element meshes. 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), 96–105, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996.