**Past Combinatorics Seminars**

** 2018/19
**

## Scaling limits of Markov Branching Trees

Consider a population where individuals have two characteristics: a size, which is a positive integer, and a type, which is a member of a finite set. This population reproduces in a Galton-Watson fashion, with one additional condition: given that an individual has size $n$, the sum of the sizes of its children is less than or equal to n. We call multi-type Markov branching tree the family tree of such a population.

As a generalisation of the results of Haas and Miermont on monotype Markov branching trees, we show that under some assumptions (mainly that macroscopic dislocation of a large fragment are rare), Markov branching trees have scaling limits in distributions which are self-similar fragmentation trees, monotype or multi-type.

We then give two applications: the scaling limits of some growth models of random trees, and new results on the scaling limits of multi-type Galton-Watson trees. This is joint work with BÃ©nÃ©dicte Haas.

- Part of Combinatorics and Probability seminar
- Speaker: Robin Stephenson, University of Oxford
- Thursday 04 October 2018, 15:00-16:00
- Watson LTB.

## An isoperimetric approach to some Erdos-Ko-Rado type problems

An Erdos-Ko-Rado (EKR) problem asks for a determination of the maximum possible size of a family of sets, subject to some intersection requirement on the sets in the family. An EKR â€˜stabilityâ€™ problem asks for a description of the families that satisfy this intersection requirement and moreover have size â€˜closeâ€™ to the maximum possible size. We make some progress on various EKR problems and EKR stability problems, via a technique based on isoperimetric inequalities for subsets of the hypercube. We substantially improve an old result of Frankl and Furedi on the maximum possible size of the union of a fixed number of intersecting families of k-element subsets of an n-element set, resolving the question for k < (1/2-o(1))n, and we prove an almost-sharp â€˜stabilityâ€™ result on t-intersecting families of k-element sets, strengthening a result of Friedgut. Based on joint work with Nathan Keller (Bar Ilan University) and Noam Lifshitz (Bar Ilan University).

- Part of Combinatorics and Probability seminar
- Speaker: David Ellis (QMUL)
- Tuesday 09 October 2018, 15:00-16:00
- Arts LR2.

## Polynomial Schur's theorem

I will discuss the Ramsey problem for {x,y,z: x+y=p(z)} for polynomials p over Z.

Joint work with Peter Pach and Csaba Sandor.

- Part of Combinatorics and Probability seminar
- Speaker: Hong Liu, University of Warwick
- Thursday 18 October 2018, 15:00-16:00
- Watson LTB.

## Induced trees and Erdos-Hajnal

A hereditary class of graphs has the Erdos-Hajnal property if there is some c>0 such that every graph G in the class contains a complete graph or independent set of size at least |G|^c. The Erdos-Hajnal Conjecture asserts that for every graph H the class of graphs with no induced copy of H has the Erdos-Hajnal property. Resolving a conjecture of Liebenau, Pilipczuk, Seymour and Spirkl, we show that, for every forest T, the class of graphs with no induced copy of T or its complement has the Erdos-Hajnal property. This is joint work with Chudnovsky, Seymour and Spirkl.

- Part of Combinatorics and Probability seminar
- Speaker: Alex Scott, University of Oxford
- Thursday 25 October 2018, 15:00-16:00
- Watson LTB.

## Analytic functions in Bernoulli percolation

We consider Bernoulli percolation on various graphs/groups and prove that certain functions are analytic in the percolation parameter p. The main arguments we use are combinatorial, and I will emphasize that aspect. I will also give an overview of the history of the percolation theory addressed to the non-expert.

This is joint work with C. Panagiotis.

- Part of Combinatorics and Probability seminar
- Speaker: Agelos Georgakopoulos, University of Warwick
- Thursday 01 November 2018, 15:00-16:00
- Watson LTB.

## Branching Brownian motion with decay of mass

