Past Combinatorial Theory Seminar

6 June 2017
14:30
Paul Russell
Abstract

It is well known that there is a finite colouring of the natural numbers such that there is no infinite set X with X+X (the pairwise sums from X, allowing repetition) monochromatic. It is easy to extend this to the rationals. Hindman, Leader and Strauss showed that there is also such a colouring of the reals, and asked if there exists a space 'large enough' that for every finite colouring there does exist an infinite X with X+X monochromatic. We show that there is indeed such a space. Joint work with Imre Leader.

  • Combinatorial Theory Seminar
30 May 2017
14:30
Abstract

A central theorem in combinatorics is Sperner’s Theorem, which determines the maximum size of a family in the Boolean lattice that does not contain a 2-chain. Erdos later extended this result and determined the largest family not containing a k-chain. Erdos and Katona and later Kleitman asked how many such chains must appear in families whose size is larger than the corresponding extremal result.

This question was resolved for 2-chains by Kleitman in 1966, who showed that amongst families of size M in the Boolean lattice, the number of 2-chains is minimized by a family whose sets are taken as close to the middle layer as possible. He also conjectured that the same conclusion should hold for all k, not just 2. The best result on this question is due to Das, Gan and Sudakov who showed roughly that Kleitman’s conjecture holds for families whose size is at most the size of the k+1 middle layers of the Boolean lattice. Our main result is that for every fixed k and epsilon, if n is sufficiently large then Kleitman’s conjecture holds for families of size at most (1-epsilon)2^n, thereby establishing Kleitman’s conjecture asymptotically (in a sense). Our proof is based on ideas of Kleitman and Das, Gan and Sudakov.

Joint work with Jozsef Balogh.

  • Combinatorial Theory Seminar
16 May 2017
14:30
Tao Jiang
Abstract

Many extremal results on cycles use what may be called BFS method, where a breath first search tree is used as a skeleton to build desired structures. A well-known example is the Bondy-Simonovits theorem that every n-vertex graph with more than 100kn^{1+1/k} edges contains an even cycle of length 2k. The standard BFS method, however, is not easily applicable for supersaturation problems where one wishes to show the existence of many copies of a given  subgraph. The method is also not easily applicable in the hypergraph setting.

In this talk, we focus on some variants of the standard BFS method. We use one of these in conjunction with some useful general reduction theorems that we develop to establish the supersaturation of loose (linear) even cycles in linear hypergraphs. This extends Simonovits' supersaturation theorem on even cycles in graphs. This is joint work with Liana Yepremyan.

If time allows, we will also discuss another variant (joint with Jie Ma) used in the study of Berge cycles of consecutive lengths in hypergraphs.

  • Combinatorial Theory Seminar
2 May 2017
14:30
Natasha Morrison
Abstract

The $r$-neighbour bootstrap process on a graph $G$ starts with an initial set of "infected" vertices and, at each step of the process, a healthy vertex becomes infected if it has at least $r$ infected neighbours (once a vertex becomes infected, it remains infected forever). If every vertex of $G$ becomes infected during the process, then we say that the initial set percolates.

In this talk I will discuss the proof of a conjecture of Balogh and Bollobás: for fixed $r$ and $d\to\infty$, the minimum cardinality of a percolating set in the $d$-dimensional hypercube is $\frac{1+o(1)}{r}\binom{d}{r-1}$. One of the key ideas behind the proof exploits a connection between bootstrap percolation and weak saturation. This is joint work with Jonathan Noel.

  • Combinatorial Theory Seminar
25 April 2017
14:30
Marthe Bonamy
Abstract

The chromatic number of a graph is trivially bounded from above by the maximum degree plus one, and from below by the size of a largest clique. Reed proved in 1998 that compared to the trivial upper bound, we can always save a number of colors proportional to the gap between the maximum degree and the size of a largest clique. A key step in the proof deals with how to spare colors in a graph whose every vertex "sees few edges" in its neighborhood. We improve the existing approach, and discuss its applications to Reed's theorem and strong edge coloring.  This is joint work with Thomas Perrett (Technical University of Denmark) and Luke Postle (University of Waterloo).

  • Combinatorial Theory Seminar
7 March 2017
14:30
Andrew Treglown
Abstract

Given two $k$-graphs $H$ and $F$, a perfect $F$-packing in $H$ is a collection of vertex-disjoint copies of $F$ in $H$ which together cover all the vertices in $H$. In the case when $F$ is a single edge, a perfect $F$-packing is simply a perfect matching. For a given fixed $F$, it is generally the case that the decision problem whether an $n$-vertex $k$-graph $H$ contains a perfect $F$-packing is NP-complete.

In this talk we describe a general tool which can be used to determine classes of (hyper)graphs for which the corresponding decision problem for perfect $F$-packings is polynomial time solvable. We then give applications of this tool. For example, we give a minimum $\ell$-degree condition for which it is polynomial time solvable to determine whether a $k$-graph satisfying this condition has a perfect matching (partially resolving a conjecture of Keevash, Knox and Mycroft). We also answer a question of Yuster concerning perfect $F$-packings in graphs.

This is joint work with Jie Han (Sao Paulo).
 

  • Combinatorial Theory Seminar
7 February 2017
14:30
Stefan Glock
Abstract

In a recent breakthrough, Peter Keevash proved the Existence conjecture for combinatorial designs, which has its roots in the 19th century. In joint work with Daniela Kühn, Allan Lo and Deryk Osthus, we gave a new proof of this result, based on the method of iterative absorption. In fact, `regularity boosting’ allows us to extend our main decomposition result beyond the quasirandom setting and thus to generalise the results of Keevash. In particular, we obtain a resilience version and a minimum degree version. In this talk, we will present our new results within a brief outline of the history of the Existence conjecture and provide an overview of the proof.

  • Combinatorial Theory Seminar
31 January 2017
14:30
Abstract

We will consider the following deceptively simple question, formulated recently by Po Shen Loh who connected it to an open problem in Ramsey Theory. Define the '2-less than' relation on the set of triples of integers by saying that a triple x is 2-less than a triple y if x is less than y in at least two coordinates. What is the maximal length of a sequence of triples taking values in {1,...,n} which is totally ordered by the '2-less than' relation?

In his paper, Loh uses the triangle removal lemma to improve slightly on the trivial upper bound of n^2, and conjectures that the truth should be of order n^(3/2). The gap between these bounds has proved to be surprisingly resistant. We shall discuss joint work with Tim Gowers, giving some developments towards this conjecture and a wide array of natural extensions of the problem. Many of these extensions remain open.
 

  • Combinatorial Theory Seminar
24 January 2017
14:30
Jakub Konieczny
Abstract

The Thue-Morse sequence is perhaps the simplest example of an automatic sequence. Various pseudorandomness properties of this sequence have long been studied. During the talk, I will discuss a new result in this direction, asserting that the Gowers uniformity norms of the Thue-Morse sequence are small in a quantitative sense. Similar results hold for the Rudin-Shapiro sequence, as well as for a much wider class of automatic sequences which will be introduced during the talk.

The talk is partially based on joint work with Jakub Byszewski.

  • Combinatorial Theory Seminar

Pages