Forthcoming events in this series
The critical window for the Ramsey-Turan problem
Abstract
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.
The scaling limit of the minimum spanning tree of the complete graph
Abstract
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).
Criticality for multicommodity flows
Abstract
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.
3-coloring graphs with no induced 6-edge paths
Abstract
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.
Positivity problems for low-order linear recurrence sequences
Abstract
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.
Inside the 4G Spectrum Auction
Abstract
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.
Optimal covers of random graphs with Hamilton cycles
Abstract
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.
Limit method in extremal combinatorics
Abstract
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.
Bootstrap percolation on infinite trees
Abstract
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.
From monotone arithmetic progressions to bounded additive complexity in infinite words
Abstract
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.
Juntas, stability and isoperimetric inequalities in the symmetric group
Abstract
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).
Self-avoiding walks in a half-plane
Abstract
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)
Long paths and cycles in subgraphs of the cube
Abstract
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.
14:30
The hitting time of rainbow connectivity two
Abstract
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
14:30
"Interpolation, box splines, and lattice points in zonotopes"
Abstract
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)
Counting and packing Hamilton cycles in dense graphs and oriented graphs
Abstract
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.
Local limit theorems for giant components
Abstract
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.
Realising evolutionary trees with local information
Abstract
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.
Law of the determinant
Abstract
What is the law of the determinant ?
I am going to give a survey about this problem, focusing on recent developments and new techniques, along with several open questions.
(partially based on joint works with H. Nguyen and T. Tao).
Tiling Euclidean space with a polytope, by translations
Abstract
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.
Strong Ramsey saturation for cycles
Abstract
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.
Extremal Problems in Eulerian Digraphs
Abstract
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
Large and judicious bisections of graphs
Abstract
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 graphs on spaces of negative curvature
Abstract
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.