We add a competitive interaction between nearby particles in a branching Brownian motion (BBM). Each particle has a mass, which decays at rate proportional to the mass density in a window centred at the location of the particle. The total mass of the system increases through branching events. In standard BBM , we may define the front location at time t as the location of the rightmost particle. For BBM with decay of mass, it makes sense to instead define the front location as the location at which the local mass density drops to o(1). We can show that in a weak sense this front is (roughly) t^(1/3) behind the front for standard BBM . Several interesting questions about this model remain open. Joint work with Louigi Addario-Berry and Julien Berestycki.

- Part of Combinatorics and Probability seminar
- Speaker: Sarah Penington, University of Bath
- Thursday 08 November 2018, 15:00-16:00
- Watson LTB.

## Counting delta-matroids

Delta-matroids were introduced by Bouchet in the late 1980s but, until recently, have not been studied a great deal since. Examples of them arise from ribbon graphs and matrices, in much the same way as matroids arise from graphs and matrices. In this talk we will give a gentle introduction to delta-matroids illustrated by their connections with ribbon graphs. We will also describe joint work with Daryl Funk and Dillon Mayhew giving bounds on the number of labelled delta-matroids. (There will not be too much matroid theory!)

- Part of Combinatorics and Probability seminar
- Speaker: Steve Noble, Birkbeck, University of London
- Thursday 15 November 2018, 15:00-16:00
- Watson LTB.

## Dynamic monopolies and degenerate sets

Dynamic monopolies are a widely studied model for influence diffusion in social networks. For a graph $G$ and an integer-valued threshold function $\tau$ on its vertex set, a dynamic monopoly is a set of vertices of $G$ such that iteratively adding to it vertices $u$ of $G$ that have at least $\tau(u)$ neighbours in it eventually yields the entire vertex set of $G$.

I present recent bounds, algorithms, and hardness results for minimum dynamic monopolies and its dual problem of maximum degenerate sets.

Some parts are joint work with S. Bessy, C. Brause, L.D. Penso, and D. Rautenbach.

- Part of Combinatorics and Probability seminar
- Speaker: Stefan Ehard, University of Ulm
- Thursday 22 November 2018, 15:00-16:00
- Watson LTB.

## The Namer-Claimer game

Consider the following game played by two players, Namer and Claimer, on the board [n]. In each round, Namer names a forbidden distance d, then Claimer claims a subset of [n] not containing two points at distance d. The game ends once Claimer has claimed all of [n]; Claimer wants this to happen as fast as possible, and Namer wants to delay it. How long is the game with optimal play from each side? The answer reveals a surprising connection with arithmetic Ramsey theory.

- Part of Combinatorics and Probability seminar
- Speaker: Ben Barber, University of Bristol
- Thursday 29 November 2018, 15:00-16:00
- Watson LTB.

## Resilient degree sequences with respect to Hamiltonicity in random graphs

The local resilience of a graph with respect to a property P can be defined as the maximum number of edges incident to each vertex that an adversary can delete without destroying P. The resilience of random graphs with respect to various properties has received much attention in recent years. We investigate a notion of local resilience in which the adversary is allowed to delete a different number of edges at each vertex, and obtain some results which improve on previous results.

This is joint work with P. Condon, J. Kim, D. KÃ¼hn and D. Osthus.

- Part of Combinatorics and Probability seminar
- Speaker: Alberto Espuny, University of Birmingham
- Thursday 13 December 2018, 15:00-16:00
- Watson LTB.

## Highly linked tournaments

In this talk I shall talk about some properties of tournaments. A tournament is k-linked if for every two disjoint subsets A, B of order k and any assignment of the vertices of A to vertices of B there exist k vertex disjoint paths routing the prescribed pairs. We will discuss a recent result which asserts that there exists a function f such that for any positive integer k, if a tournament is 4k-strongly-connected and has minimum out-degree at least f(k), then it is k-linked. This comes close to resolving a conjecture of Pokrovskiy. Along the way, we show that a tournament with sufficiently large minimum out- degree contains a subdivision of a complete directed graph.

