Abstracts of past talks

• 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 2021 - 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.