The seminars are now held on Wednesday at 2-3pm.

Zoom Meeting ID: 830 9689 8964

Password: WC2020

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.

Paradoxical Colouring Rules (Robert Simon), 14:00, Online

A colouring rule on a probability space is paradoxical if there a way to colour the space according to the rule but no way to do so that is measurable with respect to any finitely additive extension of the probability measure. We show that a paradoxical colouring induces a weak form of paradoxical decomposition, explore some examples and open problems.

Lipschitz bijections between boolean functions (Thomas Johnston), 14:00, Online

A frequent theme in the analysis of boolean functions is the study of the similarities and differences between boolean functions with different geometric or structural properties; for example, between functions such as Dictator that are determined by a small number of coordinates, and functions such as Majority or XOR that are not. One measure of similarity, introduced by Rao and Shinkar in 2018, is the existence of a Lipschitz mapping (with small constant) between them.

In this talk, we answer two questions posed by Rao and Shinkar.

- We show that there is no O(1)-bi-Lipschitz bijection from Dictator to XOR such that each output bit depends on O(1) input bits.

- We show that with high probability there is a O(1)-bi-Lipschitz mapping from Dictator to a uniformly random balanced function.

Joint work with Alex Scott.

Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor (Sergey Norin), 14:00 Online

Hadwiger's conjecture from 1943 states that every simple graph with no $K_t$ minor can be properly colored using $t-1$ colors. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable. We will discuss recent joint work with Luke Postle and Zi-Xia Song, which shows that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > 1/4$. This is the first improvement on the order of magnitude of the Kostochka-Thomason bound. We will also discuss the extensions of this result to list-coloring and to odd minors.

Classifying translation-closed set systems with bounded VC-dimension (Olof Sisask), 14:00 Online

The notion of the VC-dimension of a set system, named for Vapnik and Chervonenkis, is a classical concept that has turned out to be interesting in all kinds of contexts, such as computational geometry, probability and machine learning. A key use of the concept in machine learning lies in the prevention of overfitting: if a collection of subsets of R^n has small VC-dimension -- for example the collection of all halfspaces -- then a set in the collection that classifies a small random sample of the data well, will with high probability also classify the full data set well. The set system of classifiers is often a collection of subsets of an abelian group that is closed under translation. We shall present some results towards classifying such set systems in the context of finite abelian groups, hopefully indicating the underlying probabilistic reason bounded VC-dimension is useful. Prior familiarity with VC-dimension should not be necessary.

Greedy maximal independent sets via local limits (Peleg Michaeli), 14:00, Online

The random greedy algorithm for finding a maximal independent set in a graph has been studied extensively in various settings in combinatorics, probability, computer science — and even in chemistry. The algorithm builds a maximal independent set by inspecting the vertices of the graph one at a time according
to a random order, adding the current vertex to the independent set if it is not connected to any previously added vertex by an edge.

In this talk I will present a natural and general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of
(possibly random) graphs, involving a useful notion of local convergence. We use this framework both to give short and simple proofs for results on
previously studied families of graphs, such as paths and binomial random graphs, and to give new results for other models such as random trees.

If time allows, I will discuss a more delicate result, according to which in expectation, the cardinality of a random greedy independent set in the path is
no larger than that in any other tree of the same order.

The talk is based on a joint work with Michael Krivelevich, Tamás Mészáros and Clara Shikhelman.

Structures of sets with minimal measure growth (Yifan Jing), 14:00 Online

Let $G$ be a connected unimodular group and let $\mu_G$ be a Haar measure on $G$. Kemperman showed that for compact $A$ and $B$ in $G$, $\mu_G(AB) \geq \min(\mu_G(A) + \mu_G(B), \mu_G(G)).$ This implies that the $n$-fold product $A^n$ of $A$ has $\mu_G( A^n) \geq \min(n\mu_G(A),\mu_G(G))$ and when $G$ is not compact, $\lim_{n \to \infty} \mu_G( A^n)/ (n \mu_G(A)) \geq 1$. We obtain simple classifications of $G$, $A$, and $B$ such that the equalities hold, answering a question asked by Kemperman in 1964. We also get near equality versions of the above results with explicit bound for compact $G$, confirming conjectures made by Griesmer and by Tao. Our strategy of proof involves reducing the problem to Lie groups through the use of an argument inspired by Breuillard--Green--Tao's classification of approximate groups via Hrushovski's Lie model theorem, and then developing new techniques to reduce the Lie group problem to the case of tori. This is joint work with Minh Tran.

Hitting time of disjoint Hamilton cycles in random subgraph processes (Yahav Alon), 14:00, Online

Consider a random graph process, in which edges are added to an empty graph consecutively in a uniformly chosen random order. A classical result by Bollobás and Frieze state that at the first moment the graph no longer contains vertices of degree less than 2k, it also typically contains k edge disjoint Hamilton cycles.

We extend this result to random subgraph processes, in which only edges of a given base graph are added, for certain families of dense base graphs.

Based on a joint work with Michael Krivelevich.

The Turán number of blow-ups of trees (Andrzej Grzesik), 14:00, Online

A conjecture of Erdős from 1967 asserts that any graph on $n$ vertices which does not contain a fixed $r$-degenerate bipartite graph $F$ has at most $Cn^{2−1/r}$ edges, where $C$ is a constant depending only on $F$. We show that this bound holds for a large family of $r$-degenerate bipartite graphs, including all $r$-degenerate blow-ups of trees. Our results generalize many previously proven cases of the Erdős conjecture, including the related results of Furedi and Alon, Krivelevich and Sudakov. Joint work with Oliver Janzer and Zoltán Lóránt Nagy.

Extremal problems concerning the traces of sets (Bjarne Schülke), 14:00, Online

Given two non-negative integers $n$ and $s$, define $m(n,s)$ to be the maximal number such that in every hypergraph $\mathcal{H}$ on $n$ vertices and with at most $ m(n,s)$ edges there is a vertex $x$ such that $\vert\mathcal{H}_x\vert\geq \vert E(\mathcal{H})\vert -s$, where $\mathcal{H}_x=\{H\setminus\{x\}:H\in E(\mathcal{H})\}$.
This problem has been posed by Füredi and Pach and by Frankl and Tokushige. While the first results were only for specific small values of $s$, Frankl determined $m(n,2^{d-1}-1)$ for all $d$ with $d\mid n$. Subsequently, the goal became to determine $m(n,2^{d-1}-c)$ for larger $c$. Frankl and Watanabe determined $m(n,2^{d-1}-c)$ for $c\in\{0,2\}$ and $d\mid n$. Other general results are not known so far.

Our main result sheds light on what happens further away from powers of two: We prove that $m(n,2^{d-1}-c)=\frac{n}{d}(2^d-c)$ for $d\geq 4c$ and $d\mid n$ and give an example showing that this formula does not hold for $c=d+1$. The other line of research on this problem is to determine $m(n,s)$ for small values of $s$. Our second result determines $m(n,2^{d-1}-c)$ for $c\in\{3,4\}$ for all $d$ with $d\mid n$. This solves more instances of the problem for small $s$ and in particular solves a conjecture by Frankl and Watanabe.

This is joint work with Simón Piga.