- Part of Combinatorics and Probability seminar
- Speaker: AntÃ³nio GirÃ£o (University of Birmingham)
- Thursday 17 January 2019, 13:00-14:00
- Watson LTB.

## Colouring dense random graphs - when can we use the second moment method?

In a colouring of a graph $G$, no two neighbouring vertices are coloured the same, and the chromatic number $\chi(G)$ is the minimum number of colours where this is possible. By definition any colour class is an independent set, so $\chi(G) \ge n/\alpha(G)$ (where $\alpha(G)$ is the independence number).

For the dense random graph $G(n, 1/2)$, Bollob\â€™as proved in 1987 that this lower bound is asymptotically sharp. In other words, there is a colouring with average colour class size $(1-o(1)) \alpha(G)$.

Using a combination of the first and second moment method and martingale concentration arguments, this can be sharpened to determine the average colour class size in an optimal colouring up to an additive $o(1)$, but no further. In this talk, we discuss the main obstacles when applying the second moment method to the number of colourings, or more generally to counts of other structures in $G(n,p)$.

If we introduce certain conditions on the colour class sizes in order to circumvent these obstacles, the second moment method can be used to yield some very sharp results. In particular, both the equitable chromatic number (where colour class sizes may differ by at most $1$) and the $(\alpha-2)$-bounded chromatic number (where we avoid colour classes of size $\alpha$ and $\alpha-1$) are concentrated on at most two consecutive values in $G(n, N/2)$.

Joint work with Konstantinos Panagiotou.

- Part of Combinatorics and Probability seminar
- Speaker: Annika Heckel (University of Oxford)
- Thursday 24 January 2019, 13:00-14:00
- Watson LTB.

## Counting hypergraph colorings in the local lemma regime

I will present a fully polynomial-time approximation scheme (FPTAS) to count the number of q-colorings for k-uniform hypergraphs with maximum degree D if k>=28 and q>315D^{14/(kâˆ’14)}, as well as an accompanying sampling algorithm with slightly worse conditions. These are the first approximate counting and sampling algorithms in the regime q\ll Î” (for large Î” and k) without any additional assumptions. In these regimes, frozen colourings are present, forming an obstacle to the standard Markov chain Monte Carlo approach. Instead, our method is based on the recent work of Moitra (STOC, 2017), in which Lovasz Local Lemma is the key ingredient.

Joint work with Chao Liao, Pinyan Lu, Chihao Zhang

- Part of Combinatorics and Probability seminar
- Speaker: Heng Guo (University of Edinburgh)
- Thursday 31 January 2019, 13:00-14:00
- Watson LTB.

## Rational Turan exponents

The extremal number ex(n,F) of a graph F is the maximum number of edges in an n-vertex graph not containing F as a subgraph. A real number r\in[1,2] is realisable if there exists a graph F with ex(n , F) = \Theta(n^r). Erdos and Simonovits conjectured that every rational number in [1,2] is realisable. We show that 2- a/b is realisable for any integers a,b \geq 1 with b>a and b \equiv \pm 1 mod a. This includes all previously known realisable numbers.

This is joint work with Dong Yeap Kang and Hong Liu.

- Part of Combinatorics and Probability seminar
- Speaker: Jaehoon Kim (University of Warwick)
- Thursday 07 February 2019, 13:00-14:00
- Watson LTB.

## Parking on the integers

Independently at each point in Z; randomly place a car with probability p and otherwise place an empty parking space. Each car independently executes a simple, symmetric random walk until it finds an empty parking space in which to park. How long does a car expect to drive before parking? Taking further a project of Damron, Gravner, Junge, Lyu, and Sivakoff, we show that for p < 1/2 the expected journey length of a car by time t is finite, and for p = 1/2 it grows like t^{3/4} up to polylogarithmic factors.

Joint work with Alexander Roberts and Alex Scott.

- Part of Combinatorics and Probability seminar
- Speaker: MichaÅ‚ Przykucki (University of Birmingham)
- Thursday 21 February 2019, 13:00-14:00
- Watson LTB.

