Past Combinatorial Theory Seminar

Gyárfás conjectured in 1985 that if $G$ is a graph with no induced cycle of odd length at least 5, then the chromatic number of $G$ is bounded by a function of its clique number.  We prove this conjecture.  Joint work with Paul Seymour.

More than twenty years ago Erdős conjectured that a triangle-free graph $G$ of chromatic number $k$ contains cycles of at least $k^{2−o(1)}$ different lengths. In this talk we prove this conjecture in a stronger form, showing that every such $G$ contains cycles of $ck^2\log k$ consecutive lengths, which is tight. Our approach can be also used to give new bounds on the number of different cycle lengths for other monotone classes of $k$-chromatic graphs, i.e.,  clique-free graphs and graphs without odd cycles.

Joint work with A. Kostochka and J. Verstraete.

We study the properties of finite graphs in which the ball of radius $r$ around each vertex induces a graph isomorphic to some fixed graph $F$. (Such a graph is said to be $r$-locally-$F$.) This is a natural extension of the study of regular graphs, and of the study of graphs of constant link. We focus on the case where $F$ is $\mathbb{L}^d$, the $d$-dimensional integer lattice. We obtain a characterisation of all the finite graphs in which the ball of radius $3$ around each vertex is isomorphic to the ball of radius $3$ in $\mathbb{L}^d$, for each integer $d$. These graphs have a very rigidly proscribed global structure, much more so than that of $(2d)$-regular graphs. (They can be viewed as quotient lattices in certain 'flat orbifolds'.) Our results are best possible in the sense that '3' cannot be replaced with '2'. Our proofs use a mixture of techniques and results from combinatorics, algebraic topology and group theory. We will also discuss some results and open problems on the properties of a random n-vertex graph which is $r$-locally-$F$. This is all joint work with Itai Benjamini (Weizmann Institute of Science). 

We use a growth procedure for binary trees due to Luczak and Winkler, a bijection between binary trees and irreducible quadrangulations of the hexagon due to Fusy, Poulalhon and Schaeffer, and the classical angular mapping between quadrangulations and maps, to define a growth procedure for maps. The growth procedure is local, in that every map is obtained from its predecessor by an operation that only modifies vertices lying on a common face with some fixed vertex. The sequence of maps has an almost sure limit G; we show that G is the distributional local limit of large, uniformly random 3-connected graphs.
A classical result of Brooks, Smith, Stone and Tutte associates squarings of rectangles to edge-rooted planar graphs. Our map growth procedure induces a growing sequence of squarings, which we show has an almost sure limit: an infinite squaring of a finite rectangle, which almost surely has a unique point of accumulation. We know almost nothing about the limit, but it should be in some way related to "Liouville quantum gravity".
Parts joint with Nicholas Leavitt.

