Notes of James Lee’s lecture nr 1

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 {S\subset V}, {h(S)=\frac{|\partial S|}{\min\{|S|,|\bar{S}|\}}}, {h(G)=\min \{h(S)\,;\, S\subset V\}}, {\alpha(G)=} idem with edge boundary {\partial S} replaced by vertex boundary {\partial_{V}S=\{u\notin S\,|\,d(v,S)=1\}}. A balanced separator is a subset {S} such that every component of {G\setminus S} has size {\leq 2n/3}.

Here is a classical theorem.

Theorem 2 (Lipton-Tarjan 1979) Every planar graph has a balanced separator of size {O(\sqrt{n})}.

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.

1.2. Spectrum

Definition 3 The discrete Laplacian is {L=D-A} where {D} is the (diagonal) degree matrix and {A} the adjacency matrix.

By definition, for every function {f} on vertices,

\displaystyle  \begin{array}{rcl}  \langle f,Lf \rangle=\sum_{x\sim y}(f(x)-f(y))^2 . \end{array}

Indeed, {L=\sum_{\mathrm{edges}} L_e} where {L_e} is the Laplacian of the one edge graph {e}.

{0} is an eigenvalue (the constant function {1} is an eigenvector), and the other ones are denoted by {0=\lambda_1 \leq \lambda_2 \leq\cdots\leq \lambda_n}. Note that {G} is connected iff {\lambda_2 >0} (use piecewise constant functions as test functions). Also, {\lambda_2} has a variational characterization,

\displaystyle  \begin{array}{rcl}  \lambda_k =\min\{\frac{\sum_{x\sim y}(f(x)-f(y))^2}{\sum_{x}f(x)^2}\,;\,f:V\rightarrow{\mathbb R},\,\langle 1,f \rangle=0\}. \end{array}

Pisier: beware, your notation {\sum_{x\sim y}=\sum_{e}} 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 {d_{max}} denote the maximum degree of vertices. Then

\displaystyle  \begin{array}{rcl}  \lambda_2 \geq \frac{h(G)^2}{2d_{max}}. \end{array}

This can be used to compute a rather sparse cut of {G}.

Spectral algorithm. Compute the second eigenvector, i.e. {f} such that {Lf=\lambda_2 f}. Sort {V} by increasing order of {f} values. This gives a family of cuts. Pick the cut that has minimum edge expansion {h}. We have an {\ell_1}-guarantee on {h(S)}, not {\ell_2}, whence the square in Cheeger’s bound.

Theorem 5 (Spielman and Teng 1996) For every planar graph {G} with maximum degree {d_{max}},

\displaystyle  \begin{array}{rcl}  \lambda_2 \leq \frac{8d_{max}}{n}. \end{array}

Thus there exists {S\subset V} such that {h(S)\leq O(\frac{d_{max}}{\sqrt{n}})}.

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 {G} into small pieces, with {O(|G|/\sqrt{n})} 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.

1.4. Computing {\lambda_2}

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 {2}-sphere.

This is a discrete analog of Riemann’s conformal mapping theorem.

Map {S^2} to {{\mathbb R}^3}. Define map {f:V\rightarrow{\mathbb R}^3} as centers of disks. Let {r_v} be the radius of the disk corresponding to {v}. Then

\displaystyle  \begin{array}{rcl}  \sum_{x\sim y}(f(x)-f(y))^2 &=&\sum_{x\sim y}(r_x +r_y)^2 \\ &\leq& 2d_{max}\sum_{v\in V}r_{v}^{2}\\ &\leq& 8d_{max}, \end{array}

since {area} of an {r}-disk is {\sim r_{v}^{2}}, disks are disjoint, sum of areas is {\leq area(S^2)}. On the other hand, the denominator is {n}. One can arrange that {\langle 1,f \rangle=0}. Indeed, moving the disk packing around using circle preserving mappings of the {2}-sphere turns the center of gravity into a continuous map of the {3}-ball to itself, which is the identity on the boundary. So Brouwer’s fixed point theorem applies. The conclusion is

\displaystyle  \begin{array}{rcl}  \lambda_2 \leq \frac{8d_{max}}{n}. \end{array}

