The lecture arrangements being somewhat informal, we only very recently requested this information from the speakers, and many did not yet have chance to reply. This page will be updated as information becomes available.

Wed 09.00 **Noga Alon**
(Tel Aviv)
*Maxcut in H-free graphs*

One of the basic results in Extremal Graph Theory is the fact that every simple graph G with m edges contains a cut (that is, a spanning bipartite subgraph) with at least m/2 edges. This can be strengthened, especially for graphs G which contain no copy of a fixed graph H. I will discuss some of these stronger results (and conjectures), focusing on a recent joint work with Béla Bollobás, Michael Krivelevich and Benny Sudakov.

Thu 09.00 **Keith Ball** (UCL)
*Entropy growth for sums of independent random variables*

Mon 10.00 **Christian Borgs**
(Microsoft Research)
*Graph Theoretic Models of the Internet and the WWW*

Mon 16.30 **Graham Brightwell** (LSE)
*How many graphs are unions of k-cliques?*

This is joint work with Béla Bollobás.

Several interesting combinatorial problems arise by asking how many structures can be built out of particular (large) substructures. For instance, one can ask how many subsets of the n-cube can be made up as unions of k-subcubes.

Here we study what seems to be the most natural problem of this type for
graphs, namely building graphs out of reasonably large cliques.
Let F[n;k] be the number of n-vertex graphs that can be written as the
edge-union of k-vertex cliques. If k is small enough that,
almost surely, every edge of a random graph is in a k-clique,
then of course F[n;k] = (1-o(1))2^{n(n-1)/2}. We show that, only
slightly above this threshold value of k, the value F[n;k] drops off
sharply.

We also obtain reasonably tight estimates for F[n;k] in the cases (i) k=n-o(n) and (ii) k=o(n) but log n = o(k). We leave open several potentially interesting cases, and raise some other questions of a similar nature.

Mon 09.30 **Jennifer Chayes**
(Microsoft Research)
*Random Graph Scaling for General Finite Graphs*

One of the seminal results of graph theory is the finite-size scaling of the random graph model, in particular the size of the dominant component and the width of the critical window. In this work, we formulate conditions under which transitive finite graphs exhibit analogous scaling, and verify those conditions for many graphs of interest including the n-cube and the Hamming cube. Our techniques are a combination of methods from mathematical physics, in particular the lace expansion, and methods from combinatorics. The key ingredient is the tight relationship between critical exponents and finite-size scaling. This talk represents collaborative work with C. Borgs, R. van der Hofstad, G. Slade, and J. Spencer.

Tue 09.30 **Reinhard Diestel**
(Hamburg)
*Infinite cycles*

Finite graph homology may be trivial, but for infinite graphs things
become interesting. We present an approach that builds the cycle space
C of a graph not on its finite cycles but on its topological
*circles*, the homeomorphic images of the unit circle in the
space formed by the graph together with its ends. This approach
permits the extension both of basic facts about C and deeper
results such as Tutte's generating theorem or MacLanes planarity
criterion, whose infinite versions would otherwise fail.

Wed 10.00 **Edward Dobson**
(Mississippi State)
*On groups of odd prime-power degree that contain a full cycle*

Burnside has proven that a transitive group of prime degree is either doubly-transitive or contains a normal Sylow p-subgroup. We will discuss applications of this result to the study of vertex-transitive graphs. Additionally, we will discuss recent extensions of Burnside's result, and why these extensions of are interest to combinatorialists.

Mon 14.00 **Ralph Faudree**
(Memphis)
*Generalizing pancyclic and k-ordered graphs*

A graph G of order n is (k, m)-*pancyclic* if for any set of k
vertices of G and any integer r between m and n,
there is a cycle of length r containing the k vertices.
Minimum degree conditions and minimum sum of degree conditions of
nonadjacent vertices that imply a graph is (k,m)-pancylic are
proved. If the additional property that the k vertices must
appear on the cycle in a specified order is required, then the
graph is said to be (k, m)-*pancyclic ordered*. Minimum
degree conditions and minimum sum of degree conditions for
nonadjacent vertices that imply a graph is (k,m)-pancylic
ordered are also proved. Examples showing that these constraints
are best possible are provided.

Wed 14.30 **Alan Frieze**
(Carnegie Mellon)
*On packing Hamilton Cycles in epsilon-regular Graphs*

Co-author Michael Krivelevich

A graph G=(V,E) on n vertices is (alpha,epsilon)-regular if its minimal degree is at least alpha*n, and for every pair of disjoint subsets S,T of V of cardinalities at least epsilon*n, the number of edges e(S,T) between S and T is such that e(S,T)/(|S|-|T|) differs from alpha by at most epsilon.