In the Erdös-Rényi random graph process, starting from an empty graph, in each step a new random edge is added to the evolving graph. One of its most interesting features is the `percolation phase transition': as the ratio of the number of edges to vertices increases past a certain critical density, the global structure changes radically, from only small components to a single giant component plus small ones.


In this talk we consider Achlioptas processes, which have become a key example for random graph processes with dependencies between the edges. Starting from an empty graph these proceed as follows: in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. We discuss why, for a large class of rules, the percolation phase transition is qualitatively comparable to the classical Erdös-Rényi process.


Based on joint work with Oliver Riordan.

A system of linear equations is called partition regular if, whenever the naturals are finitely coloured, there is a monochromatic solution of the equations. Many of the classical theorems of Ramsey Theory may be phrased as assertions that certain systems are partition regular.

What happens if we are colouring not the naturals but the (non-zero) integers, rationals, or reals instead? After some background, we will give various recent results.

Erdos, Faudree, Gould, Gyarfas, Rousseau and Schelp, conjectured that
whenever the edges of a complete graph are coloured using three colours
there always exists a set of at most three vertices which have at least
two-thirds of their neighbours in one of the colours.  We will describe a
proof of this conjecture. This is joint work with Rahil Baber

Fix positive integers p and q with 2 \leq q \leq {p \choose 2}. An edge-colouring of the complete graph K_n is said to be a (p, q)-colouring if every K_p receives at least q different colours. The function f(n, p, q) is the minimum number of colours that are needed for K_n to have a (p,q)-colouring. This function was introduced by Erdos and Shelah about 40 years ago, but Erdos and Gyarfas were the first to study the function in a systematic way. They proved that f(n, p, p) is polynomial in n and asked to determine the maximum q, depending on p, for which f(n,p,q) is subpolynomial in n. We prove that the answer is p-1.

We also discuss some related questions.

Joint work with Jacob Fox, Choongbum Lee and Benny Sudakov.

I will discuss a novel approach to estimating communication costs of an algorithm (also known as its I/O complexity), which is based on small-set expansion for computational graphs. Various applications and implications will be discussed as well, mostly having to do with linear algebra algorithms. This includes, in particular, first known (and tight) bounds on communication complexity of fast matrix multiplication.

Joint work with Grey Ballard, James Demmel, Benjamin Lipshitz and Oded Schwartz.

We discuss some questions related to coloring the edge/vertices of randomgraphs. In particular we look at
(i) The game chromatic number;
(ii) Rainbow Matchings and Hamilton cycles;
(iii) Rainbow Connection;
(iv) Zebraic Colorings.

Several objects can be associated to a list of vectors with integer coordinates: among others, a family of tori called toric arrangement, a convex polytope called zonotope, a function called vector partition function; these objects have been described in a recent book by De Concini and Procesi. The linear algebra of the list of vectors is axiomatized by the combinatorial notion of a matroid; but several properties of the objects above depend also on the arithmetics of the list. This can be encoded by the notion of a "matroid over Z". Similarly, applications to tropical geometry suggest the introduction of matroids over a discrete valuation ring.Motivated by the examples above, we introduce the more general notion of a "matroid over a commutative ring R". Such a matroid arises for example from a list of elements in a R-module. When R is a Dedekind domain, we can extend the usual properties and operations holding for matroids (e.g., duality). We can also compute the Tutte-Grothendieck ring of matroids over R; the class of a matroid in such a ring specializes to several invariants, such as the Tutte polynomial and the Tutte quasipolynomial. We will also outline other possible applications and open problems. (Joint work with Alex Fink).

We give a new proof of the Frankl-Rödl theorem on set systems with a forbidden intersection. Our method extends to codes with forbidden distances, where over large alphabets our bound is significantly better than that obtained by Frankl and Rödl. One consequence of our result is a Frankl-Rödl type theorem for permutations with a forbidden distance. Joint work with Peter Keevash.

A Steiner Triple System on a set X is a collection T of 3-element subsets of X such that every pair of elements of X is contained in exactly one of the triples in T. An example considered by Plücker in 1835 is the affine plane of order three, which consists of 12 triples on a set of 9 points. Plücker observed that a necessary condition for the existence of a Steiner Triple System on a set with n elements is that n be congruent to 1 or 3 mod 6. In 1846, Kirkman showed that this necessary condition is also sufficient.

In 1853, Steiner posed the natural generalisation of the question: given integers q and r, for which n is it possible to choose a collection Q of q-element subsets of an n-element set X such that any r elements of X are contained in exactly one of the sets in Q? There are some natural necessary divisibility conditions generalising the necessary conditions for Steiner Triple Systems. The Existence Conjecture states that for all but finitely many n these divisibility conditions are also sufficient for the existence of general Steiner systems (and more generally designs).

We prove the Existence Conjecture, and more generally, we show that the natural divisibility conditions are sufficient for clique decompositions of simplicial complexes that satisfy a certain pseudorandomness condition.

We introduce and develop a theory of limits for sequences of sparse graphs based on $L^p$ graphons, which generalizes both the existing $L^\infty$ theory of dense graph limits and its extension by Bollob\'as and Riordan to sparse graphs without dense spots. In doing so, we replace the no dense spots hypothesis with weaker assumptions, which allow us to analyze graphs with power law degree distributions. This gives the first broadly applicable limit theory for sparse graphs with unbounded average degrees.

Joint work with Christian Borgs, Jennifer T. Chayes, and Henry Cohn.

We consider the parameter $a(H)$, which is the smallest a such that if $|E(G)|$ is at least/exceeds $a|V(H)|/2$ then $G$ has an $H$-minor. We are especially interested in sparse $H$ and in bounding $a(H)$ as a function of $|E(H)|$ and $|V(H)|$. This is joint work with David Wood.

Nesetril and Ossona de Mendez introduced a new notion of convergence of graphs called FO convergence. This notion can be viewed as a unified notion of convergence of dense and sparse graphs. In particular, every FO convergent sequence of graphs is convergent in the sense of left convergence of dense graphs as studied by Borgs, Chayes, Lovasz, Sos, Szegedy, Vesztergombi and others, and every FO convergent sequence of graphs with bounded maximum degree is convergent in the Benjamini-Schramm sense.

FO convergent sequences of graphs can be associated with a limit object called modeling. Nesetril and Ossona de Mendez showed that every FO convergent sequence of trees with bounded depth has a modeling. We extend this result

to all FO convergent sequences of trees and discuss possibilities for further extensions.

The talk is based on a joint work with Martin Kupec and Vojtech Tuma.

We prove a generalization of Helly's theorem concerning intersections of convex sets that has an interesting voting theory interpretation. We then
consider various extensions in which compelling mathematical problems are motivated from very natural questions in the voting context.

The Ramsey number $R(K_s, Q_n)$ is the smallest integer $N$ such that every red-blue colouring of the edges of the complete graph $K_N$ contains either a red $n$-dimensional hypercube, or a blue clique on $s$ vertices. Note that $N=(s-1)(2^n -1)$ is not large enough, since we may colour in red $(s-1)$ disjoint cliques of cardinality $2^N -1$ and colour the remaining edges blue. In 1983, Burr and Erdos conjectured that this example was the best possible, i.e., that $R(K_s, Q_n) = (s-1)(2^n -1) + 1$ for every positive integer $s$ and sufficiently large $n$. In a recent breakthrough, Conlon, Fox, Lee and Sudakov proved the conjecture up to a multiplicative constant for each $s$. In this talk we shall sketch the proof of the conjecture and discuss some related problems.

(Based on joint work with Gonzalo Fiz Pontiveros, Robert Morris, David Saxton and Jozef Skokan)

The Tutte polynomial of a graph $G$ is a two-variable polynomial $T(G;x,y)$, which encodes much information about~$G$. The number of spanning trees in~$G$, the number of acyclic orientations of~$G$, and the partition function of the $q$-state Potts model are all specialisations of the Tutte polynomial. Jackson and Sokal have studied the sign of the Tutte polynomial, and identified regions in the $(x,y)$-plane where it is ``essentially determined'', in the sense that the sign is a function of very simple characteristics of $G$, e.g., the number of vertices and connected components of~$G$. It is natural to ask whether the sign of the Tutte polynomial is hard to compute outside of the regions where it is essentially determined. We show that the answer to this question is often an emphatic ``yes'': specifically, that determining the sign is \#P-hard. In such cases, approximating the Tutte polynomial with small relative error is also \#P-hard, since in particular the sign must be determined. In the other direction, we can ask whether the Tutte polynomial is easy to approximate in regions where the sign is essentially determined. The answer is not straightforward, but there is evidence that it often ``no''. This is joint work with Leslie Ann Goldberg (Oxford).

Perfect matchings are fundamental objects of study in graph theory. There is a substantial classical theory, which cannot be directly generalised to hypergraphs unless P=NP, as it is NP-complete to determine whether a hypergraph has a perfect matching. On the other hand, the generalisation to hypergraphs is well-motivated, as many important problems can be recast in this framework, such as Ryser's conjecture on transversals in latin squares and the Erdos-Hanani conjecture on the existence of designs. We will discuss a characterisation of the perfect matching problem for uniform hypergraphs that satisfy certain density conditions (joint work with Richard Mycroft), and a polynomial time algorithm for determining whether such hypergraphs have a perfect matching (joint work with Fiachra Knox and Richard Mycroft).

Let $G$ be an addable minor-closed class of graphs. We prove that a zero-one law holds in monadic second-order logic (MSO) for connected graphs in G, and a convergence law in MSO for all graphs in $G$. For each surface $S$, we prove the existence of a zero-one law in first order logic (FO) for connected graphs embeddable in $S$, and a convergence law in FO for all graphs embeddable in $S$. Moreover, the limiting probability that a given FO sentence is satisfied is independent of the surface $S$. If $G$ is an addable minor-closed class, we prove that the closure of the set of limiting probabilities is a finite union of intervals, and it is the same for FO and MSO. For the class of planar graphs it consists of exactly 108 intervals. We give examples of non-addable classes where the results are quite different: for instance, the zero-one law does not hold for caterpillars, even in FO. This is joint work with Peter Heinig, Tobias Müller and Anusch Taraz.

An independent set in an $r$-uniform hypergraph is a subset of the vertices that contains no edges. A container for the independent set is a superset of it. It turns out to be desirable for many applications to find a small collection of containers, none of which is large, but which between them contain every independent set. ("Large" and "small" have reasonable meanings which will be explained.)

Applications include giving bounds on the list chromatic number of hypergraphs (including improving known bounds for graphs), counting the solutions to equations in Abelian groups, counting Sidon sets, establishing extremal properties of random graphs, etc.

The work is joint with David Saxton.

The first application of Szemeredi's regularity method was the following celebrated Ramsey-Turan result proved by Szemeredi in 1972: any K_4-free graph on N vertices with independence number o(N) has at most (1/8 + o(1))N^2 edges. Four years later, Bollobas and Erdos gave a surprising geometric construction, utilizing the isodiametric inequality for the high dimensional sphere, of a K_4-free graph on N vertices with independence number o(N) and (1/8 - o(1)) N^2 edges. Starting with Bollobas and Erdos in 1976, several problems have been asked on estimating the minimum possible independence number in the critical window, when the number of edges is about N^2 / 8.

These problems have received considerable attention and remained one of the main open problems in this area.  More generally, it remains an important problem to determine if, for certain applications of the regularity method, alternative proofs exist which avoid using the regularity lemma and give better quantitative estimates.  In this work, we develop new regularity-free methods which give nearly best-possible bounds, solving the various open problems concerning this critical window.

Joint work with Jacob Fox and Yufei Zhao.

Consider the complete graph on n vertices with independent and identically distributed edge-weights having some absolutely continuous distribution. The minimum spanning tree (MST) is simply the spanning subtree of smallest weight. It is straightforward to construct the MST using one of several natural algorithms. Kruskal's algorithm builds the tree edge by edge starting from the globally lowest-weight edge and then adding other edges one by one in increasing order of weight, as long as they do not create any cycles. At each step of this process, the algorithm has generated a forest, which becomes connected on the final step. In this talk, I will explain how it is possible to exploit a connection between the forest generated by Kruskal's algorithm and the Erd\"os-R\'enyi random graph in order to prove that $M_n$, the MST of the complete graph, possesses a scaling limit as $n$ tends to infinity. In particular, if we think of $M_n$ as a metric space (using the graph distance), rescale edge-lengths by $n^{-1/3}$, and endow the vertices with the uniform measure, then $M_n$ converges in distribution in the sense of the Gromov-Hausdorff-Prokhorov distance to a certain random measured real tree.

This is joint work with Louigi Addario-Berry (McGill), Nicolas Broutin (INRIA Paris-Rocquencourt) and Grégory Miermont (ENS Lyon).

The ``k-commodity flow problem'' is: we are given k pairs of vertices of a graph, and we ask whether there are k flows in the graph, where the ith flow is between the ith pair of vertices, and has total value one, and for each edge, the sum of the absolute values of the flows along it is at most one. We may also require the flows to be 1/2-integral, or indeed 1/p-integral for some fixed p.

If the problem is feasible (that is, the desired flows exist) then it is still feasible after contracting any edge, so let us say a flow problem is ``critical'' if it is infeasible, but becomes feasible when we contract any edge. In many special cases, all critical instances have only two vertices, but if we ask for integral flows (that is, p = 1, essentially the edge-disjoint paths problem), then there arbitrarily large critical instances, even with k = 2. But it turns out that p = 1 is the only bad case; if p>1 then all critical instances have bounded size (depending on k, but independent of p), and the same is true if there is no integrality requirement at all.

The proof gives rise to a very simple algorithm for the k edge-disjoint paths problem in 4-edge-connected graphs.

Since graph-coloring is an NP-complete problem in general, it is natural to ask how the complexity changes if the input graph is known not to contain a certain induced subgraph H. Due to results of Kaminski and Lozin, and Hoyler, the problem remains NP-complete, unless H is the disjoint union of paths. Recently the question of coloring graphs with a fixed-length induced path forbidden has received considerable attention, and only a few cases of that problem remain open for k-coloring when k>=4. However, little is known for 3-coloring. Recently we have settled the first open case for 3-coloring; namely we showed that 3-coloring graphs with no induced 6-edge paths can be done in polynomial time. In this talk we will discuss some of the ideas of the algorithm.

This is joint work with Peter Maceli and Mingxian Zhong.

We consider two decision problems for linear recurrence sequences(LRS) over the integers, namely the Positivity Problem (are all terms of a given LRS positive?) and the Ultimate Positivity Problem (are all but finitely many terms of a given LRS positive?). We show decidability of both problems for LRS of order 5 or less, and for simple LRS (i.e. whose characteristic polynomial has no repeated roots) of order 9 or less. Moreover, we show by way of hardness that extending the decidability of either problem to LRS of order 6 would entail major breakthroughs in analytic number theory, more precisely in the field of Diophantine approximation of transcendental numbers.
This talk is based on a recent paper, available at
http://www.cs.ox.ac.uk/people/joel.ouaknine/publications/positivity13ab…
joint with James Worrell and Matt Daws.

The recently completed auction for 4G mobile spectrum was the most importantcombinatorial auction ever held in the UK.  In general, combinatorial auctions allow bidders to place individual bids on packages of items,instead of separate bids on individual items, and this feature has theoretical advantages for bidders and sellers alike.  The accompanying challenges of implementation have been the subject of intense work over the last few years, with the result that the advantages of combinatorial auctions can now be realised in practice on a large scale.  Nowhere has this work been more prominent than in auctions for radio spectrum.  The UK's 4G auction is the most recent of these and the publication by Ofcom (the UK's telecommunications regulator) of the auction's full bidding activity creates a valuable case study of combinatorial auctions in action.

We prove that if $\frac{\log^{117} n}{n} \leq p \leq 1 -

n^{-1/8}$, then asymptotically almost surely the edges of $G(n,p)$ can

be covered by $\lceil \Delta(G(n,p))/2 \rceil$ Hamilton cycles. This

is clearly best possible and improves an approximate result of Glebov,

Krivelevich and Szab\'o, which holds for $p \geq n^{-1 + \varepsilon}$.

Based on joint work with Daniela Kuhn, John Lapinskas and Deryk Osthus.

Razborov's flag algebras provide a formal system

for operating with asymptotic inequalities between subgraph densities,

allowing to do extensive "book-keeping" by a computer. This novel use

of computers led to progress on many old problems of extremal

combinatorics. In some cases, finer structural information can be

derived from a flag algebra proof by by using the Removal Lemma or

graph limits. This talk will overview this approach.

While usual percolation concerns the study of the connected components of

random subgraphs of an infinite graph, bootstrap percolation is a type of

cellular automaton, acting on the vertices of a graph which are in one of

two states: `healthy' or `infected'. For any positive integer $r$, the

