Invited Speakers

Titles and Abstracts of Invited Talks

• Ron Aharoni   (Technion, Haifa)

Menger's Theorem for Infinite Graphs

We prove that Menger's theorem is valid for infinite graphs, in the following strong form: given two sets of vertices, A and B, in a possibly infinite digraph, there exist a set C of disjoint A-B paths, and a set S of vertices separating A from B, such that S consists of a choice of precisely one vertex from each path in C. This settles an old conjecture of Erdös.

Joint work with Eli Berger

• Mireille Bousquet-Mélou  (LaBRI, Bordeaux)

On the Shape of Binary Trees.

Take a random binary tree with n nodes, and embed it in Z2 in a canonical way: that is, the root of the tree sits at the origin $\left(0,0\right)$, and each right [left] son of a node lies one unit above and one unit to the right [left] of its father.

Using techniques from enumerative combinatorics and complex analysis, we shall study the typical shape of this canonical embedding for large binary trees of a given size. This includes questions like: how high, how wide is the embedding? What are the horizontal and vertical profiles of the tree? That is, how many nodes lie at a given abscissa or ordinate?

The results dealing with the horizontal profile are not new, while those dealing with the vertical profile are recent (math.CO/0501266). Their main motivation lies in the connection between embeddings of binary trees and the ISE (Integrated SuperBrownian Excursion). However, the emphasis will be put on the enumeration rather than on the probability during this talk.

• Hein van der Holst  (TU, Eindhoven)

Some recent results in topological graph theory

Each graph can be embedded in 3-space. The problem becomes more interesting if we put restrictions on the type of embedding. For example, a linkless embedding of a graph is one where each pair of vertex-disjoint circuits has linking number equal to zero. The class of all graphs that have a linkless embeddingisclosed undertaking minors. Robertson,Seymour, and Thomas gave the forbidden minors for this class of graphs. Open remained how to find a linkless embedding in polynomial time. In the talk we start with discussing an algorithm to find a linkless embedding.
Instead of embedding the graph in 3-space, we could also consider mapping properties of certain superstructures of the graph in 3-space, and, indeed,if this superstructure has not the right mapping properties in 3-space, see whether it has the right one in 4-space, etc. Recently, we introduced for a graph G a new graph parameter σ(G), which is defined as the smallest d such that superstructures of G have a zero intersection mapping in d-space. The nicest property of this graph parameter is its independence of the superstructure and thus depends on the graph only. For d = 2 and d =3, σ(G) <= d if and only if G is outerplanar and planar,respectively. The graphs G with σ(G) <= 4 are exactly those that have a linkless embedding. In the second part of the talk we will discuss this new graph parameter.

Partly joint work with R.Pendavingh.

• Nati Linial  (Hebrew University, Jerusalem)

Lifts of Graphs

A graph $H$ is called an $n$-lift of a graph $G$ if $V\left(H\right) = V\left(G\right) x \left[n\right]$ and $E\left(H\right)$ consists of a perfect matching between the sets $\left\{u\right\} x \left[n\right]$ and $\left\{v\right\} x \left[n\right]$ for every edge $uv$ in $E\left(G\right)$. (This is a special case of covering maps from topology). When the above perfect matchings are selected at random, we speak of random lifts. In this talk I will survey a number of papers that concerning lifts of graphs. Among the main results to be covered are:

• Several theorems pertaining to the typical properties of random lifts, and how they reflect the properties of $G$.
• An application of graph lifts to the construction of graphs with nearly optimal spectral gap.
• Connections of graph lifts to PCP theory.

This talk is based on papers written jointly with:
Alon Amit, Yonatan Bilu, Yotam Drier, Jirka Matousek, and Eyal Rozenman.

• László Lovász  (Eötvös University and Microsoft Research)

Graph Algebras