We prove that if alpha >> epsilon>0 are constants, then every (alpha,epsilon)-regular graph on n vertices contains a family of (alpha/2-O(epsilon))*n edge-disjoint Hamilton cycles. As a consequence we derive that for every p, with high probability in the random graph G(n,p), almost all edges can be packed into edge-disjoint Hamilton cycles. A similar result is proven for the directed case. An application is shown in the context of Maker-Breaker games.

Thu 12.00 **Timothy Gowers**
(Cambridge)
*Extensions of Szemerédi's theorem*

Mon 15.00 **Roland Häggkvist**
(Umea)
*Factors galore: Extending theorems
by Petersen, Baebler, Belck and Gallai*

- follow the lead by the danish mathematician Julius Petersen 1891 who among other things showed that every bridgeless cubic graph has a 2-factor avoiding any given edge and implicitly conjectured that every bridgeless regular graph contains a 2-factor,
- mention and ask for biographical data on the german (swiss?) mathematician Fridolin Baebler who in 1938, nine years prior to Tutte's publicaton of his well known 1-factor criterium, not only published a proof of Petersen's conjecture but also indeed the stronger statement that every r-regular multigraph without an r-factor, r even, has a separating set of at most r-1 edges,
- mention and likewise ask for data on the german
Hans Boris Belck who in 1950 published his one and only mathematical paper, a
34 page opus in Crelle's Journal in which he not only gave the first general
k-factor criterium including the first purely graph theoretical proof of
Tutte's 1-factor theorem but also settled the following question completely:
*For what value of l=lr,k) is an l-edge-connected r-regular graph pseudograph of even order if k is odd guaranteed to have a k-factor.*

Mon 14.30 **Penny Haxell**
(Waterloo)
*to be announced*

Mon 17.00 **Svante Janson**
(Uppsala)
*The first eigenvalue of random graphs*

We extend a result by Füredi and Komlos and show that the first
eigenvalue of a random graph is asymptotically normal,
both for G(n,p) and G(n,m), provided np>= n^{delta} or
m/n>= n^{delta} for some delta>0.

The formula for asymptotic mean involves a mysterious power series.

Thu 10.00 **Jeffrey Kahn**
(Rutgers)
*On the number of Hamiltonian cycles in a tournament*

Let P(n) and C(n) denote, respectively, the maximum possible numbers of Hamiltonian paths and Hamiltonian cycles in a tournament on n vertices.

The study of P(n) was suggested by
Szele (1943), who showed in an early application of
probabilistic method that
P(n) >= n!2^{-n+1}, and conjectured
that lim (P(n)/ n! )^{1/n}= 1/2.
This was proved by Alon (1990), who showed
that the conjecture follows from a suitable bound on C(n),
and observed that a (more than) adequate bound,
C(n) < O(n^{3/2}(n-1)!2^{-n}),
follows from Brégman's Theorem (1973, a.k.a. the Minc Conjecture)
on permanents of {0,1}-matrices.
Here we improve this to
C(n) < O(n^{3/2-x}(n-1)!2^{-n}),
with x = 0.2507.., following an entropy approach of
J. Radhakrishnan, and wonder about the true behavior and
some related questions.

This is joint with Ehud Friedgut.

Tue 10.00 **Gyula Katona**
(Rényi Institute)
*Pairs of disjoint sets*

Let X be a finite set of n elements. Two, only formally similar topics
will be considered. The first part will be mostly historic remarks on a
classical result of Bollobás determining the maximum number of pairs
A_{i}, B_{i} of subsets of X, |A_{i}|=k,
|B_{i}|=l satisfying the condition A_{i} is disjoint from
B_{j} iff i=j. The second one is a new, joint result of
Bollobás, Leader and the speaker. It asymptotically determines the
maximum number of unordered pairs A_{i}, B_{i} of subsets
of X, |A_{i}|=|B_{i}|=k, with A_{i} disjoint from
B_{i} where the distance of any two pairs is at least d. The
distance is the smaller one of the two possible pairwise symmetric
differences, k,d are fixed, n is large.

Wed 16.30 **Jeong Han Kim**
(Microsoft Research)
*to be announced*

Wed 11.30 **Yoshiharu Kohayakawa**
(São Paolo)
*Distance graphs on the integers*

In this talk, we consider certain extremal problems concerning representations
of graphs as *distance graphs* on the integers. Given a graph
G=(V,E), we wish to find an injective function
f:V->N and a subset D of N so that uv is an edge if and only if
|f(u)-f(v)| is in D.

