Past Combinatorial Theory Seminar

The induced graph removal lemma states that for any fixed graph $H$ on $h$ vertices and any $e\textgreater 0$ there exists $d\textgreater0$ such that any graph $G$ with at most $d n^h$ induced copies of $H$ may be made $H$-free by adding or removing atmost $e n^2$ edges. This fact was originally proven by Alon, Fischer, Krivelevich and Szegedy. In this talk, we discuss a new proof and itsrelation to various regularity lemmas. This is joint work with Jacob Fox.

It is known that generic and universal structures and Ramsey classes are related. We explain this connection and complement it by some new examples. Particularly we disscuss universal and Ramsey classes defined by existence and non-existence of homomorphisms.

The 2-dimensional assignment problem (minimum cost matching) is solvable in polynomial time, and it is known that a random instance of size n, with entries chosen independently and uniformly at random from [0,1], has expected cost tending to π^2/6.  In dimensions 3 and higher, the "planar" assignment problem is NP-complete, but what is the expected cost for a random instance, and how well can a heuristic do?  In d dimensions, the expected cost is of order at least n^{2-d} and at most ln n times larger, but the upper bound is non-constructive.  For 3 dimensions, we show a heuristic capable of producing a solution within a factor n^ε of the lower bound, for any constant ε, in time of order roughly n^{1/ε}.  In dimensions 4 and higher, the question is wide open: we don't know any reasonable average-case assignment heuristic.

We consider random walks on two classes of random graphs and explore the likely structure of the the set of unvisited vertices or vacant set. In both cases, the size of the vacant set $N(t)$ can be obtained explicitly as a function of $t$. Let $\Gamma(t)$ be the subgraph induced by the vacant set. We show that, for random graphs $G_{n,p}$ above the connectivity threshold, and for random regular graphs $G_r$, for constant $r\geq 3$, there is a phase transition in the sense of the well-known Erdos-Renyi phase transition. Thus for $t\leq (1-\epsilon)t^*$ we have a unique giant plus components of  size $O(\log n)$ and for $t\geq (1+\epsilon)t^*$ we have only components of  size $O(\log n)$.

In the case of $G_r$ we describe the likely degree sequence, size of the giant component and structure of the small ($O(\log n)$) size components.

A random planar graph $P_n$ is a graph drawn uniformly at random from the class of all (labelled) planar graphs on $n$ vertices. In this talk we show that with probability $1-o(1)$ the number of vertices of degree $k$ in $P_n$ is very close to a quantity $d_k n$ that we determine explicitly. Here $k=k(n) \le c \log n$. In the talk our main emphasis will be on the techniques for proving such results. (Joint work with Kosta Panagiotou.)

We highlight a technique for studying edge colourings of multigraphs, due to Tashkinov. This method is a sophisticated generalisation of the method of alternating paths, and builds upon earlier work by Kierstead and Goldberg. In particular we show how to apply it to a number of edge colouring problems, including the question of whether the class of multigraphs that attain equality in Vizing's classical bound can be characterised.

This talk represents joint work with Jessica McDonald.

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.

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.

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.