Thursday 23 January 2025, 14:00-15:00
Watson Building, B16
We consider a generic game where there are n players who can each be in one of k states and at each time step the players can choose to change their state based on the current states of the other players. It is known that there are no 'simple' dynamics which converge to a pure Nash equilibrium in every generic game that has one, but are there a small number of difficult games or is it hard to converge in most of the games? One simple dynamic is the best response with inertia dynamic, in which case convergence is a question about the connectivity of the best-response graph. We will look at the connectivity of a random best-response graph and show that this simple dynamic converges to a pure Nash equilibrium in almost all generic games that have one. Based on joint work with Michael Savery, Alex Scott and Bassel Tarbush.
Thursday 30 January 2025, 14:00-15:00
Watson Building, B16
A strong external difference family (SEDF) is a collection of disjoint subsets A1,...,Am of a finite group G with the property that for each 1 ≤ i ≤ m, the non-zero elements of G occur exactly once as a difference of the form ai-aj with ai ∈ Ai and aj ∈ Aj for some j ≠ i. These were defined in 2016 in an attempt to characterise optimal examples of certain structures arising from an application in cryptography. In this talk we give a history of subsequent results on SEDFs and related structures, with a particular focus on connections to other areas of combinatorics including graph labelling and additive combinatorics. Based on joint work with Sophie Huczynska, Don Kreher and Doug Stinson.
Thursday 6 February 2025, 14:00-15:00
Watson Building, B16
Graph layout problems seek representations of finite graphs which minimise some specified cost function. Examples include cutwidth, treewidth and bandwidth. They have many applications, for example in circuit design (very large scale integration), bioinformatics and code creation. Typically, finding optimal representations is NP-hard, even for restricted classes of graphs (such as planar graphs).
One facet of geometric group theory is to reveal the close relationship between the algebraic properties of a finitely generated group and the combinatorial and geometric properties of their Cayley graphs. As Cayley graphs depend on a choice of generating set, 'large-scale' properties (those which are shared by all Cayley graphs) are particularly prized.
In this talk I will explain how - once correctly normalised - graph layout cost functions are large-scale properties of bounded degree graphs, and as such have potential algebraic applications. Finally, I will show how recent progress in geometric group theory yields new bounds for graph layout problems.
Thursday 13 February 2025, 14:00-15:00
Watson Building, B16
There has historically been much interest in the distribution of the circumference, the length of the longest cycle, of a random graph G(n,p) in the sparse regime, where p = Θ(1/n). Recently, Anastos and Frieze proved that the circumference has a scaling limit in the upper end of this regime, along the way establishing an alternative 'structural' approximation for the circumference. In this talk I will outline a proof of a central limit theorem for the circumference in this regime using a novel argument based on the Efron-Stein inequality, which relies on a combinatorial analysis of the effect of resampling edges on this approximation
Thursday 20 February 2025, 14:00-15:00
Watson Building, B16
The vertex-Turan problem for hypercubes asks: how small a family of vertices F can we take in {0,1}n, in such a way that F intersects the vertex-set of every d-dimensional subcube? A widely believed folklore conjecture stated that the minimal measure of such a family is (asymptotically) 1/(d + 1), which is attained by taking every (d + 1)th layer of the cube. (This was proven in the special case d = 2 by Kostochka in 1976, and independently by Johnson and Entringer.) In this talk, we will outline a construction of such a family F with measure at most cd for an absolute constant c < 1, disproving the folklore conjecture in a strong sense. We will explain the connection to Turan questions for 'daisies', and discuss various other widely believed conjectures, e.g. on forbidden posets, that can be seen to fail due to our construction. Several open problems remain, including the optimal value of c above. Based on joint work with Maria-Romina Ivan and Imre Leader.
Thursday 27 February 2025, 14:00-15:00
Watson Building, B16
The Ramsey multiplicity problem asks for the minimum asymptotic density of monochromatic labelled copies of a graph H in a red/blue colouring of Kn. As with explicitly calculating Ramsey numbers, this problem is notoriously difficult, with it being solved for only a handful of graphs H. Here, and in an accompanying paper ('Off-Diagonal Ramsey Multiplicity' by Jonathan Noel and Elena Moss), we introduce an off-diagonal generalisation in which the goal is to minimise a certain naturally weighted sum of the densities of red copies of one graph and blue copies of another.
In this talk we will focus on when colourings based on the Turán-graph appear as such minimisers, in particular proving a result based on a recent breakthrough of Fox and Wigderson, who answered the Ramsey multiplicity problem for a certain class of uncommon graphs. Joint work with Jonathan Noel and Jae-baek Lee.
Thursday 6 March 2025, 14:00-15:00
Watson Building, B16
A variant of the notable Erdős-Sós conjecture, posed by Havet, Reed, Stein and Wood, states that every graph with minimum degree at least 2k/3 and maximum degree at least k contains a copy of every tree with k edges. For trees of bounded degree, we prove an approximate version of this, building on results already known in the dense setting due to Besomi, Pavez-Signé and Stein. We also prove similar results for related conjectures, where alternative degree combinations are considered.
This is joint work with Leo Versteegen and Alexey Pokrovskiy.
Thursday 13 March 2025, 14:00-15:00
Watson Building, B16
The Erdős-Sauer problem asks to find, for any constant r, the maximum possible number of edges that an n-vertex graph can have without containing an r-regular subgraph. The problem had seen no progress since Pyber's work in 1985 until recently when Janzer and Sudakov resolved this problem up to a multiplicative constant depending on r. We resolve the Erdős-Sauer problem up to an absolute constant factor (not depending on r) as follows. There exists an absolute constant C such that for each positive integer r, every n-vertex graph with at least Cr2nlog log >i>n edges contains an r-regular subgraph. We also show this to be tight up to the value of C for all r \geq 3 and n\geq n(r). Moreover, we obtain similarly tight results for almost the whole range of possible values of r (i.e., not just when r is a constant). This resolves a problem of Rödl and Wysocka (for most values of r). This talk is based on joint work with Janzer, Methuku, and Montgomery.
Wednesday 19 March 2025, 10:00-17:00
University of Warwick
Thursday 27 March 2025, 14:00-15:00
Watson Building, B16
Abstract: TBA
Thursday 3 April 2025, 14:00-15:00
Watson Building, B16
Abstract: TBA
Wednesday 2 October 2024, 14:00-15:00
Watson Building, Lecture Theatre C
Given a k-uniform hypergraph H on n vertices with an r-colouring of its edges, we look for a minimum ℓ-degree condition that guarantees the existence of a perfect matching in H that has more than n/rk edges in one colour. We call this a colour-bias perfect matching.
For 2-coloured graphs, a result of Balogh, Csaba, Jing and Pluhár yields the minimum degree threshold that ensures a perfect matching of significant colour-bias. In this talk, I will present an analogous of this result for k-uniform hypergraphs. More precisely, for each 1 ≤ ℓ ≺ k and r ≥ 2 we determined the minimum ℓ-degree threshold that forces a perfect matching of significant colour-bias in an r-edge-coloured k-uniform hypergraph.
The presented result is joint work with J. Balogh, H. Hàn, R. Lang, J. P. Marciano, M. Pavez-Signé, N. Sanhueza-Matamala and A. Treglown.
Wednesday 9 October 2024, 14:00-15:00
Watson Building, Lecture Theatre C
A classical question in extremal (hyper)graph theory asks for tight minimum degree conditions which force the existence of certain spanning structures in large graphs, generalising Dirac's theorem from 1952. One aspect of this concerns tiling graphs with identical vertex disjoint copies of a small subgraph. For example, asking for tight minimum codegree conditions in a k-uniform hypergraph which force a perfect matching (under the obvious additional necessary condition that the number of vertices is divisible by k). While there has been a lot of interest in these types of tiling problem, still very few results are known. We share a new result in this area, which is joint work with Amarja Kathapurkar, Natasha Morrison and Richard Mycroft.
Wednesday 16 October 2024, 14:00-15:00
Watson Building, Lecture Theatre C
In 1975, Erdős asked for the maximum number of edges that an n-vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set. It is known that Turán-type results can be used to prove an upper bound n3/2+o(1). However, this approach cannot give an upper bound better than n3/2. We show that, for any k, every n-vertex graph with at least n×polylog(n) edges contains k pairwise edge-disjoint cycles with the same vertex set, resolving this old problem in a strong form up to a polylogarithmic factor. The well-known construction of Pyber, Rodl and Szemerédi of graphs without 4-regular subgraphs shows that there are n-vertex graphs with Ω(n log log n) edges which do not contain two edge-disjoint cycles with the same vertex set, so the polylogarithmic term in our result cannot be completely removed.
Wednesday 23 October 2024, 14:00-15:00
Watson Building, Lecture Theatre C
Traditional models of human brain activity often represent it as a network of pairwise interactions between brain regions. Going beyond this limitation, recent approaches have been proposed to infer higher-order interactions from temporal brain signals involving three or more regions. However, to this day it remains unclear whether methods based on inferred higher-order interactions outperform traditional pairwise ones for the analysis of fMRI data. In this talk I will introduce a novel approach to the study of interacting dynamics in brain connectomics, based on higher-order interaction models. Our method builds on recent advances in simplicial complexes and topological data analysis, with the overarching goal of exploring macro-scale and time-dependent higher-order processes in human brain networks. I will present our preliminary findings along these lines, and discuss limitations and potential future directions for the exciting field of higher-order brain connectomics.
Wednesday 30 October 2024, 14:00-15:00
Watson Building, Lecture Theatre C
Let Kn(k) be the complete k-uniform hypergraph on n vertices. A tight cycle is a k-uniform graph with its vertices cyclically ordered so that every k consecutive vertices form an edge, and any two consecutive edges share exactly k - 1 vertices. A result by Bustamante, Corsten, Frankl, Pokrovskiy and Skokan shows that all r-edge-coloured Kn(k) can be partitioned into cr,k vertex disjoint monochromatic tight cycles. However, the constant cr,k is of tower-type. In this work, we show that cr,k is a polynomial in r.
This is joint work with Allan Lo.
Wednesday 6 November 2024, 14:00-15:00
Watson Building, Lecture Theatre A
We consider the problem of decomposing the edges of a digraph into as few paths as possible. There is a natural lower bound for the number of paths needed in such a decomposition in terms of the in- and outdegrees of the vertices: any digraph that achieves this bound is called consistent. As a generalisation of Kelly’s conjecture on Hamilton decompositions of regular tournaments, Alspach, Mason, and Pullman conjectured in 1976 that every tournament of even order is consistent. This was recently verified for large tournaments by Girão, Granet, Kühn, Lo, and Osthus. A more general conjecture of Pullman states that every orientation of a regular graph of odd degree is consistent. We prove that this holds for the random regular graph of odd degree with high probability. Along the way, we verify the conjecture for graphs of high girth. This is joint work with Mehmet Akif Yildiz.
Wednesday 27 November 2024, 14:00-15:00
Watson Building, Lecture Theatre C
It is easy to see that every q-edge colouring of a complete graph on 2q + 1 vertices contains a monochromatic odd cycle. An old question of Erdős and Graham asks for the smallest size of such monochromatic odd cycle. We will discuss a recent result (joint work with Zach Hunter) where we give the first non-trivial upper bound of the form 2q/q1-o(1).
Wednesday 4 December 2024, 14:00-15:00
Watson Building, Lecture Theatre C
A matrix is given in 'shredded' form if we are presented with the multiset of rows and the multiset of columns, but not told which row is which or which column is which. We say that a matrix is re-constructible if it is uniquely determined by this information. In this talk we will discuss reconstructing shredded random binary n × n matrices, where each entry independently is 1 with probability p. We will cover some history, new results, and related problems. In particular, we will present a sharp threshold for re-constructibility at p ∼ log(n)/(2n).
This talk is based on a joint work with Paul Balister, Alex Scott, and Youri Tamitegama.
Wednesday 11 December 2024, 14:00-15:00
Watson Building, Lecture Theatre C
Accessibility percolation is a simple model in evolutionary biology describing how a population driven by the evolutionary forces of selection and mutation explores a fitness landscape. Mathematically, the fitness landscape is modelled by attaching random weights to the vertices of a graph. Then, accessible percolation asks whether there are paths of increasing fitness of a certain length. I will review some of the progress in this area and then consider the question what happens if the fitness landscape changes over time.
In particular, I will focus on the case when the underlying graph is a regular tree and show how the time it takes to see an increasing path scales in the different regimes of the model. Some of the proofs rely on adapting techniques from the area of noise sensitivity for Boolean functions.