Combinatorics Seminar
The seminars are normally held on Fridays at 2-3pm, unless otherwise specified.
Organisers:
Term 1: Hong Liu
Term 1 2019/20
| 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.