Abstracts of past talks

• 22 April 2024 - Cédric Pilatte (University of Oxford)

  Improved bounds for Chowla's conjecture with logarithmic weights

  
  

  The Liouville function $\lambda(n)$ is defined to be +1 if n is a product of an even number of primes, and -1 otherwise. In many ways, the Liouville function is expected to behave like a random sequence of +1’s and -1’s. Instances of this phenomenon are intimately connected with the distribution of primes. For instance, the statement that the partial sums of the Liouville function grow no faster than $x^{1/2+\epsilon}$ is equivalent to the Riemann Hypothesis. The two-point Chowla conjecture predicts that the average of $\lambda(n)\lambda(n+1)$ over $n\leq x$ tends to zero as $x\to \infty$. I will present my work on a logarithmically weighted version of this problem. The proof uses elementary combinatorics to study a graph encoding number-theoretic information.

  
  

• 18 March 2024 - Alp Müyesser (UCL)

  Approximate path decompositions of regular graphs

  
  

  We show that any $d$-regular graph can be approximately decomposed into paths of length almost $d$, giving an approximate solution to a problem of Kotzig from 1957. Along the way, we also show that almost all vertices of a $d$-regular graph can be partitioned into $n/(d+1)$ paths, asymptotically confirming a conjecture of Magnant and Martin from 2009.

  This is joint work with Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov.

  
  

• 11 March 2024 - Alexandra Wesolek (Technische Universität Berlin)

  Extremal graphs in the generalized Turán problem

  
  

  One of the first results in extremal graph theory is Turán’s theorem, which states that the Turán graph $T(n,r)$ maximizes the number of edges in an $n$-vertex graph that does not contain $K_{r+1}$ as a subgraph. More generally, given two graphs $H$ and $F$, the generalized Turán number $ex(n, H, F)$ is the largest number of copies of $H$ in an $n$-vertex $F$-free graph and such graphs with $ex(n, H, F)$ copies of $H$ are called extremal graphs. For fixed $H$, $F=K_{r+1}$ and $r$ large enough, we recently showed in a joint work with Morrison, Nir, Norine, and Rzążewski, that the extremal graph for the generalized Turán problem is the Turán graph $T(n,r)$. This talk discusses this result and more broadly, results on generalized Turán numbers.

  
  

• 4 March 2024 - Nemanja Draganić (University of Oxford)

  Hamiltonicity of expanders - optimal bounds and applications

  
  

  An $n$-vertex graph $G$ is a $C$-expander if $|N(X)|\geq C|X|$ for every $X \subseteq V(G)$ with $|X|< n/2C$ and there is an edge between every two disjoint sets of at least $n/2C$ vertices. We show that there is some constant $C>0$ for which every $C$-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in $(n,d,\lambda)$-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications.

  Joint work with R. Montgomery, D. Munhá Correia, A. Pokrovskiy and B. Sudakov.

  
  

• 26 February 2024 - Francesco Di Braccio (The London School of Economics)

  Hamilton decompositions of regular tripartite tournaments

  
  

  A regular $k$-partite tournament is a regular orientation of the balanced complete $k$-partite graph. Kühn and Osthus proved that for all $k \ge 4$ any large enough regular $k$-partite tournament can be decomposed into edge-disjoint Hamilton cycles and conjectured the same to be true for all $k$. Granet proved the conjecture for $k=2$ and, somewhat surprisingly, gave a construction of a non-Hamilton decomposable regular tripartite tournament. Our main result is a proof that an approximate version of the conjecture still holds for $k=3$, i.e. that in each such large tournament one may find edge-disjoint Hamilton cycles covering all but $o(n^2)$ edges. We also prove that if $a > 1/3$, any balanced regular tripartite digraph with minimum semidegree at least $a*n$ is Hamilton decomposable.

  This is based on joint work with J. Lada, V. Patel, Y. Pehova, J. Skokan.

  
  

• 19 February 2024 - Richard Lang (University of Hamburg)

  Dirac-type problems in hypergraphs

  
  

  The question under which minimum degree conditions a given hypergraph contains a Hamilton cycle has received a lot of attention over the past twenty years. In this talk, I will give an overview of the progress in the area and then present some new results.

  
  

• 5 February 2024 - Maksim Zhukovskii (University of Sheffield)

  Stability of large cuts in random graphs

  
  

  We prove that the family of largest cuts in the binomial random graph exhibits the following stability property: with high probability, there is a set of $(1-o(1))n$ vertices that is partitioned in the same manner by all maximum cuts. We also show some applications of this property - in particular, to the validity of Simonovits’s property in binomial random graphs. Recall that a graph is $H$-Simonovits, if each of its largest $H$-free subgraphs is $(\chi(H)−1)$-partite.

  The talk is based on joint work with Ilay Hoshen and Wojciech Samotij

  
  

• 29 January 2024 - Bhavik Mehta (University of Cambridge)

  Formalising Ramsey Theory

  
  

  In March 2023, Campos et al proved the first exponential improvement to the upper bound on Ramsey’s theorem in the two-colour case, showing R(k) <= (4 - c)^k for a positive constant c. I will discuss the complete formalisation of this result in the Lean theorem prover, and touch on the verification of related Ramsey theory problems. Knowledge of neither the Campos et al paper nor Lean is required.

  
  

• 22 January 2024 - Debsoumya Chakraborti (University of Warwick)

  Bandwidth theorem for graph transversals

  
  

  The bandwidth of a graph is the minimum $b$ such that there is a labeling of the vertex set of $H$ by the numbers $1,2,\ldots,n$ with $|i-j|\le b$ for every edge $ij$ of $H$. The celebrated bandwidth theorem states that if $H$ is an $n$-vertex graph with chromatic number $r$, bounded maximum degree, and bandwidth $o(n)$, then every $n$-vertex graph with minimum degree at least $\left(1-\frac{1}{r}+o(1)\right)n$ contains a copy of $H$. This minimum degree is best possible up to the $o(1)$ term.

  Recently, there have been systematic studies extending spanning subgraph problems to the setting of transversals over a collection of graphs. Given a graph-collection $\mathcal{G}={G_1,\dots, G_h}$ with the same vertex set $V$, an $h$-edge graph $H$ on the vertex set $V$ is a $\mathcal{G}$-transversal if there exists a bijection $\lambda : E(H) \rightarrow {1,\ldots,h}$ such that $e\in E(G_{\lambda(e)})$ for each $e\in E(H)$. The minimum degree condition $\delta(\mathcal{G})=\min{ \delta(G_i)}$ for finding a spanning $\mathcal{G}$-transversal $H$ have been actively studied when $H$ is a Hamilton cycle, an $F$-factor, a tree with maximum degree $o(n/\log n)$, and power of Hamilton cycles, etc.

  Generalizing both these results and the original bandwidth theorem, we obtain asymptotically sharp minimum degree conditions for graphs with bounded degree and sublinear bandwidth, proving the bandwidth theorem for graph transversals. This talk is based on joint work with Seonghyuk Im, Jaehoon Kim, and Hong Liu.

  
  