Let s(n) be the smallest number such that any graph G on n vertices admits
a representation (f_{G},D_{G}) such that
f_{G} is bounded above by s(n). We shall show
that s(n)=(1+o(1))n^{2} for large n. Somewhat
surprisingly, the lower bound s(n) >= (1+o(1))n^{2} follows even if we
restrict our attention to r-regular graphs with any r=r(n) >> log n.

Given a graph G=(V,E), let D_{e}(G) be the smallest possible
cardinality of a set D for which there is some f:V->N so that (f,D)
represents G. We shall show that, for almost all n-vertex graphs G,
D_{e}(G) is at least n^{2}/4 -
(1+o(1))n^{3/2}(log n)^{1/2},
whereas for some n-vertex graph G,
D_{e}(G) exceeds n^{2}/2 -
n^{3/2}(log n)^{1/2+o(1)}.
Further extremal problems of similar nature will be mentioned.

This is joint work with M. Ferrara and V. Rödl (Atlanta).

Wed 15.00 **Alexandr Kostochka**
(Illinois)
*On packing of sparse graphs*

This is a joint work with B. Bollobás and K. Nakprasit. Directions of studying packing of graphs were defined about 25 years ago by fundamental papers of Bollobás and Eldridge and Sauer and Spencer. In this talk, we discuss three conjectures of Bollobás and Eldridge. We prove a partial case of the main Bollobás-Eldridge Conjecture. Apart from this, we extend a conjecture and disprove another conjecture from their paper.

Mon 11.30 **Nati Linial**
(Jerusalem)
*Random Simplicial Complexes - Connectivity In Two Dimensions*

(Joint work with Roy Meshulam)

It is unnecessary to remind this audience of the tremendous success that
random graphs have had in all parts of discrete mathematics. One possible
view of graphs is that they are one-dimensional simplicial complexes.
Can we develop, then, a similarly rich and powerful theory of
higher-dimensional simplicial complexes? In this talk I describe a first
small step in this direction. There are several natural higher-dimensional
analogues of graph connectivity: vanishing of the Z_{2} homology,
of the Z-homology, and simple connectedness (these conditions are progressively
stronger in this order). In this talk I will describe a proof of the
following theorem: in a random 2-dimensional simplicial complex, the
threshold for the vanishing of the Z_{2} homology occurs at
(hyper)edge probability 2 log n / n.

If time permits, I will say a few words on the conjectured analogous statements for the other two notions of connectivity.

Thu 14.00 **Laszló Lovász**
(Microsoft Research)
*Discrete localization*

If we have a real valued function on a finite set whose values sum to a positive number, then there is an element where its value is positive. This trivial fact is an important step in many proofs, in particular in most applications of the Probabilistic Method.

Now suppose we have two functions defined on the same finite set whose values sum to positive numbers. Can we find a ``small'' subset (perhaps with weights) of the domain over which both functions sum to positive values? Lovász and Simonovits proved such a "localization lemma" in the continuous setting, which has several applications to geometric inequalities.

In the discrete setting, we prove a result for the case when the domain of the functions is a boolean algebra, and ``small'' means a 4-element subalgebra. Applications include extensions of the Four Function Theorem.

This is joint work with Mike Saks.

Mon 12.00 **Tomasz Luczak**
(Poznan)
*Protean graphs*

In the talk we shall propose a new probabilistic model of web graphs and describe some of its basic properties.

It is a joint work with Pawel Pralat.

Tue 09.00 **Vitali Milman**
(Tel Aviv)
*On some very recent results in Asymptotic Geometric Analysis*

Wed 09.30 **Jaroslav Nesetril**
(Prague)
*Unique extensions, projectivity and complexity of colorings*

Thu 11.00 **Boris Pittel**
(Ohio State)
*On dimensions of a random solid diagram*

