Forthcoming events in this series


Tue, 29 Nov 2016
14:30
L6

Decomposing the Complete r-Graph

Imre Leader
(University of Cambridge)
Abstract

The Graham-Pollak theorem states that to decompose the complete graph $K_n$ into complete bipartite subgraphs we need at least $n-1$ of them. What
happens for hypergraphs? In other words, suppose that we wish to decompose the complete $r$-graph on $n$ vertices into complete $r$-partite $r$-graphs; how many do we need?

In this talk we will report on recent progress on this problem. This is joint work with Luka Milicevic and Ta Sheng Tan.

Tue, 22 Nov 2016
14:30
L6

Colouring perfect graphs with a bounded number of colours

Paul Seymour
(Princeton University)
Abstract

It follows from the ellipsoid method and results of Grotschel, Lovasz and Schrijver that one can find an optimal colouring of a perfect graph in polynomial time. But no ''combinatorial'' algorithm to do this is known.

Here we give a combinatorial algorithm to do this in an n-vertex perfect graph in time O(n^{k+1}^2) where k is the clique number; so polynomial-time for fixed k. The algorithm depends on another result, a polynomial-time algorithm to find a ''balanced skew partition'' in a perfect graph if there is one.

Joint work with Maria Chudnovsky, Aurelie Lagoutte, and Sophie Spirkl.

Tue, 15 Nov 2016
14:30
L6

Forbidden vector-valued intersection

Eoin Long
(Oxford University)
Abstract

Given vectors $V = (v_i: i \in [n]) \in R^D$, we define the $V$-intersection of $A,B \subset [n]$ to be the vector $\sum_{i \in A \cap B} v_i$. In this talk, I will discuss a new, essentially optimal, supersaturation theorem for $V$-intersections, which can be roughly stated as saying that any large family of sets contains many pairs $(A,B)$ with $V$-intersection $w$, for a wide range of $V$ and $w$. A famous theorem of Frankl and Rödl corresponds to the case $D=1$ and all $v_i=1$ of our theorem. The case $D=2$ and $v_i=(1,i)$ solves a conjecture of Kalai.

Joint work with Peter Keevash.

Tue, 08 Nov 2016
14:30
L6

Turán Numbers via Local Stability Method

Liana Yepremyan
(Oxford University)
Abstract

The Turán number of an $r$-graph $G$, denoted by $ex(n,G)$, is the maximum number of edges in an $G$-free $r$-graph on $n$ vertices. The Turán density  of an $r$-graph $G$, denoted by $\pi(G)$, is the limit as $n$ tends to infinity of the maximum edge density of an $G$-free $r$-graph on $n$ vertices.

During this talk I will discuss a method, which we call  local stability method, that allows one to obtain exact Turán numbers from Turán density results. This method can be thought of as an extension of the classical stability method by  generically utilising the Lagrangian function. Using it, we obtained new hypergraph Turán numbers. In particular, we did so for a hypergraph called generalized triangle, for uniformities 5 and 6, which solved a conjecture of Frankl and Füredi from 1980's.

This is joint work with Sergey Norin.

Tue, 01 Nov 2016
14:30
L6

Exact Ramsey numbers of odd cycles via nonlinear optimisation

Matthew Jenssen
(London School of Economics)
Abstract

For a graph $G$, the $k$-colour Ramsey number $R_k(G)$ is the least integer $N$ such that every $k$-colouring of the edges of the complete graph $K_N$ contains a monochromatic copy of $G$. Let $C_n$ denote the cycle on $n$ vertices. We show that for fixed $k\geq2$ and $n$ odd and sufficiently large,
$$
R_k(C_n)=2^{k-1}(n-1)+1.
$$
This resolves a conjecture of Bondy and Erdős for large $n$. The proof is analytic in nature, the first step of which is to use the regularity method to relate this problem in Ramsey theory to one in nonlinear optimisation.  This allows us to prove a stability-type generalisation of the above and establish a correspondence between extremal $k$-colourings for this problem and perfect matchings in the $k$-dimensional hypercube $Q_k$.

Tue, 25 Oct 2016
14:30
L6

