The seminars are normally held on Fridays at 2-3pm at MS.04, unless otherwise specified.

Organisers:

Term 1 & 2 & 3: Hong Liu

Term 3

Term 2

Term 1

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

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.

Self-avoiding walks on hyperbolic graphs (Christoforos Panagiotis), 14:00, MS.04

The self-avoiding walk (graph-theoretic term: path) is a model of interest both in mathematics and in physics. It has been studied extensively on Euclidean lattices but over the last few decades, the study of self-avoiding walk on non-Euclidean lattices has received increasing attention. In this talk, we will consider the case of regular tessellations of the hyperbolic plane. We will show that there are exponentially fewer self-avoiding polygons (graph-theoretic term: cycles) than self-avoiding walks, and we will deduce that self-avoiding walk is ballistic.

Evolving inhomogeneous random graphs (Nikolaos Fountoulakis), 14:00, MS.04

In this talk, we will consider growing random structures which generalise the preferential attachment mechanism.
Vertices arriving one-at-a-time are equipped with a random fitness and the location they attach to is random, but its distribution is determined by a small number (but more than 1) of vertices in the vicinity. Our results have to do with the degree profile of such a random structure.
This is joint work with Tejas Iyer, Cécile Mailler and Henning Sulzbach.

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.

Ramsey upper density of infinite graphs (Ander Lamaison Vidarte), 14:00, MS.04

Let $H$ be an infinite graph. In a two-coloring of the edges of the complete graph on the natural numbers, what is the densest monochromatic subgraph isomorphic to H that we are guaranteed to find? We measure the density of a subgraph by the upper density of its vertex set. This question, in the
particular case of the infinite path, was introduced by Erdős and Galvin. Following a recent result for the infinite path, we present bounds on the
maximum density for other choices of H, including exact values for a wide class of bipartite graphs.

Exact stability for Turán's theorem (Daniel Korandi), 14:00, MS.04

Turán's theorem says that an extremal $K_{r+1}$-free graph is $r$-partite. The Stability Theorem of Erdős and Simonovits shows that if a $K_{r+1}$-free graph with $n$ vertices has close to the maximal $t_r(n)$ edges, then it is close to being $r$-partite.
In this talk we determine exactly the $K_{r+1}$-free graphs with at least $m$ edges that are farthest from being $r$-partite, for any $m > t_r(n) - \delta n^2$. This extends work by Erdős, Győri and Simonovits, and proves a conjecture of Balogh, Clemen, Lavrov, Lidický and Pfender.
Joint work with Alexander Roberts and Alex Scott.

Ramsey games near the critical threshold (Shagnik Das), 14:00, MS.04

A well-known result of Rödl and Ruciński states that for any graph $H$ there exists a constant $C$ such that if $p \ge C n^{-1/m_2(H)}$, then the random graph $G(n,p)$ is a.a.s. $H$-Ramsey, that is, any 2-colouring of its edges contains a monochromatic copy of $H$. Aside from a few simple exceptions, the corresponding 0-statement also holds; that is, there exists $c>0$ such that if $p\le c n^{-1/m_2(H)}$ the random graph $G(n,p)$ is a.a.s. not $H$-Ramsey.
We show that near this threshold, even when $G(n,p)$ is not $H$-Ramsey, it is often extremely close to being $H$-Ramsey. More precisely, we prove that for any constant $c > 0$ and any strictly 2-balanced graph $H$, if $p \ge c n^{-1/m_2(H)}$, then the random graph $G(n,p)$ a.a.s. has the property that every 2-edge-colouring without monochromatic copies of $H$ cannot be extended to an $H$-free colouring after a superlinear number of additional random edges are added. This addresses a question raised by Friedgut, Kohayakawa, Rödl, Ruciński and Tetali, who in 2002 proved the same statement for triangles. We also provide examples to show that these theorems need not hold when $H$ is not strictly 2-balanced, and further provide results in the 3-coloured setting.
This is joint work with David Conlon, Joonkyung Lee, and Tamás Mészáros.

Coordinate Deletion (Eero Raty), 14:00, MS.04

For a family $A$ in $\{0,...,k\}^n$, its deletion shadow is the set obtained from $A$ by deleting from any of its vectors one coordinate. Given the size of $A$, how should we choose $A$ to minimise its deletion shadow? And what happens if instead we may delete only a coordinate that is zero? We discuss these problems, and give an exact solution to the second problem.