$r$-neighbour bootstrap process is the following update rule for the

states of vertices: infected vertices remain infected forever and each

healthy vertex with at least $r$ infected neighbours becomes itself

infected. These updates occur simultaneously and are repeated at discrete

time intervals. Percolation is said to occur if all vertices are

eventually infected.

As it is often difficult to determine precisely which configurations of

initially infected vertices percolate, one often considers a random case,

with each vertex infected independently with a fixed probability $p$. For

an infinite graph, of interest are the values of $p$ for which the

probability of percolation is positive. I will give some of the history

of this problem for regular trees and present some new results for

bootstrap percolation on certain classes of randomly generated trees:

Galton--Watson trees.

I will describe how a search for the answer to an old question about the existence of monotone arithmetic progressions in permutations of positive integers led to the study of infinite words with bounded additive complexity. The additive complexity of a word on a finite subset of integers is defined as the function that, for a positive integer $n$, counts the maximum number of factors of length $n$, no two of which have the same sum.

Results of Bourgain and Kindler-Safra state that if $f$ is a Boolean function on $\{0,1\}^n$, and

the Fourier transform of $f$ is highly concentrated on low frequencies, then $f$ must be close

to a ‘junta’ (a function depending upon a small number of coordinates). This phenomenon is

known as ‘Fourier stability’, and has several interesting consequences in combinatorics,

