Forthcoming events in this series
In 1961 Hajos conjectured that if a graph contains no subdivsion of a clique of order t then its chromatic number is less than t. In 1981, Erdos and Fajtlowicz showed that the conjecture is almost always false. We show it is almost always true. This is joint work with Keevash, Mohar, and McDiarmid.
I shall describe some recent results about the asymptotic behaviour of matroids.
Specifically almost all matroids are simple and have probability at least 1/2 of being connected.
Also, various quantitative results about rank, number of bases and number and size of circuits of almost all matroids are given. There are many open problems and I shall not assume any previous knowledge of matroids. This is joint work, see below.
1 D. Mayhew, M. Newman, D. Welsh and G. Whittle,
On the asymptotic properties of connected matroids, European J. Combin. to appear
2 J. Oxley, C. Semple, L. Wasrshauer and D. Welsh,
On properties of almost all matroids, (2011) submitted
The $C_\ell$-free process starts with the empty graph on $n$ vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of $C_\ell$ is created. For every $\ell \geq 4$ we show that, with high probability as $n \to \infty$, the maximum degree is $O((n \log n)^{1/(\ell-1)})$, which confirms a conjecture of Bohman and Keevash and improves on bounds of Osthus and Taraz. Combined with previous results this implies that the $C_\ell$-free process typically terminates with $\Theta(n^{\ell/(\ell-1)}(\log n)^{1/(\ell-1)})$ edges, which answers a question of Erd\H{o}s, Suen and Winkler. This is the first result that determines the final number of edges of the more general $H$-free process for a non-trivial \emph{class} of graphs $H$. We also verify a conjecture of Osthus and Taraz concerning the average degree, and obtain a new lower bound on the independence number. Our proof combines the differential equation method with a tool that might be of independent interest: we establish a rigorous way to `transfer' certain decreasing properties from the binomial random graph to the $H$-free process.
How many triangles must a graph of density d contain? This old question due to Erdos was recently answered by Razborov, after many decades of progress by numerous authors.
We will consider the analogous question for tripartite graphs. Given a tripartite graph with prescribed edges densities between each
pair of classes how many triangles must it contain?
A family of graphs F on a fixed set of n vertices is said to be triangle-intersecting if for any two graphs G,H in F, the intersection of G and H contains a triangle. Simonovits and Sos conjectured that such a family has size at most (1/8)2^{\binom{n}{2}}, and that equality holds only if F
consists of all graphs containing some fixed triangle. Recently, the author, Yuval Filmus and Ehud Friedgut proved a strengthening of this conjecture, namely that if F is an odd-cycle-intersecting family of graphs, then |F| \leq (1/8) 2^{\binom{n}{2}}. Equality holds only if F consists of all graphs containing some fixed triangle. A stability result also holds: an odd-cycle-intersecting family with size close to the maximum must be close to a family of the above form. We will outline proofs of these results, which use Fourier analysis, together with an analysis of the properties of random cuts in graphs, and some results in the theory of Boolean functions. We will then discuss some related open questions.
All will be based on joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Hebrew University of Jerusalem).
Combinatorial pattern matching is a subject which has given us fast and elegant algorithms for a number of practical real world problems as well as being of great theoretical interest. However, when single character wildcards or so-called "don't know" symbols are introduced into the input, classic methods break down and it becomes much more challenging to find provably fast solutions. This talk will give a brief overview of recent results in the area of pattern matching with don't knows and show how techniques from fields as disperse FFTs, group testing and algebraic coding theory have been required to make any progress. We will, if time permits, also discuss the main open problems in the area.
We revisit the problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time sorting algorithm achieving this bound up to a constant factor. They established a crucial link between the entropy of the input partial order and the information-theoretic lower bound. However, their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it unpractical. We develop efficient algorithms for sorting under partial information, derived from approximation and exact algorithms for computing the partial order entropy.
This is joint work with S. Fiorini, G. Joret, R. Jungers, and I. Munro.
The problem of checking existence for an Euler tour of a graph is trivial (are all vertex degrees even?). The problem of counting (or even approximate counting) Euler tours seems to be very difficult. I will describe two simple classes of graphs where the problem can be
solved exactly in polynomial time. And also talk about the many many classes of graphs where no positive results are known.
Consider a configuration of points in $d$-dimensional Euclidean space
together with a set of constraints
which fix the direction or the distance between some pairs of points.
Basic questions are whether the constraints imply that the configuration
is unique or locally unique up to congruence, and whether it is bounded. I
will describe some solutions
and partial solutions to these questions.
Whether as the sudoku puzzles of popular culture or as
restricted coloring problems on graphs or hypergraphs, completing partial
Latin squares and cubes present a framework for a variety of intriguing
problems. In this talk we will present several recent results on
completing partial Latin squares and cubes.
Suppose that $A \subset \mathbb F_2^n$ has density $\Omega(1)$. How
large a subspace is $A+A:=\{a+a’:a,a’ \in A\}$ guaranteed to contain? We
discuss this problem and how the the result changes as the density
approaches $1/2$.
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.
The Wulff droplet arises by conditioning a spin system in a dominant
phase to have an excess of signs of opposite type. These gather
together to form a droplet, with a macroscopic Wulff profile, a
solution to an isoperimetric problem.
I will discuss recent work proving that the phase boundary that
delimits the signs of opposite type has a characteristic scale, both
at the level of exponents and their logarithmic corrections.
This behaviour is expected to be shared by a broad class of stochastic
interface models in the Kardar-Parisi-Zhang class. Universal
distributions such as Tracy-Widom arise in this class, for example, as
the maximum behaviour of repulsive particle systems. time permitting,
I will explain how probabilistic resampling ideas employed in spin
systems may help to develop a qualitative understanding of the random
mechanisms at work in the KPZ class.
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.
We define the edge reconnecting model, a random multigraph evolving in time. At each time step we change one endpoint of a uniformly chosen edge: the new endpoint is chosen by linear preferential attachment. We consider a sequence of edge reconnecting models where the sequence of initial multigraphs is convergent in a sense which is a natural generalization of the Lovász-Szegedy notion of convergence of dense graph sequences. We investigate how the limit objects evolve under the edge reconnecting dynamics if we rescale time properly: we give the complete characterization of the time evolution of the limiting object from its initial state up to the stationary state using the theory of exchangeable arrays, the Pólya urn model, queuing and diffusion processes. The number of parallel edges and the degrees evolve on different timescales and because of this the model exhibits “aging”.
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.
In the Max Acyclic Subdigraph problem we are given a digraph $D$ and ask whether $D$ contains an acyclic subdigraph with at least $k$ arcs. The problem is NP-complete and it is easy to see that the problem is fixed-parameter tractable, i.e., there is an algorithm of running time $f(k)n$ for solving the problem, where $f$ is a computable function of $k$ only and $n=|V(D)|$. The last result follows from the fact that the average number of arcs in an acyclic subdigraph of $D$ is $m/2$, where $m$ is the number of arcs in $D$. Thus, it is natural to ask another question: does $D$ have an acyclic subdigraph with at least $m/2 +k$ arcs?
Mahajan, Raman and Sikdar (2006, 2009), and by Benny Chor (prior to 2006) asked whether this and other problems parameterized above the average are fixed-parameter tractable (the problems include Max $r$-SAT, Betweenness, and Max Lin). Most of there problems have been recently shown to be fixed-parameter tractable.
Methods involved in proving these results include probabilistic inequalities, harmonic analysis of real-valued
functions with boolean domain, linear algebra, and algorithmic-combinatorial arguments. Some new results obtained in this research are of potential interest for several areas of discrete mathematics and computer science. The examples include a new variant of the hypercontractive inequality and an association of Fourier expansions of real-valued functions with boolean domain with weighted systems of linear equations over $F^n_2$.
I’ll mention results obtained together with N. Alon, R. Crowston, M. Jones, E.J. Kim, M. Mnich, I.Z. Ruzsa, S. Szeider, and A. Yeo.
A graph is $\chi$-bounded with a function $f$ is for all induced subgraph H of G, we have $\chi(H) \le f(\omega(H))$. Here, $\chi(H)$ denotes the chromatic number of $H$, and $\omega(H)$ the size of a largest clique in $H$. We will survey several results saying that excluding various kinds of induced subgraphs implies $\chi$-boundedness. More precisely, let $L$ be a set of graphs. If a $C$ is the class of all graphs that do not any induced subgraph isomorphic to a member of $L$, is it true that there is a function $f$ that $\chi$-bounds all graphs from $C$? For some lists $L$, the answer is yes, for others, it is no.
A decomposition theorems is a theorem saying that all graphs from a given class are either "basic" (very simple), or can be partitioned into parts with interesting relationship. We will discuss whether proving decomposition theorems is an efficient method to prove $\chi$-boundedness.
The line graph operation, in which the edges of one graph are taken as the vertices of a new graph with adjacency preserved, is arguably the most interesting of graph transformations. In this survey, we will begin looking at characterisations of line graphs, focusing first on results related to our set of nine forbidden subgraphs. This will be followed by a discussion of some generalisations of line graphs, including our investigations into the Krausz dimension of a graph G, defined as the minimum, over all partitions of the edge-set of G into complete subgraphs, of the maximum number of subgraphs containing any vertex (the maximum in Krausz's characterisation of line graphs being 2).
The line graph operation, in which the edges of one graph are taken as the vertices of a new graph with adjacency preserved, is arguably the most interesting of graph transformations. In this survey, we will begin looking at characterisations of line graphs, focusing first on results related to our set of nine forbidden subgraphs. This will be followed by a discussion of some generalisations of line graphs, including our investigations into the Krausz dimension of a graph G, defined as the minimum, over all partitions of the edge-set of G into complete subgraphs, of the maximum number of subgraphs containing any vertex (the maximum in Krausz's characterisation of line graphs being 2).
The notion of a boundary graph property is a relaxation of that of a
minimal property. Several fundamental results in graph theory have been obtained in
terms of identifying minimal properties. For instance, Robertson and Seymour showed that
there is a unique minimal minor-closed property with unbounded tree-width (the planar
graphs), while Balogh, Bollobás and Weinreich identified nine minimal hereditary
properties of labeled graphs with the factorial speed of growth. However, there are
situations where the notion of minimal property is not applicable. A typical example of this type
is given by graphs of large girth. It is known that for each particular value of k, the
graphs of girth at least k are of unbounded tree-width and their speed of growth is
superfactorial, while the limit property of this sequence (i.e., the acyclic graphs) has bounded
tree-width and its speed of growth is factorial. To overcome this difficulty, the notion of
boundary properties of graphs has been recently introduced. In the present talk, we use this
notion in order to identify some classes of graphs which are well-quasi-ordered with
respect to the induced subgraph relation.
The famous theorem of Szemerédi says that for any natural number $k$ and any $a>0$ there exists $n$ such that if $N\ge n$ then any subset $A$ of the set $[N] =\{1, 2,\ldots , N\}$ of size $|A| \ge a N$ contains an arithmetic progression of length $k$. We consider the question of when such a theorem holds in a random set. More precisely, we say that a set $X$ is $(a, k)$-Szemerédi if every subset $Y$ of $X$ that contains at least $a|X|$ elements contains an arithmetic progression of length $k$. Let $[N]_p$ be the random set formed by taking each element of $[N]$ independently with probability $p$. We prove that there is a threshold at about $p = N^{-1/(k-1)}$ where the probability that $[N]_p$ is $(a, k)$-Szemerédi changes from being almost surely 0 to almost surely 1.
There are many other similar problems within combinatorics. For example, Turán’s theorem and Ramsey’s theorem may be relativised, but until now the precise probability thresholds were not known. Our method seems to apply to all such questions, in each case giving the correct threshold. This is joint work with Tim Gowers.
A family of graphs $H_1,...,H_k$ packs into a graph $G$ if there exist pairwise edge-disjoint copies of $H_1,...,H_k$ in $G$. Gyarfas and Lehel conjectured that any family $T_1, ..., T_n$ of trees of respective orders $1, ..., n$ packs into $K_n$. A similar conjecture of Ringel asserts that $2n$ copies of any trees $T$ on $n+1$ vertices pack into $K_{2n+1}$. In a joint work with Boettcher, Piguet, Taraz we proved a theorem about packing trees. The theorem implies asymptotic versions of the above conjectures for families of trees of bounded maximum degree. Tree-indexed random walks controlled by the nibbling method are used in the proof.
In a joint work with Adamaszek, Adamaszek, Allen and Grosu, we used the nibbling method to prove the approximate version of the related Graceful Tree Labelling conjecture for trees of bounded degree.
In the talk we shall give proofs of both results. We shall discuss possible extensions thereof to trees of unbounded degree.
Fix a positive integer $k$, and consider the class of all graphs which do not have $k+1$ vertex-disjoint cycles. A classical result of Erdos and P\'{o}sa says that each such graph $G$ contains a blocker of size at most $f(k)$. Here a {\em blocker} is a set $B$ of vertices such that $G-B$ has no cycles.
We give a minor extension of this result, and deduce that almost all such labelled graphs on vertex set $1,\ldots,n$ have a blocker of size $k$. This yields an asymptotic counting formula for such graphs; and allows us to deduce further properties of a graph $R_n$ taken uniformly at random from the class: we see for example that the probability that $R_n$ is connected tends to a specified limit as $n \to \infty$.
There are corresponding results when we consider unlabelled graphs with few disjoint cycles. We consider also variants of the problem involving for example disjoint long cycles.
This is joint work with Valentas Kurauskas and Mihyun Kang.
Gupta et al. introduced a very general multi-commodity flow problem in which the cost of a given flow solution on a graph $G=(V,E)$ is calculated by first computing the link loads via a load-function l, that describes the load of a link as a function of the flow traversing the link, and then aggregating the individual link loads into a single number via an aggregation function.
We show the existence of an oblivious routing scheme with competitive ratio $O(\log n)$ and a lower bound of $\Omega(\log n/\logl\og n)$ for this model when the aggregation function agg is an $L_p$-norm.
Our results can also be viewed as a generalization of the work on approximating metrics by a distribution over dominating tree metrics and the work on minimum congestion oblivious. We provide a convex combination of trees such that routing according to the tree distribution approximately minimizes the $L_p$-norm of the link loads. The embedding techniques of Bartal and Fakcharoenphol et al. [FRT03] can be viewed as solving this problem in the $L_1$-norm while the result on congestion minmizing oblivious routing solves it for $L_\infty$. We give a single proof that shows the existence of a good tree-based oblivious routing for any $L_p$-norm.
The simple harmonic urn is a discrete-time stochastic process on $\mathbb Z^2$ approximating the phase portrait of the harmonic oscillator using very basic transitional probabilities on the lattice, incidentally related to the Eulerian numbers.
This urn which we consider can be viewed as a two-colour generalized Polya urn with negative-positive reinforcements, and in a sense it can be viewed as a “marriage” between the Friedman urn and the OK Corral model, where we restart the process each time it hits the horizontal axes by switching the colours of the balls. We show the transience of the process using various couplings with birth and death processes and renewal processes. It turns out that the simple harmonic urn is just barely transient, as a minor modification of the model makes it recurrent.
We also show links between this model and oriented percolation, as well as some other interesting processes.
This is joint work with E. Crane, N. Georgiou, R. Waters and A. Wade.
Let $G=(V,E)$ be a graph with weights $\{w_e : e \in E\}$, and assume all weights are distinct. If $G$ is finite, then the well-known Prim's algorithm constructs its minimum spanning tree in the following manner. Starting from a single vertex $v$, add the smallest weight edge connecting $v$ to any other vertex. More generally, at each step add the smallest weight edge joining some vertex that has already been "explored" (connected by an edge) to some unexplored vertex.
If $G$ is infinite, however, Prim's algorithm does not necessarily construct a spanning tree (consider, for example, the case when the underlying graph is the two-dimensional lattice ${\mathbb Z}^2$, all weights on horizontal edges are strictly less than $1/2$ and all weights on vertical edges are strictly greater than $1/2$).
The behavior of Prim's algorithm for *random* edge weights is an interesting and challenging object of study, even
when the underlying graph is extremely simple. This line of research was initiated by McDiarmid, Johnson and Stone (1996), in the case when the underlying graph is the complete graph $K_n$. Recently Angel et. al. (2006) have studied Prim's algorithm on regular trees with uniform random edge weights. We study Prim's algorithm on $K_n$ and on its infinitary analogue Aldous' Poisson-weighted infinite tree. Along the way, we uncover two new descriptions of the Poisson IIC, the critical Poisson Galton-Watson tree conditioned to survive forever.
Joint work with Simon Griffiths and Ross Kang.
Let $A$ be a finite set in some ambient group. We say that $A$ is a $K$-approximate group if $A$ is symmetric and if the set $A.A$ (the set of all $xy$, where $x$, $y$ lie in $A$) is covered by $K$ translates of $A$. I will illustrate this notion by example, and will go on to discuss progress on the "rough classification" of approximate groups in various settings: abelian groups, nilpotent groups and matrix groups of fixed dimension. Joint work with E. Breuillard.
The Gilbert model of a random geometric graph is the following: place points at random in a (two-dimensional) square box and join two if they are within distance $r$ of each other. For any standard graph property (e.g. connectedness) we can ask whether the graph is likely to have this property. If the property is monotone we can view the model as a process where we place our points and then increase $r$ until the property appears. In this talk we consider the property that the graph has a Hamilton cycle. It is obvious that a necessary condition for the existence of a Hamilton cycle is that the graph be 2-connected. We prove that, for asymptotically almost all collections of points, this is a sufficient condition: that is, the smallest $r$ for which the graph has a Hamilton cycle is exactly the smallest $r$ for which the graph is 2-connected. This work is joint work with Jozsef Balogh and B\'ela Bollob\'as
There are many theorems concerning cycles in graphs for which it is natural to seek analogous results for directed graphs. I will survey
recent progress on certain questions of this type. New results include
(i) a solution to a question of Thomassen on an analogue of Dirac’s theorem
for oriented graphs,
(ii) a theorem on packing cyclic triangles in tournaments that “almost” answers a question of Cuckler and Yuster, and
(iii) a bound for the smallest feedback arc set in a digraph with no short directed cycles, which is optimal up to a constant factor and extends a result of Chudnovsky, Seymour and Sullivan.
These are joint work respectively with (i) Kuhn and Osthus, (ii) Sudakov, and (iii) Fox and Sudakov.
A graph homomorphism is a mapping of vertices which takes edges to edges. The endomorphisms of a graph (homomorphisms to itself) form a submonoid of he full transformation monoid on the vertex set. In the other direction, there is a construction of a graph from a transformation monoid, which will be described in the talk. Composing these maps gives closure operators on graphs and on monoids which have some interesting properties. There are also connections with finite automata and permutation groups.
The conjecture was made by Pemantle that a forest chosen uniformly at random from all forests in any finite graph G has the edge-negative association property. We use enumerative methods to show that this conjecture is true for n large enough when G is a complete graph on n vertices and derive related results for random trees.
Consider the Erdos-Renyi random graph $G(n,p)$ inside the critical window, so that $p = n^{-1} + \lambda n^{-4/3}$ for some real \lambda. In
this regime, the largest components are of size $n^{2/3}$ and have finite surpluses (where the surplus of a component is the number of edges more than a tree that it has). Using a bijective correspondence between graphs and certain "marked random walks", we are able to give a (surprisingly simple) metric space description of the scaling limit of the ordered sequence of components, where edges in the original graph are re-scaled by $n^{-1/3}$. A limit component, given its size and surplus, is obtained by taking a continuum random tree (which is not a Brownian continuum random tree, but one whose distribution has been exponentially tilted) and making certain natural vertex identifications, which correspond to the surplus edges. This gives a metric space in which distances are calculated using paths in the original tree and the "shortcuts" induced by the vertex identifications. The limit of the whole critical random graph is then a collection of such
metric spaces. The convergence holds in a sufficiently strong sense (an appropriate version of the Gromov-Hausdorff distance) that we are able to deduce the convergence in distribution of the diameter of $G(n,p)$, re-scaled by $n^{-1/3}$, to a non-degenerate random variable, for $p$ in the critical window.
This is joint work (in progress!) with Louigi Addario-Berry (Universite de Montreal) and Nicolas Broutin (INRIA Rocquencourt).
We consider a natural generalisation of the independence and chromatic numbers and study their behaviour in Erdos-Renyi random graphs. The t-dependence number of a graph G is the size of the largest subset of the vertices of G whose induced subgraph has maximum degree at most t. The t-improper chromatic number of G is the smallest number of parts needed in a partition of the vertex set of G such that each part induces a subgraph of maximum degree at most t. Clearly, when t = 0, these parameters are, respectively, the independence and chromatic numbers of G. For dense random graphs, we determine the asymptotic ehaviour of these parameters over the range of choices for the growth of t as a function of the number of vertices.
This is joint work with Nikolaos Fountoulakis and Colin McDiarmid.
Random partial orders and random linear extensions
Several interesting models of random partial orders can be described via a
process that builds the partial order one step at a time, at each point
adding a new maximal element. This process therefore generates a linear
extension of the partial order in tandem with the partial order itself. A
natural condition to demand of such processes is that, if we condition on
the occurrence of some finite partial order after a given number of steps,
then each linear extension of that partial order is equally likely. This
condition is called "order-invariance".
The class of order-invariant processes includes processes generating a
random infinite partial order, as well as those that amount to taking a
random linear extension of a fixed infinite poset.
Our goal is to study order-invariant processes in general. In this talk, I
shall explain some of the problems that need to be resolved, and discuss
some of the combinatorial problems that arise.
(joint work with Malwina Luczak)