New bounds for Roth's theorem on arithmetic progressions

Thomas Bloom
(University of Bristol)
Abstract

In joint work with Olof Sisask, we establish new quantitative bounds for Roth's theorem on arithmetic progressions, showing that a set of integers with no three-term arithmetic progressions must have density O(1/(log N)^{1+c}) for some absolute constant c>0. This is the integer analogue of a result of Bateman and Katz for the model setting of vector spaces over a finite field, and the proof follows a similar structure. 

Tue, 18 Oct 2016
14:30
L6

Component sizes in random graphs with given vertex degrees

Svante Janson
(Uppsala University)
Abstract

The threshold for existence of a giant component in a random graph with given vertex degrees was found by Molloy and Reed (1995), and several authors have since studied the size of the largest and other components in various cases. The critical window was found by Hatami and Molloy (2012), and has a width that depends on whether the asymptotic degree distribution has a finite third moment or not. I will describe some new results (joint work with Remco van der Hofstad and Malwina Luczak) on the barely supercritical case, where this difference between finite and infinite third moment also is seen.

Tue, 11 Oct 2016
14:30
L6

Some applications of the p-biased measure to Erdős-Ko-Rado type problems

David Ellis
(Queen Mary University of London)
Abstract

'Erdős-Ko-Rado type problems' are well-studied in extremal combinatorics; they concern the sizes of families of objects in which any two (or any $r$) of the objects in the family 'agree', or 'intersect', in some way.

If $X$ is a finite set, the '$p$-biased measure' on the power-set of $X$ is defined as follows: choose a subset $S$ of $X$ at random by including each element of $X$ independently with probability $p$. If $\mathcal{F}$ is a family of subsets of $X$, one can consider the $p$-biased measure of $\mathcal{F}$, denoted by $\mu_p(\mathcal{F})$, as a function of $p$. If $\mathcal{F}$ is closed under taking supersets, then this function is an increasing function of $p$. Seminal results of Friedgut and Friedgut-Kalai give criteria under which this function has a 'sharp threshold'. Perhaps surprisingly, a careful analysis of the behaviour of this function also yields some rather strong results in extremal combinatorics which do not explicitly mention the $p$-biased measure - in particular, in the field of Erdős-Ko-Rado type problems. We will discuss some of these, including a recent proof of an old conjecture of Frankl that a symmetric three-wise intersecting family of subsets of $\{1,2,\ldots,n\}$ has size $o(2^n)$, and some 'stability' results characterizing the structure of 'large' $t$-intersecting families of $k$-element subsets of $\{1,2,\ldots,n\}$. Based on joint work with (subsets of) Nathan Keller, Noam Lifschitz and Bhargav Narayanan.

Tue, 14 Jun 2016
16:30
L6

Counting Designs

Peter Keevash
(Oxford)
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 1974, Wilson conjectured an approximate formula for the number of such systems. We will outline a proof of this
conjecture, and a more general estimate for the number of Steiner systems. Our main tool is the technique of Randomised Algebraic Construction, which
we introduced to resolve a question of Steiner from 1853 on the existence of designs.

Tue, 14 Jun 2016
14:30
L6

Limits of Some Combinatorial Problems

Endre Csóka
(Budapest)
Abstract

We purify and generalize some techniques which were successful in the limit theory of graphs and other discrete structures. We demonstrate how this technique can be used for solving different combinatorial problems, by defining the limit problems of the Manickam--Miklós--Singhi Conjecture, the Kikuta–Ruckle Conjecture and Alpern's Caching Game.

Tue, 07 Jun 2016
14:30
L6

The Sharp Threshold for Making Squares

Paul Balister
(Memphis)
Abstract

Many of the fastest known algorithms for factoring large integers rely on finding subsequences of randomly generated sequences of integers whose product is a perfect square. Motivated by this, in 1994 Pomerance posed the problem of determining the threshold of the event that a random sequence of N integers, each chosen uniformly from the set
{1,...,x}, contains a subsequence, the product of whose elements is a perfect square. In 1996, Pomerance gave good bounds on this threshold and also conjectured that it is sharp.