• 15 January 2024 - James Davies (University of Cambridge)

  Odd distances in colourings of the plane

  
  

  We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd integral distance from each other.

  
  

• 11 December 2023 - Abhishek Dhawan (Georgia Tech)

  Some extremal results on multipartite hypergraphs.

  
  

  A $k$-uniform hypergraph $H = (V, E)$ is $k$-partite if $V$ can be partitioned into $k$ sets $V_1, \ldots, V_k$ such that each edge in $E$ contains precisely one vertex from each $V_i$. For example, a 2-partite 2-uniform hypergraph is a bipartite graph. In this talk, we will discuss extensions of results on bipartite graphs to this more general setting pf hypergraphs. Specifically, we will consider list colorings, balanced colorings, and balanced independent sets.

  
  

  This talk will be in Foster Court room 114.

  
  

• 4 December 2023 - Gal Kronenberg (Oxford)

  Shotgun reconstruction of random graphs.

  
  

  We say that a graph $G$ is reconstructible from its $r$-neighbourhoods if all graphs $H$ having the same collection of $r$-balls as $G$ up to isomorphism, are isomorphic to $G$. We are interested in the reconstruction of the Erdős–Renyi random graph $G(n,p)$ for a wide range of values of $r$, aiming to determine the values of $p$ for which $G(n, p)$ is $r$-reconstructible with high probability. Mossel and Ross showed that the the graph $G(n,p)$ can be reconstructed from its 3-neighbourhoods with high probability provided that $p \gg \log^2(n)/n$. Later, Gaudio and Mossel studied reconstruction from the 1- and 2-neighbourhoods, giving bounds on the values of $p$ for which $G(n,p)$ is reconsructible. For 1-neighbourhoods, this was improved very recently by Huang and Tikhomirov who determined the correct threshold up to logarithmic factors, around $n^{−1/2}$. In this talk we will show new bounds on p for the $r$-reconstructibility problem in $G(n, p)$. We improve the bounds for 2-neighbourhoods given by Gaudio and Mossel by polynomial factors. We also improve the result of Huang and Tikhomirov for 1-neighbourhoods, showing that the logarithmic factor is necessary. Finally, we determine the exact thresholds for $r$-reconstructibility for $r \ge 3$. If time permits, I will also discuss new related results on reconstruction of random directed graphs and random matrices.

  This based on joint works with Tom Johnston, Alexander Roberts, Alex Scott, Paul Balister, and Youri Tamitegama.

  
  

  This talk will be in Bedford Way (20) room 822.

  
  

• 27 November 2023 - Peleg Michaeli (Oxford)

  Rigid partitions

  
  

  A graph is called $d$-rigid if there exists an embedding of its vertex set into $\mathbb{R}^d$ such that every continuous motion of the vertices that preserves the lengths of all edges actually preserves the distances between all pairs of vertices. In this talk, I will present new sufficient conditions for the $d$-rigidity of a graph in terms of the existence of “rigid partitions” - partitions of the graph that satisfy certain connectivity properties. Following this, I will outline several broadly applicable conditions for the existence of rigid partitions and discuss a few applications, among which are new results on the rigidity of highly-connected, (pseudo)random graphs, and dense graphs. In particular, I will show that $Cd^2\log^2(n)$-connected $n$-vertex graphs are $d$-rigid, a result that can be viewed as a step towards the Lovász-Yemini conjecture, which states that $Cd^2$-connected graphs are $d$-rigid.

  The talk is based on joint work with Michael Krivelevich and Alan Lew.

  
  

  This talk will be in Bedford Way (20) room 780.

  
  

• 20 November 2023 - Matt Bowen (Oxford)

  Composite Ramsey theorems via trees

  
  

  We discuss a technique for obtaining new Ramsey theorems from the compositions of old ones. As our simplest application, we show that any finite coloring of $\mathbb{N}$ contains arbitrarily large $A,B\subset \mathbb{N}$ with $(A+B)\cup (A\cdot B)$ monochromatic, addressing a problem of Kra, Moreira, Richter, and Robertson. More generally, we also prove iterated versions of this, finding monochromatic sets such as ${A \circ_1 (B \circ_2 C): \circ_i\in {+,\cdot}} $ and a variety of mixed arithmetic and geometric versions of van der Waerden’s theorem, finding monochromatic sets such as ${a+id, c\cdot ad^i: i\leq k}$ and ${a(b+ic)^j: i,j\leq k}.$

  
  

  This talk will be in Bedford Way (20) room 822.

  
  

• 15 November 2023 - Imre Bárány (Rényi Mathematical Institute)

  Pairwise intersecting convex sets and cylinders in $\mathbb{R}^3$

  
  

  We prove that given a finite collection of cylinders in $\mathbb{R}^3$ with the property that any two of them intersect, there is a line intersecting an $\alpha$-fraction of the cylinders where $\alpha=1/14$. This is a special case of an interesting conjecture.

  
  

  This talk will be in Bedford Way (20) room 639 at 3-4pm.

  
  