theoretical computer science and social choice theory. We will describe some of these,

before turning to the analogous question for Boolean functions on the symmetric group. Here,

genuine stability does not occur; it is replaced by a weaker phenomenon, which we call

‘quasi-stability’. We use our 'quasi-stability' result to prove an isoperimetric inequality

for $S_n$ which is sharp for sets of size $(n-t)!$, when $n$ is large. Several open questions

remain. Joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Weizmann

Institute).

A self-avoiding walk on a lattice is a walk that never visits the same vertex twice.  Self-avoiding walks (SAW) have attracted interest for decades, first in statistical physics, where they are considered as polymer models, and then in combinatorics and in probability theory (the first mathematical contributions are probably due to John Hammersley, from Oxford, in the early sixties). However, their properties remain poorly understood in low dimension, despite the existence of remarkable conjectures.

About two years ago, Duminil-Copin and Smirnov proved an "old" and remarkable conjecture of Nienhuis (1982), according to which the number of SAWs of length n on the honeycomb (hexagonal) lattice grows like mu^n, with mu=sqrt(2 +sqrt(2)).

This beautiful result has woken up the hope to prove other simple looking conjectures involving these objects. I will thus present the proof of a younger conjecture (1995) by Batchelor and Yung, which deals with SAWs confined to a half-plane and interacting with its boundary.