In a paper published in Annals of Mathematics in 2012, Croot, Granville, Pemantle and Tetali significantly improved these bounds, and stated a conjecture as to the location of this sharp threshold. In recent work, we have confirmed this conjecture. In my talk, I shall give a brief overview of some of the ideas used in the proof, which relies on techniques from number theory, combinatorics and stochastic processes. Joint work with Béla Bollobás and Robert Morris.

Tue, 17 May 2016
14:30
L6

A Switching Approach to Random Graphs with a Fixed Degree Sequence

Guillem Perarnau
(Birmingham University)
Abstract

For a fixed degree sequence D=(d_1,...,d_n), let G(D) be a uniformly chosen (simple) graph on {1,...,n} where the vertex i has degree d_i. The study of G(D) is of special interest in order to model real-world networks that can be described by their degree sequence, such as scale-free networks. While many aspects of G(D) have been extensively studied, most of the obtained results only hold provided that the degree sequence D satisfies some technical conditions. In this talk we will introduce a new approach (based on the switching method) that allows us to study the random graph G(D) imposing no conditions on D. Most notably, this approach provides a new criterion on the existence of a giant component in G(D). Moreover, this method is also useful to determine whether there exists a percolation threshold in G(D). The first part of this talk is joint work with F. Joos, D. Rautenbach and B. Reed, and the second part, with N. Fountoulakis and F. Joos.

Tue, 10 May 2016
14:30
L6

Finite Reflection Groups and Graph Norms

Joonkyung Lee
(Oxford University)
Abstract

For any given graph H, we may define a natural corresponding functional ||.||_H. We then say that H is norming if ||.||_H is a semi-norm. A similar notion ||.||_{r(H)} is defined by || f ||_{r(H)}:=|| | f | ||_H and H is said to be weakly norming if ||.||_{r(H)} is a norm. Classical results show that weakly norming graphs are necessarily bipartite. In the other direction, Hatami showed that even cycles, complete bipartite graphs, and hypercubes are all weakly norming. Using results from the theory of finite reflection groups, we demonstrate that any graph which is edge-transitive under the action of a certain natural family of automorphisms is weakly norming. This result includes all previous examples of weakly norming graphs and adds many more. We also include several applications of our results. In particular, we define and compare a number of generalisations of Gowers' octahedral norms and we prove some new instances of Sidorenko's conjecture. Joint work with David Conlon.

Tue, 03 May 2016
16:30
L6

Cubic Graphs Embeddable on Surfaces

Michael Mosshammer
(Graz University of Technology)
Abstract

In the theory of random graphs, the behaviour of the typical largest component was studied a lot. The initial results on G(n,m), the random graph on n vertices and m edges, are due to Erdős and Rényi. Recently, similar results for planar graphs were obtained by Kang and Łuczak.


In the first part of the talk, we will extend these results on the size of the largest component further to graphs embeddable on the orientable surface S_g of genus g>0 and see how the asymptotic number and properties of cubic graphs embeddable on S_g are used to obtain those results. Then we will go through the main steps necessary to obtain the asymptotic number of cubic graphs and point out the main differences to the corresponding results for planar graphs. In the end we will give a short outlook to graphs embeddable on surfaces with non-constant genus, especially which results generalise and which problems are still open.

Tue, 03 May 2016
14:30
L6

The Multiplication Table Problem for Bipartite Graphs

Bhargav Narayanan
(Cambridge University)
Abstract

Given a bipartite graph with m edges, how large is the set of sizes of its induced subgraphs? This question is a natural graph-theoretic generalisation of the 'multiplication table problem' of Erdős:  Erdős’s problem of estimating the number of distinct products a.b with a, b in [n] is precisely the problem under consideration when the graph in question is the complete bipartite graph K_{n,n}.

Based on joint work with J. Sahasrabudhe and I. Tomon.

Tue, 08 Mar 2016
14:30
L6

Parking in Trees and Mappings - Enumerative Results and a Phase Change Behaviour

