Combinatorics in Cambridge

August 4th to 7th 2003


Lecture titles and abstracts

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

The talk will explain a new variational characterisation of the Fisher information of a marginal and its use in solving the problem of showing that the entropy of the normalised sums n-1/2(X1+...+Xn) of IID random varaibles increases with n.


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

Both the internet and the WWW are naturally described in terms of graphs. They share many properties, including power law degree distribution and small diameter, but differ in that while the WWW is oriented, the internet graph is unoriented to first approximation. In this talk, I review several mathematical models of random graphs describing these structures. For most of them, Béla has been instrumental in their formulation and/or the mathematical understanding of their properties. Given that time is short, I ask the audience for forgiveness if work not associated with Béla gets short-changed.


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))2n(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

(with Ronald J. Gould, Michael S. Jacobson and Linda Lesniak)

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

Many interesting extensions of Szemerédi's theorem have been proved using ergodic-theoretic techniques, including density versions of Gallai's theorem and the Hales-Jewett theorem, and the famous "polynomial Szemerédi theorem" of Bergelson and Leibman. However, for most of these extensions nothing whatsoever is known about bounds. In this talk I shall discuss the prospects for quantitative versions of some of these theorems.


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

I shall in the alotted span of twenty minutes Thus Baebler's theorem has the corollary that every 2s-edge-connected 3s-regular pseudograph has an s-factor while Belck has as a corollary of his theorem that every bridgeless 3s-regular pseudograph has an s-factor. The latter statement, also found as a corollary from a general theorem in a slightly later paper by the hungarian Tibor Gallai, can be given a direct proof from Petersen's theorem by applying an elementary splitting operation: in particular every vertex can be split in s vertices all of degree 3 such that the resulting graph is bridgeless (any 1-factor in the new graph obviously gives an s-factor in the old).


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>= ndelta or m/n>= ndelta 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(n3/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(n3/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 Ai, Bi of subsets of X, |Ai|=k, |Bi|=l satisfying the condition Ai is disjoint from Bj 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 Ai, Bi of subsets of X, |Ai|=|Bi|=k, with Ai disjoint from Bi 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 (fG,DG) such that fG is bounded above by s(n). We shall show that s(n)=(1+o(1))n2 for large n. Somewhat surprisingly, the lower bound s(n) >= (1+o(1))n2 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 De(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, De(G) is at least n2/4 - (1+o(1))n3/2(log n)1/2, whereas for some n-vertex graph G, De(G) exceeds n2/2 - n3/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 Z2 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 Z2 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

We review research related to uniquelly colorable and uniquelly extendable sparse graphs. On a proper level of generality this is related to projective graphs and this in turn implies hardness of H-coloring problem for most graphs H.


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 Cr2k be the 2k-uniform hypergraph obtained by letting P1,...,Pr be pairwise disjoint sets of size k and taking as edges all sets Pi u Pj with i not equal to j. This can be thought of as the `k-expansion' of the complete graph Kr: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain C32k can be obtained by partitioning V = V1 u V2 and taking as edges all sets of size 2k that intersect each of V1 and V2 in an odd number of elements. We prove a conjecture of Frankl, which states that every extremal C32k-free hypergraph has this structure.

Sidorenko has given an upper bound of (r-2)/(r-1) for the Turán density of Cr2k for any r, and a construction establishing a matching lower bound when r is of the form 2p+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 Cr4 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

This is a joint work with Béla Bollobás, improving an earlier result of B. Bollobás and A. Thomason.

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.