• 13 November 2023 - Yani Pehova (LSE)

  Universality for transversal Hamilton cycles

  
  

  In a recent paper from 2020 Joos and Kim showed that every collection of n graphs $G_1,…,G_n$ on a common vertex set $[n]$ with minimum degree at least $n/2$ contains a Hamilton cycle using exactly one edge from each graph. Such a Hamilton cycle is called transversal, or rainbow. This result directly extends Dirac’s theorem, which can be deduced by taking all graphs in the collection to be isomorphic, and kick-started a systematic study of transversal problems in extremal combinatorics. We show that (asymptotically) the same degree condition guarantees not only a single rainbow Hamilton cycle, but in fact every rainbow Hamilton cycle. That is, if all $G_i$ have minimum degree $(1/2+\varepsilon)n$ for some small $\varepsilon$, then there is a Hamilton cycle $C=e_1…e_n$ whose edges $e_i$ are taken in the natural cyclic ordering, such that each $e_i$ is in $E(G_i)$.

  This is joint work with Candida Bowtell, Patrick Morris and Katherine Staden.

  
  

  This talk will be in Bedford Way (20) room 639.

  
  

• 6 November 2023 - Keat Hng (Czech Academy of Sciences)

  Characterising flip process rules with the same trajectories

  
  

  Garbe, Hladký, Šileikis and Skerman recently introduced a class of discrete-time random graph processes called flip processes. A flip process starts with a given $n$-vertex graph, and each step of a flip process involves randomly selecting a $k$-tuple of distinct vertices and modifying the induced subgraph according to a predetermined rule. It was proved by Garbe, Hladký, Šileikis and Skerman that the typical behaviour of flip processes correspond to certain continuous-time deterministic graphon trajectories. In this talk I will discuss recent work towards characterising flip process rules with the same trajectories.

  
  

  This talk will be in Bedford Way (20) room 639.

  
  

• 30 October 2023 - Julien Portier (Cambridge)

  Anti-concentration of Rademacher sums and Tomaszewski's counterpart problem

  
  

  A Rademacher sum is a finite weighted sum of independent Rademacher random variables, that is $R=a_1\epsilon_1+\dots+a_n\epsilon_n$ where the $a_i$ are real constants and $\epsilon_i$ are picked independently and uniformly at random from ${-1,+1}$. Tomaszewski’s conjecture from 1986 states that every Rademacher sum $R$ of variance 1 satisfies $\mathbb{P}(|R| \leq 1) \geq 1/2$. This problem has attracted significant attention over the years before it was finally settled by Keller and Klein in 2020. Tomaszewski’s counterpart problem is concerned with determining $\inf \mathbb{P}(|R| \geq 1)$, where the infimum is taken over the class of Rademacher sums $R$ of variance 1. This problem has also received much attention over the years, with Hitczenko and Kwapień conjecturing in 1994 that the infimum is $7/32$. In this talk we confirm Hitczenko and Kwapień’s conjecture. In fact, our methods enable us to fully determine $f(y)= \inf \mathbb{P}(|R| \geq y\sqrt{\mathrm{Var}(R)})$ where the infimum is taken over all Rademacher sums $R$, confirming a conjecture by Lowther and giving a partial answer to a question by Keller and Klein.

  This is joint work with Lawrence Hollom.

  
  

  This talk will be in Bedford Way (20) room 104 (Elvin Hall).

  
  

• 23 October 2023 - Barnabás Janzer (Oxford)

  Packing the largest trees in the tree packing conjecture

  
  

  The tree packing conjecture of Gyárfás from 1976 says that any sequence of trees $T_1,\ldots,T_n$ such that $|T_i|=i$ for each $i$ packs into $K_n$. Packing even just the largest trees in such a sequence has proven difficult, with Bollobás drawing attention to this in 1995 by conjecturing that, for each $k$, if $n$ is sufficiently large then the largest $k$ trees in any such sequence can be packed. Despite many partial results and much related work on the full tree packing conjecture, even this weakening remained open. We prove Bollobás’s conjecture, by showing that, moreover, a linear number of the largest trees can be packed in the tree packing conjecture. Joint work with Richard Montgomery.

  
  

  This talk will be in Bedford Way (20) room 639.

  
  

• 16 October 2023 - Clément Legrand-Duchesne (Bordeaux)

  The structure of quasi-transitive graphs

  
  

  Clément replaces Michael Krivelevich whose talk was cancelled due to the situation in Israel following Hamas’s horrific attack.

  
  

  An infinite graph is quasi-transitive if its vertex set has finitely many orbits under the action of its automorphism group. We obtain a structure theorem for locally finite quasi-transitive graphs avoiding a minor, which is reminiscent of the Robertson-Seymour Graph Minor Structure Theorem. As applications of this result, we prove that every locally finite quasi-transitive graph attains its Hadwiger number, that is, if such a graph contains arbitrarily large clique minors, then it contains an infinite clique minor. This answers a question of Thomassen from 1992. We also derive some results on the accessibility of quasi-transitive graphs and groups avoiding a minor. Finally, we prove the minor-excluded case of a conjecture of Ballier and Stein (2018) on the domino problem.

  
  

  This talk will be in Foster Court room 114.

  
  

• 9 October 2023 - Michael Savery (Oxford)

  Chromatic number is not tournament-local

  
  

  Scott and Seymour conjectured the existence of a function $f$ such that, for every graph $G$ and tournament $T$ on the same vertex set, $\chi(G)\geq f(k)$ implies that $\chi(G[N_T^+(v)])\geq k$ for some vertex $v$. We will disprove this conjecture even if $v$ is replaced by a vertex set of size $\mathcal{O}(\log{|V(G)|})$. As a consequence, we obtain a negative answer to a question of Harutyunyan, Le, Thomassé, and Wu concerning the analogous statement where the graph $G$ is replaced by another tournament. Time permitting, we will also discuss the setting in which chromatic number is replaced by degeneracy, where a quite different behaviour is exhibited.

  This is joint work with António Girão, Kevin Hendrey, Freddie Illingworth, Florian Lehner, Lukas Michel, and Raphael Steiner.

  
  

  This talk will be in Bedford Way (20) room 639.

  
  