A solid diagram of volume n is a packing of n unit cubes into a corner so that the heights of vertical stacks of cubes do not increase in either of two horizontal directions away from the corner. An asymptotic distribution of the dimensions---heights, depths, and widths---of the diagram chosen uniformly at random among all such diagrams is studied. For each k, the planar base of k tallest stacks ("footprint") is shown to be Plancherel distributed. (Plancherel's measure of a planar diagram is proportional to the square of the number of linear extensions of the standard partial order on the diagram.)

Tue 11.00 **Hans-Jürgen Prömel
** (Humboldt)
*to be announced*

Thu 11.30 **Pierre Rosenstiehl**
(EHESS)
*Balanced bicoloration, Homomorphism and Graph Dimension*

(joint work with Patrice Ossona de Mendez)

The dimension of a graph, that is the dimension of its incidence poset, became a major bridge between posets and graphs. Although allowing a nice characterization of planarity, this dimension badly behaves with respect to homomorphisms.

We introduce the universal dimension of a graph G as the maximum dimension of a graph having a homomorphism to G. The universal dimension, which is clearly homomorphism monotone, is related to the existence of some balanced bicoloration of the vertices with respect to some realizer.

Non trivial new results related to the original graph dimension are subsequently deduced from our study of universal dimension, including chromatic and extremal properties.

Tue 11.30 **Alex Scott** (UCL)
*to be announced*

Mon 11.00 **Miklós Simonovits**
(Rényi Institute)
*How many?*

The aim of this birthday-survey talk is to speak about some results of Béla Bollobás. The selection principle is to speak about results which I also worked on. I shall focus basically on four topics: (1) The Erdös-Pósa Theorem. (2) The qualitative version of the Erdös-Stone theorem, (the Bollobás-Erdös-Simonovits, the Chvatál-Szemerédi theorem, and its surrounding). (3) Counting forbidden subgraphs in a supersaturated subgraph, (Bollobás's results, the Lovász-Simonovits theorems). (4) The Balogh-Bollobás-Simonovits theorem and its surrounding.

Wed 11.00 **Vera T. Sós**
(Rényi Institute)
*to be announced*

Thu 09.30 **Benjamin Sudakov**
(Princeton)
*Surprising behavior of some hypergraph Turán numbers*

Let C_{r}^{2k} be the 2k-uniform hypergraph obtained by letting
P_{1},...,P_{r} be pairwise disjoint sets of size k and
taking as edges all sets P_{i} u P_{j} with i not equal to j.
This can be thought of as the `k-expansion' of the complete graph
K_{r}: each vertex has been replaced with a set of size k. An
example of a hypergraph with vertex set V that does not contain
C_{3}^{2k} can be obtained by partitioning V =
V_{1} u V_{2} and taking as edges all sets of size 2k
that intersect each of V_{1} and V_{2} in an odd number of
elements. We prove a conjecture of Frankl, which states that every extremal
C_{3}^{2k}-free hypergraph has this structure.

Sidorenko has given an upper bound of (r-2)/(r-1) for the Turán
density of C_{r}^{2k} for any r, and a construction
establishing a matching lower bound when r is of the form 2^{p}+1.
Surprisingly, when r is not of this form, we show that corresponding
constructions do not exist and improve the upper bound on the Turán
density of C_{r}^{4} to (r-2)/(r-1) - c(r), where c(r) is a
constant depending only on r.

The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realization draw on extremal graph theory, linear algebra, the Kruskal-Katona theorem and properties of Krawtchouck polynomials.

This is joint work with Peter Keevash.

Wed 14.00 **Endre Szemerédi**
(Rutgers and Rényi Institute)
*Girth of
sparse graphs*

For n>2 and k at most n(n-3)/2, let g(n,k) denote the maximal girth of a simple graph with n vertices and n+k edges. Our main result asserts that for n>3 and k>1, g(n,k) is at most 2(n+k)(log k + loglog k + 4)/3k. We also discuss related conjectures.

Tue 12.00 **H.N.V. Temperley**
(Somerset)
*New results on the Potts, Onsager-Ising and related models*

A report will be given on recent progress regarding a general treatment for a large class of problems, including the Potts model, the Onsager-Ising model, and problems of enumeration of graphs on lattices, such as the dimer problem.

Wed 17.00 **Carsten Thomassen**
(TU Denmark)
*On Hajós' conjecture*

Hajós' conjecture says that every k-chromatic graph contains a subdivision of the complete graph on k vertices. The conjecture is open for k=5,6. I shall discuss some consequences of the conjecture to Ramsey theory, perfect graphs, and the maximum cut problem.

Wed 12.00 **Dominic Welsh**
(Oxford)
*Combinatorial and complexity questions arising from a problem
in quantum computation*

Recent work with M. Bordewich, M.Freedman and L.Lovász on approximate counting is motivated by the relationship between quantum computation and particular evaluations of the Jones polynomial of a knot.In this talk I shall discuss some combinatorial/complexity questions about the chromatic and Tutte polynomial of a graph which have arisen from this.

Thu 14.30 **Peter Winkler**
(Bell Labs)
*Some Puzzles Even Béla Can't Solve*

An "unsolved puzzle" is, in the speaker's mind, an open mathematical conjecture which is simple enough for a layperson to understand; ideally it should be elegant but not too important. The more embarrassing it is that the answer is unknown, the better.

The audience will be provided with (or reminded of) a dozen or more of these, and asked to contribute their own favorites to the collection.