Schedule, Fall 2003

Date Speaker Topic and Paper Reference

September 4 Brighten Algorithmic Mechanism Design

September 11 Kris The Lovasz local lemma holds a special place in my heart since it played a key role in one of the papers I talked about at my prelims. So that's what I will talk about this Thursday.
I will start by proving the Lovasz Local Lemma and then give two applications. The first will be to lower bound the van der Waerden function. (I will, of course, explain what the van der Waerden function is.)
The second will be an application to acyclic job shop scheduling, and I'll go most of the way towards showing it can be done within a constant factor of the obvious lowerbound.

September 18 Tim I will be talking about the Edmonds-Gallai Partition that characterizes maximum matchings (a nice exposition is in the Matching Theory book by Lovasz/Plummer).

September 25 James Basketball, the long code, and algebraic topology all in one talk...
Take a basketball, deflate it (i.e. remove all the air), crumple and fold it however you like, and then lie it flat on the ground (still crumpled). There are two points on the surface of the ball that were diametrically opposite before you took out the air and are now lying directly on top of each other. This is the Borsuk-Ulam theorem in two dimensions.
1933: Borsuk proves the "Ulam conjecture," yielding the Borsuk-Ulam theorem.
1978: In a stunning display of mathematical agility, Lovasz uses Borsuk-Ulam to prove a long-standing (1955) conjecture of Kneser about the chromatic number of a certain family of graphs.
2002: In another ingenious maneuver, Dinur, Regev, and Smyth use the unusual properties of the Kneser graph (e.g. it has both high chromatic number _and_ large independent sets) to give new hardness of approximation results in hypergraph coloring.
I will present one or more elementary proofs of the Borsuk-Ulam theorem, give some very elegant combinatorial applications (including Laci's result on the Kneser conjecture), and if time permits, discuss how a "stability" version of the Kneser conjecture helps in "list-decoding" a coloring in the DRS03 result.

October 2 David R. I'm speaking about "Rubber Bands, Convex Embeddings and Graph Connectivity" by N. Linial, L. Lovasz and A. Wigderson.
In this paper, the authors show that a graph is k-connected if and only if, specifying any k vertices of G, the vertices of G can be represented by points of R^{k-1} so that no k are on a hyperplane and each vertex is in the convex hull of its neighbors (except the k specified vertices). This embedding can be found by fixing the position of the specified nodes, allowing the edges of the graph to behave like rubber bands and letting its vertices settle into equilibrium. This embedding is non-degenerate exactly when the graph is k connected. This is a generalization of Tutte's theorem that every 3-connected planar graph has a convex planar embedding.
I will discuss this result and sketch how the authors use it to give a fast randomized algorithm for connectivity testing.

October 9 (Eve of FOCS) NO MEETING !

October 16 Chris NO MEETING ! (due to FOCS jetlagging)

October 23 Alex NO MEETING ! (more FOCS jetlagging)

October 30 Mani Cut-and-paste operations for tree-enthusiasts
We are given two trees and asked to measure the distance between them. The distance is the minimum number of cut-and-paste operations to transform one tree to the other. I will talk about three distance metrics: NNI (Nearest Neighbor Interchange), SPR (Subtree Prune and Regraft), and TBR (Tree Bisect and Reconnect).
I will be presenting from the paper: "Subtree Transfer Operations and their Induced Metrics on Evolutionary Trees", B. Allen, M. Steel. The paper has some nice combinatorics since it talks about unrooted binary trees, which are even nicer structures than general trees. I will also remind you of the proof of Cayley's theorem (number of different trees on n vertices) along the way.

November 6 David M. Spectral Graph Theory and Spectral Partitioning
What happens if you diagonalize the adjacency matrix of a graph? The study of this question is the province of "spectral graph theory," and it makes interesting, beautiful, and useful connections between linear algebra and graph theory.
I will survey some basic results in spectral graph theory and discuss the relationship between the spectrum of a graph, expansion properties, and random walks on a graph. Then we'll turn our attention to algorithms for "spectral partitioning."
First introduced by Fiedler, these algorithms use the second smallest eigenvector of the Laplacian of a graph to find good graph separators. I'll give some applications of spectral partitioning and sketch a result due to Spielman and Teng that shows "spectral partitioning works" for the case of planar graphs.
References:
Spectral Partitioning Works" (Spielman and Teng)
Course on Expanders and their Applications (Linial and Wigderson)
Course on Applied Extremal Combinatorics (Spielman)
Some Applications of Laplace Eigenvalues of Graphs (Mohar)

November 13 Andrej I will talk about the phenomenon of "Global Information from Local Observation" (Benjamini, Lovasz 2002.) Here is a telling quote from the work itself:
"At least since Polya's observation (1921) that 'a drank (sic) man will return home while a drank bird might lose its way forever,' it is known that geometric properties of the underlying space can manifest themselves in the behavior of a random process taking place on the space."

November 20 Satish I will try to describe Umesh, Sanjeev, and my recent result on sparsest cut. (i.e., An $O(\sqrt{\log n)$ approximation for sparsest cut using semidefinite programming...)

November 28 (Thanksgiving) NO MEETING !

December 4 Kevin I'm going to present a well-known result from Alon, Karp, Peleg and West (1993), A graph-theoretic game and its application to the k-server problem. This paper considers the problem of embedding an arbitrary n-point graph metric into one of its spanning tree so as to minimize the average distortion, over all edges in the graph. The AKPW paper gives an upper bound of exp(O(\sqrt(log n log log n)) but the only known lower bound is log n. A long-standing (10 years) open problem is to close this gap. Which shall be eschewed - the upper bound or lower bound?

December 11 (Finals Week)

Date	Speaker	Topic and Paper Reference
September 4	Brighten	Algorithmic Mechanism Design
September 11	Kris	The Lovasz local lemma holds a special place in my heart since it played a key role in one of the papers I talked about at my prelims. So that's what I will talk about this Thursday. I will start by proving the Lovasz Local Lemma and then give two applications. The first will be to lower bound the van der Waerden function. (I will, of course, explain what the van der Waerden function is.) The second will be an application to acyclic job shop scheduling, and I'll go most of the way towards showing it can be done within a constant factor of the obvious lowerbound.
September 18	Tim	I will be talking about the Edmonds-Gallai Partition that characterizes maximum matchings (a nice exposition is in the Matching Theory book by Lovasz/Plummer).
September 25	James	Basketball, the long code, and algebraic topology all in one talk... Take a basketball, deflate it (i.e. remove all the air), crumple and fold it however you like, and then lie it flat on the ground (still crumpled). There are two points on the surface of the ball that were diametrically opposite before you took out the air and are now lying directly on top of each other. This is the Borsuk-Ulam theorem in two dimensions. 1933: Borsuk proves the "Ulam conjecture," yielding the Borsuk-Ulam theorem. 1978: In a stunning display of mathematical agility, Lovasz uses Borsuk-Ulam to prove a long-standing (1955) conjecture of Kneser about the chromatic number of a certain family of graphs. 2002: In another ingenious maneuver, Dinur, Regev, and Smyth use the unusual properties of the Kneser graph (e.g. it has both high chromatic number _and_ large independent sets) to give new hardness of approximation results in hypergraph coloring. I will present one or more elementary proofs of the Borsuk-Ulam theorem, give some very elegant combinatorial applications (including Laci's result on the Kneser conjecture), and if time permits, discuss how a "stability" version of the Kneser conjecture helps in "list-decoding" a coloring in the DRS03 result.
October 2	David R.	I'm speaking about "Rubber Bands, Convex Embeddings and Graph Connectivity" by N. Linial, L. Lovasz and A. Wigderson. In this paper, the authors show that a graph is k-connected if and only if, specifying any k vertices of G, the vertices of G can be represented by points of R^{k-1} so that no k are on a hyperplane and each vertex is in the convex hull of its neighbors (except the k specified vertices). This embedding can be found by fixing the position of the specified nodes, allowing the edges of the graph to behave like rubber bands and letting its vertices settle into equilibrium. This embedding is non-degenerate exactly when the graph is k connected. This is a generalization of Tutte's theorem that every 3-connected planar graph has a convex planar embedding. I will discuss this result and sketch how the authors use it to give a fast randomized algorithm for connectivity testing.
October 9	(Eve of FOCS)	NO MEETING !
October 16	Chris	NO MEETING ! (due to FOCS jetlagging)
October 23	Alex	NO MEETING ! (more FOCS jetlagging)
October 30	Mani	Cut-and-paste operations for tree-enthusiasts We are given two trees and asked to measure the distance between them. The distance is the minimum number of cut-and-paste operations to transform one tree to the other. I will talk about three distance metrics: NNI (Nearest Neighbor Interchange), SPR (Subtree Prune and Regraft), and TBR (Tree Bisect and Reconnect). I will be presenting from the paper: "Subtree Transfer Operations and their Induced Metrics on Evolutionary Trees", B. Allen, M. Steel. The paper has some nice combinatorics since it talks about unrooted binary trees, which are even nicer structures than general trees. I will also remind you of the proof of Cayley's theorem (number of different trees on n vertices) along the way.
November 6	David M.	Spectral Graph Theory and Spectral Partitioning What happens if you diagonalize the adjacency matrix of a graph? The study of this question is the province of "spectral graph theory," and it makes interesting, beautiful, and useful connections between linear algebra and graph theory. I will survey some basic results in spectral graph theory and discuss the relationship between the spectrum of a graph, expansion properties, and random walks on a graph. Then we'll turn our attention to algorithms for "spectral partitioning." First introduced by Fiedler, these algorithms use the second smallest eigenvector of the Laplacian of a graph to find good graph separators. I'll give some applications of spectral partitioning and sketch a result due to Spielman and Teng that shows "spectral partitioning works" for the case of planar graphs. References: Spectral Partitioning Works" (Spielman and Teng) Course on Expanders and their Applications (Linial and Wigderson) Course on Applied Extremal Combinatorics (Spielman) Some Applications of Laplace Eigenvalues of Graphs (Mohar)
November 13	Andrej	I will talk about the phenomenon of "Global Information from Local Observation" (Benjamini, Lovasz 2002.) Here is a telling quote from the work itself: "At least since Polya's observation (1921) that 'a drank (sic) man will return home while a drank bird might lose its way forever,' it is known that geometric properties of the underlying space can manifest themselves in the behavior of a random process taking place on the space."
November 20	Satish	I will try to describe Umesh, Sanjeev, and my recent result on sparsest cut. (i.e., An $O(\sqrt{\log n)$ approximation for sparsest cut using semidefinite programming...)
November 28	(Thanksgiving)	NO MEETING !
December 4	Kevin	I'm going to present a well-known result from Alon, Karp, Peleg and West (1993), A graph-theoretic game and its application to the k-server problem. This paper considers the problem of embedding an arbitrary n-point graph metric into one of its spanning tree so as to minimize the average distortion, over all edges in the graph. The AKPW paper gives an upper bound of exp(O(\sqrt(log n log log n)) but the only known lower bound is log n. A long-standing (10 years) open problem is to close this gap. Which shall be eschewed - the upper bound or lower bound?
December 11	(Finals Week)