• 2 October 2023 - Asier Calbet Rípodas (Queen Mary)

  $K_r$-saturated graphs with large minimum degree

  
  

  Given a graph $H$, we say that a graph $G$ is $H$-saturated if $G$ is maximally $H$-free, meaning $G$ contains no copy of $H$ but adding any new edge to $G$ creates a copy of $H$. The saturation problem is to determine the saturation number $\mathrm{sat}(n,H)$, the minimum number of edges in an $H$-saturated graph $G$ on $n$ vertices. The saturation number of cliques was determined exactly by Erdős, Hajnal and Moon in the 60s. The problem becomes more interesting, however, if we additionally require the minimum degree of $G$ to be large.

  Let $\mathrm{sat}(n,K_r,t)$ be the minimum number of edges in a $K_r$-saturated graph $G$ on $n$ vertices with $\delta(G) \geq t$. Day showed in 2017 that for fixed $r$ and $t$, $\mathrm{sat}(n,K_r,t)=tn-c(r,t)$ for large enough $n$, where $c(r,t)$ is a constant depending on $r$ and $t$. He raised the problem of estimating $c(r,t)$ and proved the estimates

  \[2^t t^{3/2} \ll c(r,t) \leq t^{t^{2t^2}}\]

  for fixed $r$ and large $t$. In this talk, I will present a result that shows that, for fixed $r$ and large $t$, the order of magnitude of $c(r,t)$ is $4^t t^{-1/2}$, and moreover gives information about the dependence on $r$. I will also discuss another result, which states that all the extremal graphs are blow-ups of some small graph.

  The problem of estimating $c(r,t)$ turns out to be intimately related to a celebrated result in extremal set theory known as the Two Families Theorem. There are several different versions of this theorem. I will discuss some of these and present a new version of the theorem which is needed in the proofs.

  
  

  This talk will be in Foster Court room 114.

  
  

• 16 May 2023 - Patrick Morris (UPC Barcelona)

  Speeding up random walk mixing by starting from a uniform vertex

  
  

  The theory of rapid mixing random walks plays a fundamental role in the study of modern randomised algorithms. Usually, the mixing time is measured with respect to the worst initial position. It is well known that the presence of bottlenecks in a graph hampers mixing and, in particular, starting inside a small bottleneck significantly slows down the diffusion of the walk in the first steps of the process. To circumvent this problem, the average mixing time is defined to be the mixing time starting at a uniformly random vertex.

  In this talk we discuss a general framework to show logarithmic average mixing time for random walks on graphs with small bottlenecks. The framework is especially effective on certain families of random graphs with heterogeneous properties. We demonstrate its applicability on two random models for which the mixing time was known to be of order $\log^2n$, speeding up the mixing to order $\log n$. First, in the context of smoothed analysis on connected graphs, we show logarithmic average mixing time for randomly perturbed graphs of bounded degeneracy. A particular instance is the Newman-Watts small-world model. Second, we show logarithmic average mixing time for supercritically percolated expander graphs. When the host graph is complete, this application gives an alternative proof that the average mixing time of the giant component in the supercritical Erdős-Rényi graph is logarithmic.

  This represents joint work with Alberto Espuny Díaz, Guillem Perarnau and Oriol Serra.

  This talk will be in 25 Gordon Street, Room 500.

  
  

• 9 May 2023 - Thomas Karam (Oxford)

  Ranges on the cube and lower-degree ranks of polynomials over finite prime fields.

  
  

  Let $p$ be a prime integer, let $1 \le t < d < p$ be integers, and let $S$ be a non-empty subset of $\mathbb{F}_p$ (which may be thought of as being {$0,1$}). We will establish that if a polynomial $P:\mathbb{F}_p^n \to \mathbb{F}_p$ with degree $d$ is such that the image $P(S^n)$ does not contain the full image $A(\mathbb{F}_p)$ of any non-constant polynomial $A: \mathbb{F}_p \to \mathbb{F}_p$ with degree at most $t$, then $P$ coincides on $S^n$ with a polynomial $Q$ that can be decomposed as a sum of a bounded number of polynomials which each have degree at most $d$ and are products of polynomials that have degrees at most $\lfloor d/(t+1) \rfloor$. In particular the polynomial $Q$ has bounded degree-$\lfloor d/(t+1) \rfloor$-rank in the sense of Green and Tao. Likewise, we will prove that if the assumption holds even for $t=d$ then $P$ coincides on $S^n$ with a polynomial with degree at most $d$ and depending only on a bounded number of variables.

  This talk will be in 25 Gordon Street, Room 500.

  
  