## Stability results for graphs containing a critical edge

The classical stability theorem of Erd\H{o}s and Simonovits states
that, for any fixed graph H with chromatic number k+1 \ge 3, the
following holds: every n-vertex graph that is H-free and has within o(n^{2) of the maximal possible number of edges can be made into the k-partite Tur\â€™{a}n graph by adding and deleting o(n}2)
edges. We prove sharper quantitative results for graphs H with a
critical edge, showing how the o(n^2) terms depend on each other. In
many cases, these results are optimal to within a constant factor. We
also discuss other recent results in a similar vein and some motivation
for providing tighter bounds.

- Part of Combinatorics and Probability seminar
- Speaker: Alex Roberts (University of Oxford)
- Thursday 28 February 2019, 13:00-14:00
- Watson LTB.

## Lagrangians of hypergraphs

Frankl and FÃ¼redi conjectured (1989) that any r-uniform hypergraph, whose edges form an initial segment of length m in the colex ordering, maximises the Lagrangian among all r-uniform hypergraphs with m edges, for all r and m. We prove this conjecture for r=3 (and large m), and disprove it for larger r (and a wide range of m). In the talk I will explain the notion of Lagrangians and focus on the counterexamples to the conjecture.

- Part of Combinatorics and Probability seminar
- Speaker: Shoham Letzter (ETH Zurich)
- Thursday 07 March 2019, 13:00-14:00
- Watson LTB.

## Cycles of length three and four in tournaments

Given a tournament with d*(n choose 3) cycles of length three, how many cycles of length four must there be? Linial and Morgenstern (2016) conjectured that the minimum is asymptotically attained by ``blowing upâ€™â€™ a transitive tournament and orienting the edges randomly within the parts. This is reminiscent of the tight examples for the famous Triangle and Clique Density Theorems of Razborov, Nikiforov and Reiher. We prove the conjecture for d â‰¥ 1/36 using spectral methods. We also show that the family of tight examples is more complex than expected and fully characterise it for d â‰¥ 1/16.

Joint work with Timothy Chan, Andrzej Grzesik and Daniel KrÃ¡lâ€™.

- Part of Combinatorics and Probability seminar
- Speaker: Jon Noel (University of Warwick)
- Thursday 14 March 2019, 13:00-14:00
- Watson LTB.

## Some open questions

