Forthcoming events in this series
Colouring graphs without odd holes
Abstract
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.
Cycles in triangle-free graphs of large chromatic number
Abstract
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.
Spanning Trees in Random Graphs
Abstract
The structure of graphs which are locally indistinguishable from a lattice.
Abstract
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).
Growing random trees, maps, and squarings
Abstract
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.
The phase transition in bounded-size Achlioptas processes
Abstract
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.
Partition Regularity in the Naturals and the Rationals
Abstract
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.
The two-thirds conjecture
Abstract
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
On the Erdos-Gyarfas problem in generalised Ramsey theory
Abstract
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.
Graph expansion and communication complexity of algorithms
Abstract
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.
Randomly Colouring Random Graphs
Abstract
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.
14:30
Matroids over a ring: motivations, examples, applications.
Abstract
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).
Frankl-Rödl type theorems for codes and permutations
Abstract
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.
The existence of designs
Abstract
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.
Sparse graph limits and scale-free networks
Abstract
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.
How many edges are needed to force an $H$-minor?
Abstract
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.
FO limits of trees
Abstract
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.
Set Intersections, Perfect Graphs, and Voting in Agreeable Societies
Abstract
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 of the clique and the hypercube
Abstract
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: sign and approximability
Abstract
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).
Hypergraph matchings
Abstract
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).
Logical limit laws for minor-closed classes of graphs
Abstract
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.
Containers for independent sets
Abstract
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.