• 21 March 2023 - Noam Lifshitz (Hebrew University)

  Product free sets in groups

  
  

  A subset $A$ of a group is said to be product free if for all elements $a,b$ in $A$ their product $ab$ is not in $A$. In 1985 Babai and Sós posed the problem of determining the largest product free sets in the alternating group. We solve this problem completely when $n$ is sufficiently large.

  Our proof combines representation theory with a recent machinery we developed called `hypercontractvity for global functions’.

  
  

• 14 March 2023 - Shubham Gupta (Imperial)

  Symmetrization inequalities on graphs

  
  

  Abstract: In the euclidean space setting, symmetrization inequalities have been quite useful in solving problems coming from various parts of analysis: spectral geometry, variational problems, mathematical physics, spectral theory, to name a few. This theory is very classical and a lot is known in the continuum. In my talk, I will discuss about discrete analogues of these inequalities on graphs. This is a fairly new topic, and there is hardly anything known in this setting. I will talk about recent developments that has happened in the last one year, connections of this theory with different types of isoperimetric inequalities on graphs. Apart from general theory, I will present some concrete results for standard graph on $2d$ integer lattices. The talk will be at the interface of discrete math and analysis, and will be based on a joint work with Stefan Steinerberger: arXiv:2212.07590.

  
  

• 7 March 2023 - Mehtaab Sawhney (MIT)

  The insensitive dice kernel

  
  

  We consider tuples of $n$ sided dice drawn from either the multiset or balanced sequence model. Relying on Fourier based methods, we prove that the natural tournament associated to $n$ sided die converges to a limit tournamenton which while highly non-quasirandom exhibits numerous symmetries. The limit tournamenton is naturally related to the spectrum of a certain skew-symmetric operator (e.g. a kernel). Our results answer a pair of questions of Conrey, Gabbard, Grant, Liu, and Morrison in the multiset model and substantially extend (and sharpen) recent works of Polymath and Cornacchia and Hązła which considered the balanced sequence model (and a continuous analog). The focus of the talk will be on local limit methods, associated heuristics, and when they may be useful in combinatorial settings.

  Joint w. Ashwin Sah

  
  

• 28 February 2023 - Matías Pavez-Signé (Warwick)

  Ramsey numbers of bounded degree trees versus general graphs

  
  

  In 1985, Erdős, Faudree, Rousseau, and Schelp showed that for every graph $H$ with chromatic number $k$ and every bounded degree tree $T$ of size $\Omega(|H|^4)$, the Ramsey number $R(T,H)$ is $(k-1)(|T|-1)+\sigma(H)$, where $\sigma(H)$ is the size of the smallest colour class across all proper $k$-colourings of $H$. In this talk, I will present a quantitative improvement on this result, showing that $R(T,H)=(k-1)(|T|-1)+\sigma(H)$ for every tree $T$ of size $\Omega(|H|)$ and bounded maximum degree. This result is tight and confirms a conjecture of Balla, Pokrovskiy, and Sudakov. This is joint work with Richard Montgomery and Jun Yan.

  
  

• 21 February 2023 - Barnabás Janzer (Cambridge)

  Partial shuffles by lazy swaps - CANCELLED

  
  

  Assume that we have a deck of $n$ cards, and we try to shuffle it using random swaps – that is, we perform a sequence of moves in which we swap two cards in given positions with given probabilities. How many such swaps are needed to make sure that the end position of every single card is uniformly distributed? And if we want to make sure that the position of any pair is uniformly distributed? And what happens if we only want to make sure that the two jokers (starting at the top of the deck) can end up in all position-pairs, with uniform probabilities? I will talk about these problems and some related questions. Joint work with Robert Johnson and Imre Leader.

  
  

• 7 February 2023 - Nora Frankl (Open University)

  Helly numbers of exponential lattices

  
  

  The Helly number of a set in the plane is the smallest $N$ such that the following is true. If any $N$ members of a finite family of convex sets contains a point of $S$, then there is a point of $S$ which is contained in all members of the family. An exponential lattice with base $x$ consists of points whose coordinates are positive integer powers of $x$. We prove lower and upper bounds on Helly numbers of exponential lattices in terms of $x$, and we determine their values exactly in some cases. We also consider asymmetric exponential lattices, and characterise those that have finite Helly numbers. Joint work with Gergely Ambrus, Martin Balko, Attila Jung and Márton Naszódi.

  
  

• 31 January 2023 - Kyriakos Katsamaktsis (UCL)

  Hamilton cycles in randomly perturbed graphs

  
  

  Let $G$ be a graph of order $n$ with linear minimum degree, and suppose we `perturbe’ $G$ by adding the edges of the binomial random graph on the same vertex set. It is well known that if the random graph has edge probability at least $C/n$ for some constant C, then with high probability the perturbed graph is Hamiltonian. We show that if each edge of the perturbed graph gets a colour independently and uniformly at random from a set of size $n$, then with high probability the perturbed graph has a rainbow Hamilton cycle, i.e. one with each edge having a different colour. This is joint work with Shoham Letzter.

  
  

• 24 January 2023 - Paul Bastide (Bordeaux)

  Graph reconstruction with distance oracles

  
  

  How fast can you reconstruct a network using a ping-pong protocol? Distance query reconstruction is a setting where we assume an unknown simple and connected graph, and we try to recover the graph only using queries of distance between pairs of vertices. In this talk we extend a result by Kannan, Mathieu, and Zhou in the probabilistic settings, creating a deterministic algorithm for chordal graphs or a randomized algorithm able to reconstruct graphs of bounded treelength with a quasi-linear number of queries in expectation. In particular, graphs of bounded treelength contain various graph classes of interest such as k-chordal graphs, permutation graphs and AT-free graphs. This talk is based on a joint work with Carla Groenland.

  
  

• 17 January 2023 - Amedeo Sgueglia (UCL)

  Spanning subgraphs in randomly perturbed graphs

  
  

  We study the model of randomly perturbed dense graphs, which is the union of any $n$-vertex graph $G_{\alpha}$ with minimum degree at least $\alpha n$ and the binomial random graph $G(n,p)$. In this talk, we discuss questions on the containment of various spanning structures, and we offer several new sharp and stability results. We also point out a number of interesting questions that remain open.

  This is joint work with Julia Böttcher, Olaf Parczyk, and Jozef Skokan.

  
  

• 5 December 2022 - Viresh Patel (Queen Mary)

  Hamilton cycles in regular oriented and directed graphs

  
  

  Classical theorems of Dirac and of Ghouila-Houri establish the minimum degree theshold that guarantees the existence of a Hamilton cycle in a graph and in a directed graph respectively. (For oriented graphs, the degree threshold was established much more recently.) By imposing suitable regularity and/or connectivity conditions on graphs, one can lower the degree threshold at which a Hamilton cycle is guaranteed to appear, and this is quite well understood in the case of graphs. Conjectures of Kuhn and Osthus and of Jackson describe the corresponding situation for directed graphs and oriented graphs respectively. I will discuss approximate solutions to these conjectures. This is based on joint work with Allan Lo and Mehmet Akif Yildiz.

  This talk will be in Gordon Square (26) Room B32.

  
  

• 29 November 2022 - Katherine Staden (Open University)

  Symmetrisation and inducibility

  
  

  Given a small graph $F$, what is the maximum number of induced copies of $F$ that an $n$-vertex graph can contain, and what does a graph with many copies look like? This is the inducibility problem introduced by Pippenger and Golumbic in 1975, which is still wide open for most $F$. I will give a survey of the area and will mention some of the latest results, including joint work with Hong Liu, Oleg Pikhurko and Maryam Sharifzadeh.

  
  

• 22 November 2022 - Xizhi Liu (Warwick)

  An invitation to nondegenerate hypergraph Turán problem

  
  

  Let us call a graph/hypergraph $G$ extremal if there exists a finite family $F$ such that $G$ is an $F$-free graph with the maximum number of edges. The classical Erdős–Stone-Simonovitsz theorem implies that Turan graphs approximate all extremal graphs in edit distance. This talk is an invitation to its analogue in the hypergraph setting: what hypergraphs can approximate all extremal hypergraphs? I’ll mention some related results.

  
  

• 15 November 2022 - Tom Johnston (Bristol)

  TBA

  
  
  
  

