L3

In this talk we will first survey results which guarantee the existence of

spanning subgraphs in dense graphs. This will lead us to the proof of the

bandwidth-conjecture by Bollobas and Komlos, which states that any graph

with minimum degree at least $(1-1/r+\epsilon)n$ contains every r-chromatic graph

with bounded maximum degree and sublinear bandwidth as a spanning subgraph.

We will then move on to discuss the analogous question for a host graph that

is obtained by starting from a sparse random graph G(n,p) and deleting a

certain portion of the edges incident at every vertex.

This is joint work with J. Boettcher, Y. Kohayakawa and M. Schacht.

Given a graph we want to draw it in the plane; well we *want* to draw it in the plane, but sometimes we just can't. So we resort to various compromises. Sometimes we add crossings and try to minimize the crossings. Sometimes we add handles and try to minimize the number of handles. Sometimes we add crosscaps and try to minimize the number of crosscaps.

Sometimes we mix these parameters: add a given number of handles (or crosscaps) and try to minimize the number of crossings on that surface. What if we are willing to trade: say adding a handle to reduce the number of crossings? What can be said about the relative value of such a trade? Can we then add a second handle to get an even greater reduction in crossings? If so, why didn't we trade the second handle in the first place? What about a third handle?

The crossing sequence cr_1, cr_2, ... , cr_i, ... has terms the minimum number of crossings over all drawings of G on a sphere with i handles attached. The non-orientable crossing sequence is defined similarly. In this talk we discuss these crossing sequences.

By Dan Archdeacon, Paul Bonnington, Jozef Siran, and citing works of others.

This talk considers the problem of sampling an independent set uniformly at random from a bipartite graph (equivalently, the problem of approximately counting independent sets in a bipartite graph). I will start by discussing some natural Markov chain approaches to this problem, and show why these lead to slow convergence. It turns out that the problem is interesting in terms of computational complexity – in fact, it turns out to be equivalent to a large number of other problems, for example, approximating the partition function of the “ferromagnetic Ising model’’ (a 2-state particle model from statistical physics) in the presence of external fields (which are essentially vertex weights). These problems are all complete with respect to approximation-preserving reductions for a logically-defined complexity class, which means that if they can be approximated efficiently, so can the entire class. In recent work, we show some connections between this class of problems and the problem of approximating the partition function of the ``ferromagnetic Potts model’’ which is a generalisation of the Ising model—our result holds for q>2 spins. (This corresponds to the approximation problem for the Tutte polynomial in the upper quadrant

above the hyperbola q=2.) That result was presented in detail at a recent talk given by Mark Jerrum at Oxford’s one-day meeting in combinatorics. So I will just give a brief description (telling you what the Potts model is and what the result is) and then conclude with some more recently discovered connections to counting graph homomorphisms and approximating the cycle index polynomial.