Kelmer extend Spielman and Teng’s eigenvalue estimate to higher genus: {\lambda_2 \leq O(poly(d_{max})g/\sqrt{n}}. GHT prove that genus {\leq g} graphs have a separator of size {\leq((g+1)\sqrt{n})}. 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 {\mathcal{F}}, there exists a constant {C_{\mathcal{F}}} such that every {G\in\mathcal{F}} has a balanced separator of size {\leq C_{\mathcal{F}}\sqrt{n}}.

Gromov asks wether conformal mapping can help for this generalization.

Theorem 8 (Biswas, Lee and Rao 2008) If {G} does not have {K_{h}} as a minor, then

\displaystyle  \begin{array}{rcl}  \lambda_2 \leq O(\frac{h^6 d_{max}}{n}). \end{array}

Theorem 9 (Kelmer, Lee, Price and Teng) Under the same assumptions,

\displaystyle  \begin{array}{rcl}  \lambda_k \leq O(k\frac{h^6 d_{max}}{n}). \end{array}

Proof: Like in the local theory of Banach spaces, let us get rid of the orthogonality condition.

\displaystyle  \begin{array}{rcl}  \lambda_2 &=&\min_{f:V\rightarrow{\mathbb R}}\frac{\sum_{x\sim y}(f(x)-f(y))^2}{\frac{1}{2n}\sum_{x,\,y\in V}(f(x)-f(y))^2}\\ &=& 2n\min_{d}\frac{\sum_{x\sim y}d(x,y)^2}{\sum_{x,\,y\in V}d(x,y)^2} \end{array}

where we minimize over all pseudo-metrics embeddable in Hilbert space. According to Bourgain’s embedding theorem, up to loosing a factor of {(\log n)^2}, we can drop the {L^2}-embeddability restriction. We use metrics of the following form. Given weights {w:V\rightarrow{\mathbb R}_+}, minimise total weights of paths between points. Then

\displaystyle  \begin{array}{rcl}  \sum_{x\sim y}dist_{w}(x,y)^2\leq \sum_{x\sim y }(w(x)+w(y))^2\leq 2d_{max}\sum_{x\in V}w(x)^2 . \end{array}

Substitute this into previous inequality,

\displaystyle  \begin{array}{rcl}  \lambda_2 \leq 2 d_{max}\frac{\sum_{x\in V}w(x)^2}{\sum_{x,\,y\in V}dist_{w}(x,y)^2}. \end{array}

Now we optimize the choice of weight. Goal is an upper bound of {o(1/n^2)}. We would like to show that there exists {w:V\rightarrow{\mathbb R}_+} which minimizes the above quantity. This is not convex enough, so we use Cauchy-Schwarz once

\displaystyle  \begin{array}{rcl}  \frac{\sum_{x\in V}w(x)^2}{\sum_{x,\,y\in V}dist_{w}(x,y)^2} \leq n^2 \frac{\sum_{x\in V}w(x)^2}{(\sum_{x,\,y\in V}dist_{w}(x,y))^2} \end{array}

to make the constraints {\sum_{x,\,y\in V}dist_{w}(x,y)=1} linear. Pass to the dual problem.

Definition 10 Flows. Let {\mathcal{P}} be the set of paths in {G}, {\mathcal{P}_{x,y}} be the set of paths joinong {x} to {y}. A flow is a function {F:\mathcal{P}\rightarrow{\mathbb R}_+}. For every vertex {v}, the congestion is the amount of flow passing through {v},

\displaystyle  \begin{array}{rcl}  C_F (v)=\sum_{v\in p\in\mathcal{P}}F(p). \end{array}

The flow between {x} and {y} is

\displaystyle  \begin{array}{rcl}  F(x,y)=\sum_{p\in \mathcal{P}_{x,y}}F(p). \end{array}

LP Duality tells us that

\displaystyle  \begin{array}{rcl}  \min_{\{w\,;\,\sum_{x,\,y\in V}dist_{w}(x,y)=1\}}\sqrt{\sum_{x\in V}w(x)^2}=\max_{\{F\,;\,F(x,y)=1\,\forall x,\,y\in V\}} (\sum_{v\in V}C_F (v)^2)^{-1/2}. \end{array}

Next goal: For all flows {F} such that {F(x,y)=1} {\forall x,\,y\in V},

\displaystyle  \begin{array}{rcl}  \sqrt{\sum_{v\in V}C_F (v)^2} \geq C\,n^2 . \end{array}

Step 1. We can assume {F} takes integer values. Indeed, pick at random one path between {x} and {y} according to distribution {F} 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 {\leq \sum_{v\in V}C_F (v)^2}. The following theorem gives a lower bounds on the number of crossings.

Theorem 11 (Leighton, Ajtai-Newborn-Oswald-Szemeredi) For any graph with {|E|\geq 3|V|}, every drawing of {G} in the plane incurs {\geq \frac{|E|^3}{64|V|^2}} crossings.

This implies that the number of crossings when {K_n} is mapped to the plane is {\geq C\,n^4}. This follows from the probabilistic method and the classical fact that {K_5} 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. \Box

Example 1 On the square grid, the optimal weight is constant. On a binary tree, put weight {1} at the root and {0} elsewhere, this is nearly optimal.

Question: Is there a weight {w:V\rightarrow{\mathbb R}_+} such that

\displaystyle  \begin{array}{rcl}  \frac{\sum_{x\in V}w(x)^2}{\sum_{x,\,y\in V}dist_{w}(x,y)^2}\leq O(n^{-2}) \end{array}

and {(V,dist_w)} is doubling ?

If so, an argument of Nick Korevaar would provide upper bounds for all eignevalues, not just {\lambda_2}.

Next time, Robi will speak about embeddings into Banach spaces. In particular, he will explain how the {(\log n)^2} loss in the proof of the Theorem 9 can be avoided.

References

[ST1] Spielman, Daniel A.; Teng, Shang-Hua; Disk packings and planar separators. 12th Symp. Computational Geometry, 349–359 (1996).

[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.

About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Course and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s