• 2 November 2022 - Eoin Long (Birmingham)

  Distinct degrees and homogeneous sets

  
  

  In this talk I will discuss some recent work examining the extremal relationship between two well-studied graph parameters: the order of the largest homogeneous set in a graph $G$ and the maximal number of distinct degrees appearing in an induced subgraph of $G$, denoted respectively by $\mathrm{hom}(G)$ and $f(G)$.

  Our main theorem improves estimates due to Bukh and Sudakov and to Narayanan and Tomon and shows that if $G$ is an $n$-vertex graph with $\mathrm{hom} (G)$ at least $n^{1/2}$ then $f(G) > ( n / \mathrm{hom} (G) )^{1 - o(1)}$. The bound here is sharp up to the $o(1)$-term, and asymptotically solves a conjecture of Narayanan and Tomon. In particular, this implies that $\max ( \mathrm{hom} (G), f(G) ) > n^{1/2 -o(1)}$ for any $n$-vertex graph $G$, which is also sharp.

  The relationship between these parameters is known to change when $\mathrm{hom}(G) < n^{1/2}$. I hope to discuss the suspected relationship in this other region, along with supporting results.

  Joint work with Laurențiu Ploscaru.

  This talk will be in Foster Court Room 243.

  
  

• 25 October 2022 - Bertille Granet (Heidelberg)

  Hamilton decompositions of regular bipartite tournaments

  
  

  A regular bipartite tournament is an orientation of a complete balanced bipartite graph $K_{2n,2n}$ where every vertex has its in- and outdegree both equal to $n$. In 1981, Jackson conjectured that any regular bipartite tournament can be decomposed into Hamilton cycles. We prove this conjecture for sufficiently large $n$. Along the way, we also prove several further results, including a conjecture of Liebenau and Pehova on Hamilton decompositions of dense bipartite digraphs.

  
  

• 18 October 2022 - Maria-Romina Ivan (Cambridge)

  A Ramsey Characterisation of Eventually Periodic Words

  
  

  A factorisation $x = u_1u_2\ldots$ of an infinite word $x$ on alphabet $X$ is called ‘super-monochromatic’, for a given colouring of the finite words $X^∗$ on alphabet $X$, if each word $u_{k_1} u_{k_2} \ldots u_{k_n}$, where $k_1 < · · · < k_n$, is the same colour. A direct application of Hindman’s theorem shows that if $x$ is eventually periodic, then for every finite colouring of $X^∗$, there exist a suffix of $x$ that admits a super-monochromatic factorisation. What about the converse? In this talk we show that the converse does indeed hold: thus a word $x$ is eventually periodic if and only if for every finite colouring of $X^∗$ there is a suffix of $x$ having a super-monochromatic factorisation. This has been a conjecture in the community for some time. Our main tool is a Ramsey result about alternating sums. This provides a strong link between Ramsey theory and the combinatorics of infinite words.

  Joint work with Imre Leader and Luca Q. Zamboni

  
  

• 11 October 2022 - Hélder Lima (Kent)

  Lattice paths, (branched) continued fractions, and (multiple) orthogonal polynomials

  
  

  The focal point of this talk is the recently found connection between two completely different corners of mathematics: multiple orthogonal polynomials, an extension of standard orthogonal polynomials developed and studied by the special-functions community, and branched continued fractions, a generalisation of continued fractions arising from the combinatorics of lattice paths and introduced by the enumerative-combinatorics community to solve total-positivity problems.

  Firstly, we revisit the classical connection between lattice paths, continued fractions, and orthogonal polynomials. Then, we discuss our ongoing research on an extension of this connection linking lattice paths, branched continued fractions, and multiple orthogonal polynomials. This work is part of a collaboration with Alan Sokal.

  
  

• 4 October 2022 - Felix Fischer (Queen Mary)

  Optimal Impartial Selection

  
  

  I will consider selection rules that map any directed graph (without loops) to a subset of its vertices. A selection rule is impartial if the selection of a vertex is independent of its outgoing edges, and an optimal impartial rule is one that in any graph selects vertices with large degrees. The idea is that vertices and edges represent individuals and nominations among invidiuals, and we want to select highly nominated individuals without individuals having an influence on their own selection. I will discuss what is know about impartial selection and point to some open problems.

  The talk is based on joint work with Noga Alon, Antje Bjelde, Javier Cembrano, David Hannon, Max Klimm, Ariel Procaccia, and Moshe Tennenholtz.

  This talk will in Gordon Square (24) Room 105 at 2:30–3:30.

  
  

• 27 September 2022 - Alp Müyesser (UCL)

  A general approach to transversal versions of Dirac-type theorems

  
  

  Given a collection of hypergraphs $\mathcal{H}=(H_1, \ldots, H_m)$ with the same vertex set, an $m$-edge graph $F\subset \cup_{i\in [m]}H_i$ is a transversal if there is a bijection $\phi:E(F)\to [m]$ such that $e\in E(H_{\phi(e)})$ for each $e\in E(F)$. How large does the minimum degree of each $H_i$ need to be so that $\mathcal{H}$ necessarily contains a copy of $F$ that is a transversal? Each $H_i$ in the collection could be the same hypergraph, hence the minimum degree of each $H_i$ needs to be large enough to ensure that $F\subseteq H_i$. Since its general introduction by Joos and Kim, a growing body of work has shown that in many cases, this lower bound is tight. In this paper, we give a unified approach to this problem by giving a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Dirac-type results for (powers of) Hamiltn cycles. For example, we derive that any collection of $2n$ graphs on an $n$-vertex set, each with minimum degree at least $(2/3+o(1))n$, contains a transversal copy of the square of a Hamilton cycle. This can be viewed as a rainbow version of Pósa’s conjecture.

  This is joint work with Pranshu Gupta, Fabian Hamann, Olaf Parczyk, and Amedeo Sgueglia.

  This talk will be held online, in https://ucl.zoom.us/j/94328070777.

  
  

• 10 May 2022 - Anurag Bishnoi (UCL)

  The minimum degree of minimal Ramsey graphs for cliques

  
  

  We will present a new upper bound of $s_r(K_k) = O(k^5 r^{5/2})$ on the Ramsey parameter $s_r(K_k)$ introduced by Burr, Erdős and Lovász in 1976, which is defined as the smallest minimum degree of a graph $G$ such that any $r$-colouring of the edges of $G$ contains a monochromatic $K_k$, whereas no proper subgraph of $G$ has this property. This improves the previous upper bound of $s_r(K_k) = O(k^6 r^3)$ proved by Fox et al. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.

  This is joint work with John Bamberg and Thomas Lesgourgues.

  
  

