Schedule

Given a graph H, the Ramsey number R(H) is the smallest positive integer n such that every 2-edge-colouring of K_n yields a monochromatic copy of H. We write mH to denote the union of m vertex-disjoint copies of H. The members of the family { mH : m >0 } are also known as H-tilings. A well-known result of Burr, Erdős and Spencer states that R( mK_3 ) = 5m for every m >1. On the other hand, Moon proved that every 2-edge-colouring of K_{3m+2} yields a K_3-tiling consisting of m monochromatic copies of K_3, for every m >1. Crucially, in Moon's result, distinct copies of K_3 might receive different colours.

In this talk, we investigate the analogous questions where the complete host graph is replaced by a graph of large minimum degree and generalise both Moon's theorem and the Burr–Erdős–Spencer theorem to this setting. 

This is joint work with József Balogh and Andrea Freschi.

The random regular graph G_d(n) is selected uniformly at random from all d-regular graphs on n vertices. This model is a lot harder to study than the Erdős-Renyi binomial random graph model G(n, p) as the probabilities of edges being present are not independent. Kim and Vu conjectured that when d ≫ log n it is possible to ‘sandwich’ the random regular graph G_d(n) between two Erdős-Renyi random graphs with similar edge density, and a proof of this sandwich conjecture would unify many previous separate hard-won results.

Various authors have proved weaker versions of the sandwich conjecture with incrementally improved bounds on d: the previous state of the art was due to Gao, Isaev and McKay who proved the conjecture for d ≫ (log n)^4. I will sketch our new proof of the full conjecture.

This is joint work with Richard Montgomery and Daniel Il'kovič.

A q-state spin system is defined by an underlying n-vertex graph G together with one or more parameters.  Configurations of the spin system are assignments s:V(G)->[q] of spins to the vertices (or sometimes edges) of G. Each configuration has a defined weight, which, when appropriately normalised, specifies the so-called Gibbs distribution on configurations. The normalising factor is known as the partition function. (In combinatorial terms this is the generating function for configurations.)  From an algorithmic perspective, the main goals are to sample configurations from the Gibbs distribution, and to evaluate the partition function.

Although their motivation comes from statistical physics, spin systems have numerous connections to combinatorics.   For example, the configurations of a system are often objects familiar from combinatorics, such as independent sets (the `hard-core' model) or matchings (the `mononer-dimer' model).  A further example is provided by the partition function of the Ising model, which is a specialisation of the celebrated Tutte polynomial. 

The computational complexity of sampling configurations, and of evaluating the partition function, is related to the presence or absence of `phase transitions' in the spin system.  This phenomenon in turn is related to the structure of the graph G, e.g., whether it is planar or of bounded degree.  In the talk I'll focus on hereditary graph classes, such as line, claw-free or other H-free graphs.  Depending on time, I might reach recent joint work with Viresh Patel.

Slide for the talk

A map is a "nice" embedding of a graph on a surface. The map is called "regular" if it admits the highest possible level of symmetry (formally: if it is transitive on flags). The regular maps on the sphere correspond to the platonic solids. 

Ultimately we would like to classify the regular maps. In trying to do this there are three standard approaches: one can think about classifying regular maps in terms of the graph being embedded, in terms of the isomorphism class of the automorphism group, or in terms of the surface on which the map sits.

In this talk we consider the latter perspective: I discuss recent work with Conder and Siran in which we describe the regular maps that can occur on a surface whose Euler characteristic is a negative prime power. This builds on earlier work of Breda, Conder, Nedela, Siran and others. Our approach is largely group-theoretic: we use the fact that the automorphism group of a regular map appears naturally as the quotient of a triangle group.

Basic Turán theory asks how many edges a graph can have, given certain restrictions such as not having a large clique. A more generalized Turán question asks how many copies of a fixed subgraph H the graph can have, given certain restrictions. There has been a great deal of recent interest in the case where the restriction is planarity. In this talk, we will discuss some of the general results in the field, primarily the asymptotic value of N_P(n,H), which denotes the maximum number of copies of H in an n-vertex planar graph. In particular, we will focus on the case where H is a cycle.

It was determined that N_P(n,C_{2m}) = (n/m)^m+o(n^m) for small values of m by Cox and Martin and resolved for all m by Lv, Győri, He, Salia, Tompkins, and Zhu.

The case of H=C_{2m+1} is more difficult and it is conjectured that  N_P(n,C_{2m+1})=2m(n/m)^m+o(n^m). 

We will discuss recent progress on this problem, including verification of the conjecture in the case where m=3 and m=4 and a lemma which reduces the solution of this problem for any m to a so-called ``maximum likelihood'' problem. The maximum likelihood problem is, in and of itself, an interesting question in random graph theory.

This is joint work with Emily Heath and Chris (Cox) Wells.

PDF Slide