Marie-Louise Lackner
(Technical University of Vienna)
Abstract
Parking functions were originally introduced in the context of a hashing procedure and have since then been studied intensively in combinatorics. We apply the concept of parking functions to rooted labelled trees and functional digraphs of mappings (i.e., functions $f : [n] \to [n]$). The nodes are considered as parking spaces and the directed edges as one-way streets: Each driver has a preferred parking space and starting with this node he follows the edges in the graph until he either finds a free parking space or all reachable parking spaces are occupied. If all drivers are successful we speak about a parking function for the tree or mapping. Via analytic combinatorics techniques we study the total number $F_{n,m}$ and $M_{n,m}$ of tree and mapping parking functions, respectively, i.e. the number of pairs $(T,s)$ (or $(f,s)$), with $T$ a size-$n$ tree (or $f : [n] \to [n]$ an $n$-mapping) and $s \in [n]^{m}$ a parking function for $T$ (or for $f$) with $m$ drivers, yielding exact and asymptotic results. We describe the phase change behaviour appearing at $m=\frac{n}{2}$ for $F_{n,m}$ and $M_{n,m}$, respectively, and relate it to previously studied combinatorial contexts. Moreover, we present a bijective proof of the occurring relation $n F_{n,m} = M_{n,m}$.
Tue, 01 Mar 2016
14:30
L6

Ramsey Classes and Beyond

Jaroslav Nešetřil
(Charles University, Prague)
Abstract

Ramsey classes may be viewed as the top of the line of Ramsey properties. Classical and not so classical examples of Ramsey classes of finite structures were recently extended by many new examples which make the characterisation of Ramsey classes  realistic (and in many cases known). Particularly I will cover recent  joint work with J. Hubicka.
 

Tue, 23 Feb 2016
14:30
L6

Size Ramsey Numbers of Bounded-Degree Triangle-Free Graphs

Rajko Nenadov
(ETH Zurich)
Abstract

The size Ramsey number r'(H) of a graph H is the smallest number of edges in a graph G which is Ramsey with respect to H, that is, such that any 2-colouring of the edges of G contains a monochromatic copy of H. A famous result of Beck states that the size Ramsey number of the path with n vertices is at most bn for some fixed constant b > 0. An extension of this result to graphs of maximum degree ∆ was recently given by Kohayakawa, Rödl, Schacht and Szemerédi, who showed that there is a constant b > 0 depending only on ∆ such that if H is a graph with n vertices and maximum degree ∆ then r'(H) < bn^{2 - 1/∆} (log n)^{1/∆}. On the other hand, the only known lower-bound on the size Ramsey numbers of bounded-degree graphs is of order n (log n)^c for some constant c > 0, due to Rödl and Szemerédi.

Together with David Conlon, we make a small step towards improving the upper bound. In particular, we show that if H is a ∆-bounded-degree triangle-free graph then r'(H) < s(∆) n^{2 - 1/(∆ - 1/2)} polylog n. In this talk we discuss why 1/∆ is the natural "barrier" in the exponent and how we go around it, why we need the triangle-free condition and what are the limits of our approach.

Tue, 16 Feb 2016
14:30
L6

Product-Free Subsets of the Alternating Group

Sean Eberhard
(Oxford University)
Abstract

There is an obvious product-free subset of the symmetric group of density 1/2, but what about the alternating group? An argument of Gowers shows that a product-free subset of the alternating group can have density at most n^(-1/3), but we only know examples of density n^(-1/2 + o(1)). We'll talk about why in fact n^(-1/2 + o(1)) is the right answer, why
Gowers's argument can't prove that, and how this all fits in with a more general 'product mixing' phenomenon. Our tools include some nonabelian Fourier analysis, a version of entropy subadditivity adapted to the symmetric group, and a concentration-of-measure result for rearrangements of inner products.

Tue, 09 Feb 2016
14:30
L6

The Chromatic Number of Dense Random Graphs

Annika Heckel
(Oxford University)
Abstract

The chromatic number of the Erdős–Rényi random graph G(n,p) has been an intensely studied subject since at least the 1970s. A celebrated breakthrough by Bollobás in 1987 first established the asymptotic value of the chromatic number of G(n,1/2), and a considerable amount of effort has since been spent on refining Bollobás' approach, resulting in increasingly accurate bounds. Despite this, up until now there has been a gap of size O(1) in the denominator between the best known upper and lower bounds for the chromatic number of dense random graphs G(n,p) where p is constant. In contrast, much more is known in the sparse case.