• 21 March 2022 - Gal Kronenberg (Oxford)

  Independent sets in random subgraphs of the hypercube

  
  

  Independent sets in bipartite regular graphs have been studied extensively in combinatorics, probability, computer science and more. The problem of counting independent sets is particularly interesting in the $d$-dimensional hypercube {$0,1$}$^d$, motivated by the lattice gas hardcore model from statistical physics. Independent sets also turn out to be very interesting in the context of random graphs.

  The number of independent sets in the hypercube {$0,1$}$^d$ was estimated precisely by Korshunov and Sapozhenko in the 1980s and recently refined by Jenssen and Perkins.

  In this talk we will discuss new results on the number of independent sets in a random subgraph of the hypercube. The results extend to the hardcore model and rely on an analysis of the antiferromagnetic Ising model on the hypercube.

  This talk is based on joint work with Yinon Spinka.

  
  

• 14 March 2022 - Adva Mond (Cambridge)

  Counting Hamiltonian cycles in Dirac hypergraphs.

  
  

  For $0 \le r < k$, a Hamiltonian $r$-cycle in a $k$-uniform hypergraph $H$ is a cyclic ordering of the vertices of $H$ in which the edges are segments of length $k$ and every two consecutive edges overlap in exactly $r$ vertices. We show that for all $0 \le r < k-1$, every Dirac $k$-graph, that is, a $k$-graph with minimum co-degree $pn$ for some $p>1/2$, has (up to a subexponential factor) at least as many Hamiltonian $r$-cycles as a typical random $k$-graph with edge-probability p. This improves a recent result of Glock, Gould, Joos, Osthus and Kühn, and verifies a conjecture of Ferber, Krivelevich and Sudakov for all values $0 \le r < k-1$. (Joint work with Asaf Ferber and Liam Hardiman.)

  
  

• 7 March 2022 - Amarja Kathapurkar (Birmingham)

  Spanning trees in dense digraphs

  
  

  In 2001, Komlós, Sárközy and Szemerédi proved that for sufficiently large $n$, every $n$-vertex graph with minimum degree at least $n/2 + o(n)$ contains a copy of every $n$-vertex tree with maximum degree at most $O(n/\log n)$. We prove the corresponding result for directed graphs. That is, we show that for sufficiently large $n$, every $n$-vertex directed graph with minimum semidegree at least $n/2 + o(n)$ contains a copy of every $n$-vertex oriented tree whose underlying maximum degree is at most $O(n/\log n)$. This improves a recent result of Mycroft and Naia, which requires the oriented trees to have underlying maximum degree at most $\Delta$, for any constant $\Delta$ and sufficiently large $n$.

  
  

• 28 February 2022 - Jane Tan (Oxford)

  Generalisations of a light switch problem

  
  

  Given any graph with lights turned on at each vertex and buttons corresponding to each vertex that toggle the status (on/off) of the vertex together with its neighbourhood, is there always a sequence of button-pushes that turns all of the lights off? This puzzle is answered by a folklore result of Gallai on partitioning the vertex set of a graph into two parts, each inducing a subgraph with specified degree parity conditions. A natural follow-up is to consider partitions satisfying prescribed degree congruence conditions modulo $q$. Recently, Ferber, Hardiman and Krivelevich showed that, for any $0\leq x <q$, almost every $G_{n,1/2}$ has a vertex partition into $q+1$ parts such that each induced subgraph has degrees $x \bmod q$, and asked whether the same holds with $q$ parts. In this talk, we outline why this is not the case; in fact, the distribution of the counts of such `good’ partitions into $q$ parts is asymptotically Poisson. This is joint work with Paul Balister, Emil Powierski and Alex Scott.

  
  

• 7 February 2022 - Richard Montgomery (Birmingham)

  On the Ryser-Brualdi-Stein Conjecture

  
  

  A Latin square of order $n$ is an $n$ by $n$ grid filled with $n$ symbols, so that every symbol appears exactly once in each row and each column. A transversal of a Latin square is a collection of cells in the grid which share no row, column or symbol.

  The Ryser-Brualdi-Stein conjecture says that every Latin square of order $n$ has a transversal with $n-1$ cells if $n$ is even and with $n$ cells if $n$ is odd. Recently, Keevash, Pokrovskiy, Sudakov and Yepremyan broke a long-standing bound on this problem by showing that every Latin square of order $n$ has a transversal with $n-O(\log n/\log \log n)$ cells.

  I will discuss how to make further progress on this problem, and in particular the challenges of using absorption techniques in this setting.

  
  

• 31 January 2022 - António Girão (Oxford)

  A canonical polynomial van der Waerden’s theorem

  
  

  A well known theorem due to Van der Waerden and dating from 1927 states that in any finite colouring of the natural numbers there exist arbitrarily long monochromatic arithmetic progressions. Most Ramsey-theoretical results (finite colourings) have a canonical version. In this setting, the palette of colours may be infinite but one still would like to characterize all unavoidable sub-structures. For example, the canonical Van der Waerden’s Theorem, first proved by Erdős and Graham, states that in any colouring of $[N]$ there exist either arbitrarily long monochromatic arithmetic progressions or arbitrarily long rainbow arithmetic progressions. In this talk, we shall talk about a canonical version of the polynomial Van der Waerden’s Theorem, originally proved by Bergelson and Liebman.

  
  

• 6 December 2021 - Julian Sahasrabudhe (Cambridge)

  The singularity probability of random symmetric matrices

  
  

  Let $M_n$ be drawn uniformly from all $n$ by $n$ symmetric matrices with coefficients in {$-1,1$}. We consider the following basic problem: what is the probability $M_n$ is singular? In this talk I will discuss some recent joint work with Marcelo Campos, Matthew Jenssen and Marcus Michelen, where we show the singularity probability is exponentially small. At the heart of the proof is a combinatorial “decoupling” lemma which I suspect has applications well beyond the scope of our work.

  
  

• 29 November 2021 - Leo Versteegen (Cambridge)

  Linear configurations containing 4-term arithmetic progressions are uncommon

  
  

  A linear configuration is called common (in $\mathbb{F}_p^n$) if every 2-coloring of $\mathbb{F}_p^n$ yields at least the number of monochromatic instances of a randomly chosen coloring. Saad and Wolf asked whether, analogously to a result by Thomason in graph theory, every configuration containing a 4-term arithmetic progression is uncommon. I will sketch a proof confirming that this is the case and discuss some of the difficulties in finding a full characterisation of common configurations.

  
  

• 22 November 2021 - Candida Bowtell (Oxford)

  The $n$-queens problem

  
  

  The $n$-queens problem asks how many ways there are to place $n$ queens on an $n \times n$ chessboard so that no two queens can attack one another, and the toroidal $n$-queens problem asks the same question where the board is considered on the surface of a torus. Let $Q(n)$ denote the number of $n$-queens configurations on the classical board and $T(n)$ the number of toroidal $n$-queens configurations. The toroidal problem was first studied in 1918 by Pólya who showed that $T(n)>0$ if and only if $n \equiv 1,5 \mod 6$. Much more recently Luria showed that $T(n)\leq ((1+o(1))ne^{-3})^n$ and conjectured equality when $n \equiv 1,5 \mod 6$. We prove this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) $n \equiv 1,5 \mod 6$. We also show that $Q(n)\geq((1+o(1))ne^{-3})^n$ for all $n \in \mathbb{N}$ which was independently proved by Luria and Simkin and, combined with our toroidal result, completely settles a conjecture of Rivin, Vardi and Zimmermn regarding both $Q(n)$ and $T(n)$.

  In this talk we’ll discuss our methods used to prove these results. A crucial element of this is translating the problem to one of counting matchings in a $4$-partite $4$-uniform hypergraph. Our strategy combines a random greedy algorithm to count `almost’ configurations with a complex absorbing strategy that uses ideas from the methods of randomised algebraic construction and iterative absorption.

  This is joint work with Peter Keevash.

  
  

