Combinatorics Seminar

Organisers:

Term 1 & 2: Hong Liu

Term 2

 Date Name Title Jan 10 TEAM WARWICK Jan 17 Yani Pehova (Warwick) On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem Jan 24 Jaehoon Kim (KAIST) Rainbow subgraphs in graphs Jan 31 Abhishek Methuku (Birmingham) Bipartite Turán problems for ordered graphs Feb 07 Feb 14 Nikolaos Fountoulakis (Birmingham) Feb 21 Olaf Parczyk (LSE) The size-Ramsey number of tight 3-uniform paths Feb 28 Mar 06 Mar 13

Term 1

Date Name Title
Oct 04 Nikhil Srivastava (Berkeley) Girth and Localization of Graph Eigenfunctions
Oct 11 Antonio Girao (Birmingham) Highly linked tournaments
Oct 18 Natasha Morrison (Cambridge) The Typical Structure of sets with Small sumset
Oct 25 George Shakan (Oxford) Some Problems in Additive Combinatorics
Oct 28 Chaim Even-Zohar (Turing) The Distribution of Permutation Patterns and Applications to Data Analysis
Nov 01 Matthew Jenssen (Oxford) Homomorphisms from the torus
Nov 08 Torsten Mutze (Warwick) On Hamilton cycles in highly symmetric graphs
Nov 15 Joel Moreira (Warwick) The Erdos Sumset Conjecture
Nov 22 Istvan Tomon (ETH) Uniform chain partitions and applications
Nov 29 Matija Bucic (ETH) Erdos-Szekeres theorem for multidimensional arrays
Dec 06 Joseph Hyde (Birmingham) A degree sequence Komlos theorem

Girth and Localization of Graph Eigenfunctions (Nikhil Srivastava), 14:00, MS.04

The extreme eigenvectors of graphs play a central role in spectral graph theory, corresponding to sparse cuts and colorings. We study the combinatorial meaning of the interior eigenvectors. Brooks and Lindenstrauss showed that if any eigenvector of the adjacency matrix of a $d$-regular graph has a large fraction of its mass on a few coordinates, then it must contain a short cycle; we sharpen their results, and complement this with a construction showing that our
improved bound on the length of the cycle is essentially optimal, thus precisely quantifying the interplay between localization of eigenvectors and girth in regular graphs.

Highly linked tournaments (Antonio Girao), 14:00, MS.04

Pokrovskiy conjectured that there is a function $f: \mathbb{N} \rightarrow \mathbb{N}$ such that any $2k$-strongly-connected tournament with minimum out and in-degree at least $f(k)$ is $k$-linked. In this talk, we shall discuss a recent result which states that every $(2k + 1)$-strongly-connected tournament with minimum out-degree at least $poly(k)$ is $k$-linked, thus resolving the conjecture up to the additive factor of $1$ in the connectivity bound, but without the extra assumption that the minimum in-degree is large. Moreover, we shall show the condition on high minimum out-degree is really necessary, by constructing arbitrarily large tournaments which are $2.5k$-strongly-connected tournaments but which are not $k$-linked. This is in close connection to the situation for undirected graphs, where Bollobas and Thomason showed that any $2k$-connected graph which has average degree at least $22k$ is $k$-linked.

The Typical Structure of sets with Small sumset (Natasha Morrison), 14:00, MS.04

One of the central objects of interest in additive combinatorics is the sumset $A + B := \{ a+b : a \in A, \, b \in B \}$ of two sets $A,B \subset \mathbb{Z}$.
Our main theorem, which improves results of Green and Morris, and of Mazur, implies that the following holds for every fixed $\lambda > 2$ and every $k \ge (\log n)^4$: if $\omega \to \infty$ as $n \to \infty$ (arbitrarily slowly), then almost all sets $A \subset [n]$ with $|A| =k$ and $|A + A| \le \lambda k$ are contained in an arithmetic progression of length $\lambda k/2 + \omega$. This is joint work with Marcelo Campos, Mauricio Collares, Rob Morris and Victor Souza.

Some Problems in Additive Combinatorics (George Shakan), 14:00, MS.04

We discuss a variety of topics including the sum-product problem, Sumsets in high dimensions, Sidon sets, distinct consecutive differences, and non-linear Roth-type theorems. Our focus will be on techniques and open problems. The talk will include some previous and ongoing (joint) works of the speaker.