(joint work with N. Beaton, J. de Gier, H. Duminil-Copin and A. Guttmann)

Let $Q_n$ denote the graph of the $n$-dimensional cube with vertex set $\{0, 1\}^n$

in which two vertices are adjacent if they differ in exactly one coordinate.

Suppose $G$ is a subgraph of $Q_n$ with average degree at least $d$. How long a

path can we guarantee to find in $G$?

My aim in this talk is to show that $G$ must contain an exponentially long

path. In fact, if $G$ has minimum degree at least $d$ then $G$ must contain a path

of length $2^d − 1$. Note that this bound is tight, as shown by a $d$-dimensional

subcube of $Q^n$. I hope to give an overview of the proof of this result and to

discuss some generalisations.

Rainbow connectivity is a new concept for measuring the connectivity of a graph which was introduced in 2008 by Chartrand, Johns, McKeon and Zhang. In a graph G with a given edge colouring, a rainbow path is a path all of whose edges have distinct colours. The minimum number of colours required to colour the edges of G so that every pair of vertices is joined by at least one rainbow path is called the rainbow connection number rc(G) of the graph G.

For any graph G, rc(G) >= diam(G). We will discuss rainbow connectivity in the random graph setting and present the result that for random graphs, rainbow connectivity 2 happens essentially at the same time as diameter 2. In fact, in the random graph process, with high probability the hitting times of diameter 2 and of rainbow connection number 2 coincide