• 15 November 2021 - Bishal Deb (UCL)

  Analysing a strategy for a card guessing game via continuously increasing subsequences in multiset permutations

  
  

  Consider the following card guessing game introduced by Diaconis and Graham (1981): there is a shuffled deck of $mn$ cards with n distinct cards appearing with multiplicity $m$. In each round, the player has to guess the top card of the deck, and is then told whether the guess was correct or not, the top card is then discarded and then the game continues with the next card. This is known as the partial feedback model. The aim is maximise the number of correct guesses. One possible strategy is the shifting strategy in which the player keeps guessing $1$ every round until the guess is correct in some round, and then keeps guessing $2$, and then $3$ and so on. We are interested in finding the expected score using this strategy.

  We can restate this problem as finding the expected length of the longest increasing subsequence of the form $123\ldots i$ in a word formed using letters $1$ to $n$ where each letter occurs with multiplicity $m$. In this talk, we show that this number is $m+1 - 1/(m+2)$ plus an exponential error term. This settles a conjecture of Diaconis, Graham, He and Spiro.

  This talk will be at an interface between combinatorics, probability and analysis, and is based on joint work with Alexander Clifton, Yifeng Huang, Sam Spiro and Semin Yoo.

  
  

• 8 November 2021 - Joseph Hyde (University of Warwick)

  Progress on the Kohayakawa-Kreuter conjecture

  
  

  Let \(H_1, ..., H_r\) be graphs. We write \(G(n,p) \to (H_1, ..., H_r)\) to denote the property that whenever we colour the edges of \(G(n,p)\) with colours from the set \([r] := \{1, ..., r\}\) there exists some \(1 \leq i \leq r\) and a copy of \(H_i\) in \(G(n,p)\) monochromatic in colour \(i\).

  There has been much interest in determining the asymptotic threshold function for this property. Rödl and Ruciński (1995) determined the threshold function for the general symmetric case; that is, when $H_1=\cdots =H_r$. A conjecture of Kohayakawa and Kreuter (1997), if true, would effectively resolve the asymmetric problem. Recently, the 1-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij (2021+). The 0-statement however has only been proved for pairs of cycles, pairs of cliques and pairs of a clique and a cycle.

  In this talk we introduce a reduction of the 0-statement of Kohayakawa and Kreuter’s conjecture to a certain deterministic, natural subproblem. To demonstrate the potential of this approach, we show this subproblem can be resolved for almost all pairs of regular graphs (satisfying properties one can assume when proving the 0-statement).

  
  

• 18 October 2021 - Liana Yepremyan (Emory University)

  Enumerating independent sets in Abelian Cayley graphs

  
  

  We show that any Cayley graph on an Abelian group of order 2n and degree $\tilde{\Omega}(\log n)$ has at most $2^{n+1}(1+o(1))$ independent sets. This bound is tight up to the $o(1)$ term whenever the graph is bipartite. Proof techniques include the graph container method of Sapozhenko and the Plünnecke-Rusza-Petridis inequality from additive combinatorics.

  This is joint work with Aditya Potukuchi.

  
  

• 11 October 2021 - Nina Kamčev (University of Zagreb)

  Common linear patterns are rare

  
  

  Several classical results in Ramsey theory (including famous theorems of Schur, van der Waerden, Rado) deal with finding monochromatic linear patterns in two-colourings of the integers. Our topic will be quantitative extensions of such results.

  A linear system $L$ over $\mathcal{F}_q$ is common if the number of monochromatic solutions to $L=0$ in any two-colouring of $\mathcal{F}_q^n$ is asymptotically at least the expected number of monochromatic solutions in a random two-colouring of $\mathcal{F}_q^n$. Motivated by existing results for specific systems (such as Schur triples and arithmetic progressions), as well as extensive research on common and Sidorenko graphs, the systematic study of common systems of linear equations was recently initiated by Saad and Wolf. Fox, Pham and Zhao characterised common linear equations.

  I will talk about recent progress towards a classification of common systems of two or more linear equations. In particular, the uncommonness of an arbitrarily large system $L$ can be reduced to studying single equations implied by $L$.

  Joint work with Anita Liebenau and Natasha Morrison.