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
Take a random binary tree with n nodes, and embed it in in
a canonical way: that is, the root of the tree sits at the origin
, 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.
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.
Partly joint work with R.Pendavingh.
A graph is called an -lift of a graph if
and consists of a perfect matching between the sets
and for every edge in . (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:
This talk is based on papers written jointly with:
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.
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 to within a
constant factor for all valuesof . Of particular interest
is the case when 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.
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.
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
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.
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?
On the Shape of Binary Trees.
Some recent results in topological graph theory
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.
Lifts of Graphs
Alon Amit, Yonatan Bilu,
Yotam Drier, Jirka Matousek, and Eyal Rozenman.
Graph Algebras
The Evolution of the Mixing Time
New Code Bounds With Noncommutative Algebra and Semidefinite Programming
Modelling Errors and Recovery for Communication
Toward an Extremal Theory of Ordered Graphs
On the Complexity of Space Tilings