This is a small problem-solving workshop that runs Mon 15 Decemper - Fri 19 December 2025. The focus is on Extremal and Probabilistic Combinatorics. Participation is by invitation only.
We thank the Mathematics Department of the LSE for their financial support.
Organisers
Location
The workshop takes place on the second floor of Columbia House at LSE. Columbia House is on the Aldwych. The talks and coffe breaks will be in COL 2.01 (Columbia House, 2nd floor).
Monday
Tuesday
Wednesday
Thursday
Friday
Dennis Clemens: On variants of the Maker-Breaker connectivity game
We will consider Maker-Breaker games, mostly on complete graphs, in which Maker’s goal is to claim spanning structures with pre-defined properties. Starting with the well-known connectivity game, for which Gebauer and Szabó (2009) determined the threshold bias asymptotically, the talk will give an overview on recent results on variants of the connectivity game. For instance, this will include the diameter game introduced by Balogh et al., a rainbow variant of the connectivity game as will as fixed spanning tree games.
Adva Mond: Optimally packing Hamilton cycles in random directed digraphs
At most how many edge-disjoint Hamilton cycles does a given directed graph contain? It is easy to see that one cannot pack more than the minimum in-degree or the minimum out-degree of the digraph. We show that in the random directed graph D(n,p) one can pack precisely this many edge-disjoint Hamilton cycles, with high probability, given that p is at least the Hamiltonicity threshold, up to a polylog factor.
Based on a joint work with Asaf Ferber.
Patrick Morris: A sparse canonical van der Waerden theorem
The canonical van der Waerden theorem asserts that, for sufficiently large n, every colouring of \([n]\) contains either a monochromatic or a rainbow arithmetic progression of length \(k\) (\(k\)-AP, for short). In this talk, we will determine the threshold at which the binomial random subset \([n]_p\) almost surely inherits this canonical property. As an application, we construct sets \(S\subseteq [n]\) that satisfy the canonical van der Waerden property for \(k\)-APs and such that the \(k\)-APs in \(S\) define a \(k\)-uniform hypergraph of arbitrarily high girth.
Joint work with J. D. Alvarado, Y. Kohayakawa, G. O. Mota and M. Ortega.
Debsoumya Chakraborti: Discrepancy and resilience for Hamilton cycles
A ‘discrepancy’ version of the classical Dirac’s theorem was established in recent works by Balogh–Csaba–Jing–Pluhár, by Freschi–Hyde–Lada–Treglown, and by Gishboliner–Krivelevich–Michaeli. In this talk, we will discuss a generalization of these results in which we asymptotically determine the maximum value \(f_{r,\alpha}(n)\) for every \(\alpha \in [\frac{1}{2}, 1]\) such that every \(r\)-edge-colouring of every \(n\)-vertex graph with minimum degree at least \(\alpha n\) contains a Hamilton cycle where one of the colours appears at least \(f_{r,\alpha}(n)\) times. We will also present a ‘random’ analogue of this result, connecting it with the well-studied notion of ‘resilience’ in random graphs.
Katherine Staden: The semi-inducibility problem
Let \(H\) be a \(k\)-edge-coloured graph and let \(n\) be a positive integer. What is the maximum number of copies of \(H\) in a \(k\)-edge-coloured complete graph on \(n\) vertices? I will discuss the case \(k=2\), which we call the semi-inducibility problem. This problem is a generalisation of the inducibility problem of Pippenger and Golumbic which is solved only for some small graphs and limited families of graphs.
I will introduce some new results in joint work with Abdul Basit, Bertille Granet, Daniel Horsley and André Kündgen.
Leo Versteegen: All in on R(m,d): the universally optimal host graph for the relative ordered Turán problem
For two ordered graphs \(F\) and \(G\), define \(\rho_<(F,G)\) as the greatest density of an \(F\)-free subgraph of \(G\). The relative Turán density \(\rho_<(F)\) of is the infimum of \(\rho_<(F,G)\) over all host graphs \(G\). Reiher, Rödl, Sales, and Schacht initiated the study of relative Turán densities of ordered graphs and showed that it is more subtle and interesting than the unordered case. In particular, \(\rho_<(F)\) is only known for a handful of graphs. In this talk, I will present out result that there exists a family of graphs \(R(m,d)\) such that for all F, whatever value \(\rho_<(F)\) may take, that value is achieved by the family \(R(m, d)\) as host graphs. I will also discuss some related results on the value of \(\rho_<(F)\) for certain families of ordered graphs \(F\).
Simon Griffiths: Giant components in directed graphs
A seminal work of Molloy and Reed in 1995 established a natural sufficient condition for the existence of a giant component in a random graph with a given degree sequence. That condition: \[ \sum_{v} d_v(d_v-2)\, \ge\, \varepsilon e(G)\, , \] corresponds to the supercriticality of a certain related branching process. That said, a number of technical conditions were also imposed on the degree sequence, and these conditions were subsequently weakened by Janson and Luczak and further by Bollobás and Riordan. A true, necessary and sufficient condition for essentially all feasible degree sequences was obtained only in the last decade by Joos, Perarnau, Rautenbach and Reed. They gave an alternative condition, based on the sum of degrees of vertices which come the moment of criticality. In a parallel history, in 2004 Cooper and Frieze explored similar results for digraphs with a fixed degree sequence. Their technical conditions were subsequently weakened by Graf and Cai and Perarnau. We discuss the significant new challenges for the digraph case and progress towards a true necessary and sufficient condition in this context.
Tash Morrison: Spanning trees in pseudorandom graphs via sorting networks
We show that \((n,d,\lambda)\)-graphs with \(\lambda=O(d/log^3n)\) are universal with respect to all bounded degree spanning trees. This significantly improves upon the previous best bound due to Han and Yang, and makes progress towards a problem of Alon, Krivelevich, and Sudakov from 2007. The key new idea in our proof relies on the existence of sorting networks of logarithmic depth, as given by a celebrated construction of Ajtai, Komlós and Szemerédi.
Joint work with Joseph Hyde, Alp Müyesser, and Matías Pavez-Signé.
Jon Noel: Less Than Half of All Oriented Paths Are Anti-Sidorenko
An oriented graph \(H\) with \(n\) vertices and \(m\) arcs is “tournament anti-Sidorenko” if the number of homomorphisms from \(H\) to any tournament \(T\) is at most \((1/2)^m|V(T)|^n\). He, Mani, Nie and Tung conjectured that a random orientation of a long path is tournament anti-Sidorenko with probability at least \(1/2 - o(1)\). We disprove their conjecture by proving that the probability of this event is at most \(0.445 +o(1)\). Our proof uses a Central Limit Theorem of Janson and the Cramér–Wold Device from probability theory together with ideas from combinatorial limits. Joint work with Hao Chen, Felix Christian Clemen and Anastasiia Sharfenberg.
Rui Alde-Lopes, Peter Allen, Juri Barkey, Julia Böttcher, Debsoumya Chakraborti, Dennis Clemens, Francesco Di Braccio, Simon Griffiths, Brian Hearn, Joseph Hyde, Jasmin Katz, Joanna Lada, Alexandru Malekshahian, Sam Mattheus, Adva Mond, Patrick Morris, Tash Morrison, Mihir Neve, Jon Noel, Pedram Noohi, Matías Pavez-Signé, Vincent Pfenninger, Jozef Skokan, Katherine Staden, Cameron Strachan, Leo Versteegen, Luming Zhang.
Please send your open problems to j.boettcher@lse.ac.uk.
Open problems can be found in this Overleaf document.
The workshop dinner is Wednesday 17 Dec at 6.30pm in Aik Sitar (an
indian restaurant).
address: 149 Strand, WC2R
1JA