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.