| Noga Alon |
Derandomization and Property Testing The probabilistic method is a powerful technique for proving the existence of combinatorial structures or substructures of given ones, with prescribed properties. The method often leads to efficient randomized algorithms for the corresponding algorithmic problems. After a brief discussion of the basic method and its algorithmic aspects, I will discuss various techniques for converting randomized algorithms into deterministic ones. I will also discuss some recent results about property testing, which deals with the design of highly efficient randomized algorithms that test if a given combinatorial structure satisfies a given property or is very far from satisfying it. |
|
| András Frank |
Constructive Characterizations of Connectivity Properties An easy theorem from graph theory asserts that an undirected graph is 2-edge-connected if and only if it may be obtained from a node by applying the following two operations: (i) add a new edge connecting existing nodes, (ii) subdivide an existing edge by a new node. This is a prototype of results the title refers to. In this lecture we overview some well-known older results such as Tutte's characterization of 3-connected graphs, exhibit other not so well-known characterizations (e.g. Cheriyan and Maheshwari's ear-decomposition of 3-connected graphs, Mader's theorem on generating all k-edge-connected directed graphs), and derive some recent results of the area (e.g.: an undirected graph contains two edge-disjoint spanning trees after deleting any of its edges if and only if it can be obtained from a node by applying the following to operations: (i) add an edge connecting two existing nodes, (ii) subdivide an existing edge by a new node and connect this node to an existing node). Several examples will be mentioned to demonstrate the usefullness of such characterizations. We will conclude some challenging open questions. |
|
| Michel Goemans |
Multicommodity Flows and Cuts, and Low Distortion Embeddings of Metrics
[tentative] I will describe several results concerning the embedding of certain types of metric spaces into others, either isometrically or with (low) distortion. We will start with classical results, such as the isometric embedding of $l_2$ into $l_1$. We will cover Bourgain's embedding of any metric into $l_1$ or $l_2$ with logarithmic distortion, and also discuss the embedding of negative type metrics. This will lead us to semidefinite programming (and results of Linial et al.), expander graphs, and maximum volume ellipsoids. To motivate the results, we will show the connection between embeddings of metric spaces and multicommodity flows/cuts (or the sparsest cut problem or expansion properties). |
|
| Monique Laurent |
I will present some results that are at the interface between
linear algebra/combinatorial matrix theory and graph theory/
combinatorial optimization. The following "matrix completion problem" will be central to the series of lectures: Given a partial rational matrix, decide if it can be completed to a positive semidefinite matrix and if yes find such a completion. This problem is an instance of semidefinite programming and its complexity is not known. The following topics will be considered. 1. Study classes of graphs (corresponding to the specified entries in the partial matrix) for which the completion problem can be solved in polynomial time. E.g., chordal graphs, graphs with fixed minimum fill-in, etc. 2. Find necessary conditions to be satisfied by the specified entries of a completable partial matrix: e.g., conditions based on cut and metric polyhedra, and characterize the graphs for which the conditions are sufficient. 3. Study the cone of psd matrices having a given sparsity pattern and a related graph parameter - the order of a graph. Topics 2 and 3 involve results giving characterizations for some classes of graphs (eg, graphs of order 2, graphs with no induced wheels, ..) with graph theoretic and linear algebraic flavours. 4. Link with other completion problems, e.g., for distance matrices or min/max rank completions. 5. (If time allows) Results about completely positive matrices and doubly nonnegative matrices; in particular, when are the two notions equivalent? |
|
| Alexander Schrijver |
The topic of my course will be polyhedral and polynomial-time
methods in combinatorial optimization.
I will talk on submodular function minimization, bipartite
edge-coloring, and matching forests.
|