We consider graphs with k nodes labeled 1,...,k and any number of unlabeled nodes. We form the product of two such graphs by gluing together their labeled nodes. (In other words, we consider decomposing along a cutset of nodes as factorization.) By extending this to quantum graphs (formal linear combinations of such k-labeled graphs), we get a commutative algebra. Every graph parameter defines a bilinear form on this algebra and through this, a factor algebra.

This factor algebra is often finite dimensional and is very useful in studying the graph parameter. For example, it was proved by Freedman, Lovász and Schrijver that the parameter can be represented as the number of homomorphisms into a fixed weighted graph (e.g., the number of 4-colorings) if and only if this factor algebra is finite dimensional for every k, its dimension grows only exponentially with k, and the inner product is positive definite.

Further applications of this algebraic setup include a characterization of generalized quasirandom graphs by Vera Sós and the author.

The construction has an analogue using edge-cuts in place of node-cuts, which leads to non-commutative algebras and where many questions are still unsettled. There is a corresponding class of graph parameters, called edge-coloring models, which were characterized by Balazs Szegedy using these algebras, in a way analogous to (but much more involved than) the characterization of homomorphism functions mentioned above.

• Bruce Reed  (McGill, Montreal)

The Evolution of the Mixing Time

Random walks on markov chains are used in random algorithms for approximately counting. The time complexity of such algorithms depends crucially on the mixing time of the corresponding chain. We determine the mixing time of the random graph $G$n,p to within a constant factor for all valuesof $p>1+\epsilon$. Of particular interest is the case when $\epsilon$ approaches 0.

This is joint work with N. Fountoulakis.

The talk is aimed at a general audience and will be much more accessible than this abstract.

• Alexander Schrijver   (CWI, Amsterdam)

New Code Bounds With Noncommutative Algebra and Semidefinite Programming

The linear programming bound of Delsarte is a classical upper bound on the size of a code of given word length and given minimum distance. With semidefinite programming this bound can be strengthened, yielding several improved upper bounds for concrete pairs of word length and minimum distance. Basic ingredient is the block diagonalization of the Terwilliger algebra of the Hamming cube. In the talk we will explain the method.

Modelling Errors and Recovery for Communication

The theory of error-correction has had two divergent schools of thought, going back to the works of Shannon and Hamming. In the Shannon school, error is presumed to have been effected probabilistically. In the Hamming school, the error is modeled as effected by an all-powerful adversary. The two schools lead to drastically different limits. In the Shannon model, a binary channel with error-rate close to, but less than, 50% is useable for effective communication. In the Hamming model, a binary channel with an error-rate of more than 25% prohibits unique recovery of the message.

In this talk, we describe the notion of list-decoding, as a bridge between the Hamming and Shannon models. This model relaxes the notion of recovery to allow for a "list of candidates". We describe results in this model, and then show how these results can be applied to get unique recovery under "computational restrictions" on the channel's ability, a model initiated by R. Lipton in 1994.

Based on joint works with V. Guruswami, and with S. Micali, C. Peikert and D. Wilson

• Gábor Tardos  (Renyi, Budapest)

Toward an Extremal Theory of Ordered Graphs

Pattern avoidance raises very interesting extremal enumerative and structural problems in many different contexts from Turan-type extremal graph theory to Davenport-Schinzel theory. This survey talk concentrates to 0-1 matrices and (the closely related concepts of) ordered graphs. An ordered graph is simple graph together with a linear order on its vertices.

• Günter M. Ziegler  (TU Berlin)

On the Complexity of Space Tilings

In planar tilings the tiles can have at most six vertices on average, and every vertex is in at most six tiles on average - assuming that we restrict our attention to tilings that are nice enough, so that "on average" makes sense. Moreover, the maximum value of six cannot be achieved simultaneously for the two conditions.

In this lecture I want to discuss analogous problems for tilings of three-space: We will see tilings where the tiles do have many vertices, and tilings where all vertices lie in many tiles - but can both conditions can be achieved simultaneously?