Given a finite list of vectors X in $\R^d$, one can define the box spline $B_X$. Box splines are piecewise polynomial functions that are used in approximation theory. They are also interesting from a combinatorial point of view and many of their properties solely depend on the structure of the matroid defined by the list X. The support of the box spline is a certain polytope called zonotope Z(X). We will show that if the list X is totally unimodular, any real-valued function defined on the set of lattice points in the interior of Z(X) can be extended to a function on Z(X) of the form $p(D)B_X$ in a unique way, where p(D) is a differential operator that is contained in the so-called internal P-space. This was conjectured by Olga Holtz and Amos Ron. The talk will focus on combinatorial aspects and all objects mentioned above will be defined. (arXiv:1211.1187)

In this talk we present a general method using permanent estimates in order to obtain results about counting and packing Hamilton cycles in dense graphs and oriented graphs. As a warm up we prove that every Dirac graph $G$ contains at least $(reg(G)/e)^n$ many distinct Hamilton cycles, where $reg(G)$ is the maximal degree of a spanning regular subgraph of $G$. We continue with strengthening a result of Cuckler by proving that the number of oriented Hamilton cycles in an almost $cn$-regular oriented graph is $(cn/e)^n(1+o(1))^n$, provided that $c$ is greater than $3/8$. Last, we prove that every graph $G$ of minimum degree at least $n/2+\epsilon n$ contains at least $reg_{even}(G)-\epsilon n$ edge-disjoint Hamilton cycles, where $reg_{even}(G)$ is the maximal even degree of a spanning regular subgraph of $G$. This proves an approximate version of a conjecture made by Osthus and K\"uhn.  Joint work with Michael Krivelevich and Benny Sudakov.