The Distribution of Permutation Patterns and Applications to Data Analysis (Chaim Even Zohar), 14:00, B3.02

Consider a random sample of n points in the xy-plane. Generically, the order relations in such a data set induce a permutation of size n, and every subset of k points induces one of k! possible "patterns" that occur in this permutation. How frequently does each pattern occur? How efficiently can we count these occurrences? What do they tell us about the global properties of our data?

The distribution of the k!-dimensional vector of pattern densities in a uniformly random permutation was studied by Janson, Nakamura, and Zeilberger (2015). Their analysis showed that some component of this vector is asymptotically multinormal of order 1/sqrt(n), while the orthogonal component is smaller. Using representations of the symmetric group, and the theory of U-statistics, we refine the analysis of this distribution. We show that it decomposes into k asymptotically uncorrelated components of different orders in n.

Homomorphisms from the torus (Matthew Jenssen), 14:00, MS.04

We present a detailed probabilistic and structural analysis of the set of weighted homomorphisms from the discrete torus Z_m^n, where m is even, to any fixed graph. We show that the corresponding probability distribution on such homomorphisms is close to a distribution defined constructively as a certain random perturbation of some "dominant phase". This has several consequences, including solutions (in a strong form) to conjectures of Engbers and Galvin and a conjecture of Kahn and Park. Special cases include sharp asymptotics for the number of independent sets and the number of proper q-colourings of Z_m^n (so in particular, the discrete hypercube). For the proof we develop a `Cluster Expansion Method', which we expect to have further applications, by combining machinery from statistical physics, entropy and graph containers. This is joint work with Peter Keevash.

On Hamilton cycles in highly symmetric graphs (Torsten Mutze), 14:00, MS.04

The question whether a graph has a Hamilton cycle or not is one of the oldest and most fundamental graph-theoretic problems, and one of the prototypical NP-complete problems. In this talk I will survey some recent results on Hamilton cycles in different families of highly symmetric graphs. The starting point is our proof of the middle levels conjecture, and various other long-standing problems that we settled subsequently, including the Hamiltonicity of bipartite Kneser, of sparse Kneser graphs, and cycles through any range of consecutive levels of the hypercube. I will highlight how these constructions and problems link several well-known concepts in combinatorics and algorithms.

The Erdos Sumset Conjecture (Joel Moreira), 14:00, MS.04

A conjecture of Erdos states that every set of natural numbers with positive density contains the (arithmetic) sum B+C of two infinite sets B and C of natural numbers. In joint work with Florian Richter and Donald Robertson we recently verified this conjecture, borrowing some ideas from ergodic theory. I will talk about this and related questions, several of which are still open, and then explain the main ideas that go into the proof.

Uniform chain partitions and applications (Istvan Tomon), 14:00, MS.04

A cornerstone result in extremal set theory is the theorem of Sperner (1928) which tells us that the size of the largest antichain in the Boolean lattice $2^{[n]}$ is $\binom{n}{\lfloor n/2\rfloor}$, which, by Dilworth's theorem, is equal to the minimum number of chains $2^{[n]}$ can be partitioned into. While the maximal sized antichain is more or less unique, there are many different ways to partition $2^{[n]}$ into the minimum number of chains. Addressing a conjecture of Furedi (1986), we show that there exists a chain decomposition into the minimum number of chains such that almost all chains have roughly the same size. Furthermore, we discuss how such chain decompositions can be used to prove certain problems in extremal set theory. This is joint work with Benny Sudakov and Adam Zsolt Wagner.

Erdos-Szekeres theorem for multidimensional arrays (Matija Bucic), 14:00, MS.04

The classical Erdos-Szekeres theorem dating back almost a hundred years states that any sequence of $(n-1)^2+1$ distinct real numbers contains a monotone subsequence of length $n$. This theorem has been generalised to higher dimensions in a variety of ways but perhaps the most natural one was proposed by Fishburn and Graham more than 25 years ago. They defined the concept of a monotone and a lex-monotone array and asked how large an array one needs in order to be able to find a monotone or a lex-monotone subarray of size $n \times \ldots \times n$. Fishburn and Graham obtained Ackerman-type bounds in both cases. We significantly improve these results. Regardless of the dimension we obtain at most a triple exponential bound in $n$ in the monotone case and a quadruple exponential one in the lex-monotone case. This is joint work with Benny Sudakov and Tuan Tran.

A degree sequence Komlos theorem (Joseph Hyde), 14:00, MS.04

Given graphs $G$ and $H$, we define an $H$-tiling in $G$ to be a collection of vertex-disjoint copies of $H$ in $G$. Let $$\eta > 0$$. We call an $$H$$-tiling perfect if it covers all of the vertices in $$G$$ and $$\eta$$-almost perfect if it covers all but at most an $$\eta$$-proportion of the vertices in $$G$$. An important theorem of Komlos provides the minimum degree of $$G$$ which ensures an $$\eta$$-almost perfect $$H$$-tiling in $$G$$. We present a degree sequence strengthening of this result and provide a proof sketch. This is joint work with Hong Liu and Andrew Treglown.

Using the aforementioned theorem of Komlos, Kuhn and Osthus determined the minimum degree of $$G$$ that ensures a perfect $$H$$-tiling in $$G$$. We present a degree sequence version of their result as an application of our degree sequence Komlos theorem. This is joint work with Andrew Treglown.

On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem (Yani Pehova), 14:00, MS.04

A classical theorem of Hajnal and Szemerédi states that if an $n$-vertex graph $G$ has minimum degree at least $(1-1/r)n$, then it contains a $K_r$-factor (that is, $n/r$ vertex-disjoint copies of $K_r$), provided $r$ divides $|G|$. Extremal examples for this result, however, contain large independent sets. Forbidding these extremal structures is likely to decrease the minimum degree condition required to force a $K_r$-factor, and indeed a result of Balogh, Molla and Sharifzadeh shows that if the independence number of $G$ is sublinear, then minimum degree slightly above $n/2$ suffices to force a triangle-factor. We prove an extension of this result for general $K_r$-factors and graphs of sublinear independence number, and go over a recent improvement of our bound due to Su and Knierim. This is joint work with Rajko Nenadov.

Rainbow subgraphs in graphs (Jaehoon Kim), 14:00, MS.04

We say a subgraph $H$ of an edge-colored graph is rainbow if all edges in $H$ has distinct colors. The concept of rainbow subgraphs generalizes the concept of transversals in Latin squares. In this talk, we discuss how these concepts are related and we introduce a result regarding approximate decompositions of graphs into rainbow subgraphs. This has implications on transversals in Latin square. It is a joint work with K\"uhn, Kupavskii and Osthus.

Bipartite Tur\'an problems for ordered graphs (Abhishek Methuku), 14:00, MS.04
A zero-one matrix $M$ contains a zero-one matrix $A$ if one can delete rows and columns of $M$, and turn 1-entries into 0-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted by $ex(n,A)$, is the maximum number of $1$-entries in an $n\times n$ sized matrix $M$ that does not contain $A$.
A matrix $A$ is column-$t$-partite (or row-$t$-partite), if it can be cut along the columns (or rows) into $t$ submatrices such that every row (or column) of these submatrices contains at most one $1$-entry. We prove that if $A$ is column-$t$-partite, then $ex(n,A)<n^{2-\frac{1}{t}+\frac{1}{2t^{2}}+o(1)}$, and if $A$ is both column- and row-$t$-partite, then $ex(n,A)<n^{2-\frac{1}{t}+o(1)}$. Our proof combines a novel density-increment-type argument with the celebrated dependent random choice method.
Results about the extremal numbers of zero-one matrices translate into results about the Tur\'an numbers of bipartite ordered graphs. In particular, a zero-one matrix with at most $t$ 1-entries in each row corresponds to an ordered graph with maximum degree $t$ in one of its vertex classes. The aim of this talk is to establish general results about the extremal numbers of ordered graphs. Our results are partially motivated by a well known result of F\"uredi (1991) and Alon, Krivelevich, Sudakov (2003) stating that if $H$ is a bipartite graph with maximum degree $t$ in one of the vertex classes, then $ex(n,H)=O(n^{2-\frac{1}{t}})$. This is joint work with Istvan Tomon.

The size-Ramsey number of tight 3-uniform paths (Olaf Parczyk), 14:00, MS.04

Given a hypergraph $H$, the size-Ramsey number is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges with the property that in any colouring of the edges of $G$ with two colours there is a monochromatic copy of $H$. Extending on results for graphs we prove that the size Ramsey number of the $3$-uniform tight path on $n$ vertices is linear in $n$.

This is joint work with Jie Han, Yoshiharu Kohayakawa, and Guilherme Mota.