Past Events

 

 

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.

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).

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.

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.

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.

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.

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!)

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.

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.

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.

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.

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.

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

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.

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.

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(n2) of the maximal possible number of edges can be made into the k-partite Tur\’{a}n graph by adding and deleting o(n2) 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.

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.

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’.

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).

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 n2/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 n2/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.

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.

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.

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.

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?

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