In an Erdős--R\'enyi random graph above the phase transition, i.e.,

where there is a giant component, the size of (number of vertices in)

this giant component is asymptotically normally distributed, in that

its centred and scaled size converges to a normal distribution. This

statement does not tell us much about the probability of the giant

component having exactly a certain size. In joint work with B\'ela

Bollob\'as we prove a `local limit theorem' answering this question

for hypergraphs; the graph case was settled by Luczak and Łuczak.

The proof is based on a `smoothing' technique, deducing the local

limit result from the (much easier) `global' central limit theorem.

Results that say local information is enough to guarantee global information provide the theoretical underpinnings of many reconstruction algorithms in evolutionary biology. Such results include Buneman's Splits-Equivalence Theorem and the Tree-Metric Theorem. The first result says that, for a collection $\mathcal C$ of binary characters, pairwise compatibility is enough to guarantee compatibility for $\mathcal C$, that is, there is a phylogenetic (evolutionary) tree that realises $\mathcal C$. The second result says that, for a distance matrix $D$, if every $4\times 4$ distance submatrix of $D$ is realisable by an edge-weighted phylogenetic tree, then $D$ itself is realisable by such a tree. In this talk, we investigate these and other results of this type. Furthermore, we explore the closely-related task of determining how much information is enough to reconstruct the correct phylogenetic tree.