I will discuss some open questions I would like to share. This talk will be mostly disjoint from my talk at the London Colloquia (http://www.lse.ac.uk/Mathematics/Events-and-Seminars/2019-Colloquia-in-Combinatorics).

- Part of Combinatorics and Probability seminar
- Speaker: Johannes Carmesin (University of Birmingham)
- Thursday 21 March 2019, 13:00-14:00
- Watson LTB.

## Sharp bounds for decomposing graphs into edges and triangles

In a paper from 1966 ErdÅ‘s, Goodman and PÃ³sa showed that for every
graph G of order n there exists a decomposition of the edges of G into
at most n^{2}/4 complete graphs. In fact, it is enough to
consider only edges and triangles for this decomposition. This is best
possible, as witnessed by the complete balanced bipartite graph. It was
later shown by GyÅ‘ri and Kostochka, by Chung, and by Kahn, that if one
seeks to minimise not the number, but the sum of the sizes of cliques in
a decomposition, the corresponding minimum is n^{2}/2. It was
conjectured by GyÅ‘ri and Tuza that edges and triangles suffice here too,
up to a small constant. We prove this conjecture for large n, and
consider extensions of this problem to other cost regimes. This is joint
work with (various subsets of) Adam Blumenthal, Dan KrÃ¡lâ€™, TaÃsa
Martins, Bernard LidickÃ½, Florian Pfender, Oleg Pikhurko and Jan Volec.

- Part of Combinatorics and Probability seminar
- Speaker: Yanitsa Pehova (University of Warwick)
- Thursday 28 March 2019, 13:00-14:00
- Watson LTB.

## Tilings in randomly perturbed graphs: bridging the gap between Hajnal--Szemer\'edi and Johansson--Kahn--Vu

A perfect $K_r$-tiling in a graph $G$ is a collection of vertex-disjoint copies of $K_r$ that together cover all the vertices in $G$. In this paper we consider perfect $K_r$-tilings in the setting of randomly perturbed graphs; a model introduced by Bohman, Frieze and Martin where one starts with a dense graph and then adds $m$ random edges to it. Specifically, given any fixed $\alpha$ between $0$ and $1-1/r$ we determine how many random edges one must add to an $n$-vertex graph $G$ of minimum degree $\delta (G) \geq \alpha n$ to ensure that, asymptotically almost surely, the resulting graph contains a perfect $K_r$-tiling. As one increases $\alpha$ we demonstrate that the number of random edges required `jumpsâ€™ at regular intervals, and within these intervals our result is best-possible. This work therefore closes the gap between the seminal work of Johansson, Kahn and Vu (which resolves the purely random case, i.e., $\alpha =0$) and that of Hajnal and Szemer\â€™edi (which demonstrates that for $\alpha \geq 1-1/r$ the initial graph already houses the desired perfect $K_r$-tiling).

`This is joint work with Jie Han and Andrew Treglown.`

- Part of Combinatorics and Probability seminar
- Speaker: Patrick Morris, University of Berlin (FU)
- Monday 29 April 2019, 15:00-16:00
- Watson LTB.

## Dynamical Models of Random Simplicial Complexes

Models of scale free random graphs are ubiquitous in their application to network science. Such models encode information about interactions between pairs of vertices, but mechanisms that encode interactions be- tween multiple vertices are less well studied. In this context, recently a number of authors (such as Bianconi and Rahmede) have paid special attention to random evolving simplicial complexes as a suitable model. Motivated by this, we introduce general dynamical models of random simplicial complexes and derive a formula for the asymptotic degree dis- tribution. This asymptotic formula generalises results for a number of existing models, including random Apollonian networks and the weighted random recursive tree. Joint work with Nikolaos Fountoulakis, CÃ©cile Mailler and Henning Sulzbach.

- Part of Combinatorics and Probability seminar
- Speaker: Tejas Iyer, University of Birmingham
- Wednesday 05 June 2019, 15:00-16:00
- Watson LTC.

## Colouring the smooth numbers

For a given n, can we colour the positive integers using precisely n colours in such a way that for any a, the numbers a, 2a, .., na all get different colours? This question is still open in general. I will present a survey of known results and some other problems it leads to. This is joint work with AndrÃ©s Caicedo and Thomas Chartier.

- Part of Combinatorics and Probability seminar
- Speaker: Peter Pach, University of Budapest
- Monday 10 June 2019, 15:00-16:00
- Watson 310.

## Spanning cycles in random directed graphs.

A beautiful coupling argument of McDiarmid shows that, given any orientated n-vertex cycle C, a copy of C almost surely appears in D(n,p) if p=(log n+log log n+omega(1))/n. This is not always optimalâ€”as Frieze had shown, for a directed Hamilton cycle p=(log n+omega(1))/n is sufficient.

This talk will address the following questions, by combining McDiarmidâ€™s coupling with constructive techniques:

- Is p=(log n+omega(1))/n sufficient for the appearance of any oriented n-vertex cycle?

- When is it likely that a copy of all such cycles can be found simultaneously?

- Part of Combinatorics and Probability seminar
- Speaker: Richard Montgomery, University of Birmingham
- Wednesday 19 June 2019, 15:00-16:00
- Watson LTB.

Previous seminars: Autumn 2006, Spring 2007, Autumn 2007, Spring 2008, Autumn 2008, Spring 2009, Autumn 2009, Spring 2010, 2010-2016, 2016/17, 2017/18, 2018/19, 2019/20, 2020/21, 2021/22, 2022/23