In the critical beta-splitting model of a random $n$-leaf rooted tree, clades (subtrees) are recursively split into sub-clades, and a clade of $m$ leaves is split into sub-clades containing $i$ and $m-i$ leaves with probabilities $\propto 1/(i(m-i))$. This model turns out to have interesting properties. There is a canonical embedding into a continuous-time model ($\operatorname{CTCS}(n)$). There is an inductive construction of $\operatorname{CTCS}(n)$ as $n$ increases, analogous to the stick-breaking constructions of the uniform random tree and its limit continuum random tree. We study the heights of leaves and the limit fringe distribution relative to a random leaf. In addition to familiar probabilistic methods, there are analytic methods (developed by co-author Boris Pittel), based on explicit recurrences, which often give more precise results. So this model provides an interesting concrete setting in which to compare and contrast these methods. Many open problems remain.
Preprints at https://arxiv.org/abs/2302.05066 and https://arxiv.org/abs/2303.02529

More than 30 year ago Jerrum studied the planted clique problem and proved that under worst-case initialization Metropolis fails to recover planted cliques of size $\ll n^{1/2}$ in the Erdős-Rényi graph $G(n,1/2)$. This result is classically cited in the literature of the problem, as the "first evidence" that finding planted cliques of size much smaller than square root $n$ is "algorithmically hard". Cliques of size $\gg n^{1/2}$ are easy to find using simple algorithms. In a recent work we show that the Metropolis process actually fails to find planted cliques under worst-case initialization for cliques up to size almost linear in $n$. Thus the algorithm fails well beyond the $\sqrt{n}$ "conjectured algorithmic threshold". We also prove that, for a large parameter regime, that the Metropolis process fails also under "natural initialization". Our results resolve some open questions posed by Jerrum in 1992. Based on joint work with Zongchen Chen and Iias Zadik.

The speakers are Maya Stein (University of Chile), Mathias Schacht (Hamburg), János Pach (Rényi Institute, Hungary and IST Austria), Marthe Bonamy (Bordeaux), Mehtaab Sawhney (Cambridge/MIT), and Julian Sahasrabudhe (Cambridge). Please see the event website for further details including titles, abstracts, and timings. Anyone interested is welcome to attend, and no registration is required.

"Colouring" a tournament means partitioning its vertex set into acylic subsets; and the "domination number" is the size of the smallest set of vertices with no common in-neighbour. In some ways these are like the corresponding concepts for graphs, but in some ways they are very different. We give a survey of some recent results and open questions on these topics.

Joint with Tung Nguyen and Alex Scott.

We determine the minimal forbidden minors characterising the class of countable graphs that embed into some compact surface. We will also discuss Thomas’s conjecture that the Robertson—Seymour Graph Minor Theorem extends to countably infinite graphs. [https://arxiv.org/abs/2301.11042]