We study the problem of covering R^d by overlapping translates of a convex polytope, such that almost every point of R^d is covered exactly k times. Such a covering of Euclidean space by a discrete set of translations is called a k-tiling. The investigation of simple tilings by translations (which we call 1-tilings in this context) began with the work of Fedorov and Minkowski, and was later extended by Venkov and McMullen to give a complete characterization of all convex objects that 1-tile R^d. By contrast, for k ≥ 2, the collection of polytopes that k-tile is much wider than the collection of polytopes that 1-tile, and there is currently no known analogous characterization for the polytopes that k-tile. Here we first give the necessary conditions for polytopes P that k-tile, by proving that if P k-tiles R^d by translations, then it is centrally symmetric, and its facets are also centrally symmetric. These are the analogues of Minkowski’s conditions for 1-tiling polytopes, but it turns out that very new methods are necessary for the development of the theory. In the case that P has rational vertices, we also prove that the converse is true; that is, if P is a rational, centrally symmetric polytope, and if P has centrally symmetric facets, then P must k-tile R^d for some positive integer k.

We call a graph $H$ \emph{Ramsey-unsaturated} if there is an edge in the

complement of $H$ such that the Ramsey number $r(H)$ of $H$ does not

change upon adding it to $H$. This notion was introduced by Balister,

Lehel and Schelp who also showed that cycles (except for $C_4$) are

Ramsey-unsaturated, and conjectured that, moreover, one may add {\em

any} chord without changing the Ramsey number of the cycle $C_n$, unless

$n$ is even and adding the chord creates an odd cycle.

We prove this conjecture for large cycles by showing a stronger

statement: If a graph $H$ is obtained by adding a linear number of

chords to a cycle $C_n$, then $r(H)=r(C_n)$, as long as the maximum

degree of $H$ is bounded, $H$ is either bipartite (for even $n$) or

almost bipartite (for odd $n$), and $n$ is large.

This motivates us to call cycles \emph{strongly} Ramsey-unsaturated.

Our proof uses the regularity method.

Graphs and digraphs behave quite differently, and many classical results for graphs are often trivially false when extended to general digraphs. Therefore it is usually necessary to restrict to a smaller family of digraphs to obtain meaningful results. One such very natural family is Eulerian digraphs, in which the in-degree equals out-degree at every vertex.

In this talk, we discuss several natural parameters for Eulerian digraphs and study their connections. In particular, we show that for any Eulerian digraph G with n vertices and m arcs, the minimum feedback arc set (the smallest set of arcs whose removal makes G acyclic) has size at least $m^2/2n^2+m/2n$, and this bound is tight. Using this result, we show how to find subgraphs of high minimum degrees, and also long cycles in Eulerian digraphs. These results were motivated by a conjecture of Bollob\'as and Scott.

Joint work with Ma, Shapira, Sudakov and Yuster

It is very well known that every graph on $n$ vertices and $m$ edges admits a bipartition of size at least $m/2$. This bound can be improved to $m/2 + (n-1)/4$ for connected graphs, and $m/2 + n/6$ for graphs without isolated vertices, as proved by Edwards, and Erd\"os, Gy\'arf\'as, and Kohayakawa, respectively. A bisection of a graph is a bipartition in which the size of the two parts differ by at most 1. We prove that graphs with maximum degree $o(n)$ in fact admit a bisection which asymptotically achieves the above bounds.These results follow from a more general theorem, which can also be used to answer several questions and conjectures of Bollob\'as and Scott on judicious bisections of graphs.
Joint work with Po-Shen Loh and Benny Sudakov

Random geometric graphs have been well studied over the last 50 years or so. These are graphs that

are formed between points randomly allocated on a Euclidean space and any two of them are joined if

they are close enough. However, all this theory has been developed when the underlying space is

equipped with the Euclidean metric. But, what if the underlying space is curved?

The aim of this talk is to initiate the study of such random graphs and lead to the development of

their theory. Our focus will be on the case where the underlying space is a hyperbolic space. We

will discuss some typical structural features of these random graphs as well as some applications,

related to their potential as a model for networks that emerge in social life or in biological

sciences.