In this talk, new upper and lower bounds for the chromatic number of G(n,p) where p is constant will be presented which match each other up to a term of size o(1) in the denominator. In particular, they narrow down the optimal colouring rate, defined as the average colour class size in a colouring with the minimum number of colours, to an interval of length o(1). These bounds were obtained through a careful application of the second moment method rather than a variant of Bollobás' method. Somewhat surprisingly, the behaviour of the chromatic number changes around p=1-1/e^2, with a different limiting effect being dominant below and above this value.

Tue, 02 Feb 2016
14:30
L6

Monochromatic Sums and Products

Ben Green
(Oxford University)
Abstract

Fix some positive integer r. A famous theorem of Schur states that if you partition Z/pZ into r colour classes then, provided p > p_0(r) is sufficiently large, there is a monochromatic triple {x, y, x + y}. By essentially the same argument there is also a monochromatic triple {x', y', x'y'}. Recently, Tom Sanders and I showed that in fact there is a
monochromatic quadruple {x, y, x+y, xy}. I will discuss some aspects of the proof.

Tue, 19 Jan 2016
14:30
L6

Excluding Holes

Paul Seymour
(Princeton)
Abstract

A "hole" in a graph is an induced subgraph which is a cycle of length > 3. The perfect graph theorem says that if a graph has no odd holes and no odd antiholes (the complement of a hole), then its chromatic number equals its clique number; but unrestricted graphs can have clique number two and arbitrarily large chromatic number. There is a nice question half-way between them - for which classes of graphs is it true that a bound on clique number implies some (larger) bound on chromatic number? Call this being "chi-bounded".

Gyarfas proposed several conjectures of this form in 1985, and recently there has been significant progress on them. For instance, he conjectured

  • graphs with no odd hole are chi-bounded (this is true);
  • graphs with no hole of length >100 are chi-bounded (this is true);
  • graphs with no odd hole of length >100 are chi-bounded; this is still open but true for triangle-free graphs.

We survey this and several related results. This is joint with Alex Scott and partly with Maria Chudnovsky.

Tue, 01 Dec 2015
14:30
L6

Cycles in oriented 3-graphs

Imre Leader
(University of Cambridge)
Abstract

It is easy to see that if a tournament (a complete oriented graph) has a directed cycle then it has a directed 3-cycle. We investigate the analogous question for 3-tournaments, and more generally for oriented 3-graphs.

Tue, 24 Nov 2015
14:30
L6

Dirac's Theorem for Hypergraphs

Jie Han
(University of Birmingham)
Abstract

Cycles are fundamental objects in graph theory. A spanning cycle in a graph is also called a Hamiltonian cycle. The celebrated Dirac's Theorem in 1952 shows that every graph on $n\ge 3$ vertices with minimum degree at least $n/2$ contains a Hamiltonian cycle. In recent years, there has been a strong focus on extending Dirac’s Theorem to hypergraphs. We survey the results along the line and mention some recent progress on this problem. Joint work with Yi Zhao.

Tue, 17 Nov 2015
14:30
L6

Large deviations in random graphs

Yufei Zhao
(University of Oxford)
Abstract

What is the probability that the number of triangles in an Erdős–Rényi random graph exceeds its mean by a constant factor? In this talk, I will discuss some recent progress on this problem.

Already the order in the exponent of the tail probability was a long standing open problem until several years ago when it was solved by DeMarco and Kahn, and independently by Chatterjee. We now wish to determine the exponential rate of the tail probability. Thanks for the works of Chatterjee--Varadhan (dense setting) and Chatterjee--Dembo (sparse setting), this large deviations problem reduces to a natural variational problem. We solve this variational problem asymptotically, thereby determining the large deviation rate, which is valid at least for p > 1/n^c for some c > 0.

Based on joint work with Bhaswar Bhattacharya, Shirshendu Ganguly, and Eyal Lubetzky.