Past Combinatorial Theory Seminar

3 May 2016
14:30
Bhargav Narayanan
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.

  • Combinatorial Theory Seminar
8 March 2016
14:30
Marie-Louise Lackner
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}$.
  • Combinatorial Theory Seminar
1 March 2016
14:30
Jaroslav Nešetřil
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.
 

  • Combinatorial Theory Seminar
23 February 2016
14:30
Rajko Nenadov
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.

  • Combinatorial Theory Seminar
16 February 2016
14:30
Sean Eberhard
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.

  • Combinatorial Theory Seminar
9 February 2016
14:30
Annika Heckel
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.

  • Combinatorial Theory Seminar
2 February 2016
14:30
Ben Green
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.

  • Combinatorial Theory Seminar
19 January 2016
14:30
Paul Seymour
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.

  • Combinatorial Theory Seminar
24 November 2015
14:30
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.

  • Combinatorial Theory Seminar

Pages