Past 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
17 January 2017
14:30
Michał Przykucki
Abstract

Consider the following particle system. We are given a uniform random rooted tree on vertices labelled by $[n] = \{1,2,\ldots,n\}$, with edges directed towards the root. Each node of the tree has space for a single particle (we think of them as cars). A number $m \le n$ of cars arrive one by one, and car $i$ wishes to park at node $S_i$, $1 \le i \le m$, where $S_1, S_2, \ldots, S_m$ are i.i.d. uniform random variables on $[n]$. If a car wishes to park at a space which is already occupied, it follows the unique path oriented towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves the tree. Let $A_{n,m}$ denote the event that all $m$ cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Set $m = \lfloor \alpha n \rfloor$. Then if $\alpha \le 1/2$, $\mathbb{P}(A_{n,\lfloor \alpha n \rfloor}) \to \frac{\sqrt{1-2\alpha}}{1-\alpha}$, whereas if $\alpha > 1/2$ we have $\mathbb{P}(A_{n,\lfloor \alpha n \rfloor}) \to 0$. In this talk, we will give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method.

Joint work with Christina Goldschmidt.

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

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

  • Combinatorial Theory Seminar
15 November 2016
14:30
Eoin Long
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.

  • Combinatorial Theory Seminar
8 November 2016
14:30
Liana Yepremyan
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.

  • Combinatorial Theory Seminar
1 November 2016
14:30
Matthew Jenssen
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$.

  • Combinatorial Theory Seminar
25 October 2016
14:30
Thomas Bloom
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. 

  • Combinatorial Theory Seminar

Pages