Combinatorics Seminar

Organisers:

Term 1: Jaehoon Kim and Maryam Sharifzadeh

Term 3 2018/19

 Date Name Title Apr 26 Patrick Morris (FU, Berlin) Tilings in randomly perturbed graphs: bridging the gap between Hajnal--Szemer\'edi and Johansson--Kahn--Vu May 3 TEAM WARWICK Short talks by our own players May 10 Richard Mycroft (Birmingham) Oriented trees in tournaments and other dense digraphs May14-16 Minicourse -- Lorenzo Luperi Baglini (Vienna) Nonstandard combinatorics May 17 Lorenzo Luperi Baglini (Vienna) Partition regularity of nonlinear Diophantine equations May 24 Oliver Roche-Newton (RICAM, Linz) Sets without four term progressions but rich in three term progressions May 31 Alexander Roberts (Oxford) Vertex-isoperimetric stability in the hypercube Jun 6 Tuan Tran (ETH) Subgraph statistics(15:00, MB0.08 We get to play in the new building : ) Jun 7 John Lapinskas (Oxford) Population structure and evolution: A survey of the graph Moran process Jun 14 Péter Pál Pach (Budapest) Jun 21 Sophie Stevens (Bristol) Distinct distances in Finite Fields Jun 28 Iain Moffatt (Royal Holloway Univ London) Tutte polynomials and bialgebras

Term 2 2018/19

 Date Name Title Jan 11 Peter Allen (LSE) Optimal packings of sparse graphs Jan 18 Oliver Janzer (Cambridge) The largest $K_s$-free induced subgraph in a $K_t$-free graph Jan 25 Jason Long (Cambridge) Partial Associativity in Latin Squares Feb 01 David Conlon (Oxford) Online Ramsey numbers Feb 08 Sean Prendiville (Manchester) Nonlinear problems in arithmetic Ramsey theory Feb 15 Mykhaylo Tyomkyn (Oxford) The Brown-Erdos-Sos conjecture in groups Feb 22 Felix Joos (Birmingham) Restricted subgraph embeddings Mar 01 Marius Tiba (Cambridge) On the Erdos Covering problem Mar 07 Katherine Staden (Oxford) The generalised Oberwolfach problem (B3.01, 1:30-2:30PM, Unusual time and location!!!) Mar 08 Max Pitz (Hamburg) Eulerian walks in infinite graphs Mar 15 Adam Wagner (ETH) An extremal problem concerning projective cubes

Term 1 2018/19

 Date Name Title Oct 05 Natalie Behague (QMUL) Hypergraph saturation irregularities Oct 12 John Sylvester (Cambridge) The dispersion time of random walks on finite graphs Oct 19 António Girão (Birmingham) A large number of m-coloured complete infinite subgraphs Oct 26 Andreas Galanis (Oxford) Phase transitions of the independence polynomial Nov 02 Joel Larsson (Warwick) The Minimum Matching problem and a local exploration game Nov 09 Lorenzo Federico (Warwick) Almost connected configuration model Nov 13 Jan Grebik (Czech academy of sciences) Weak* topology and graphons (Please note the unusual time and location) Nov 16 Hong Liu (Warwick) Polynomial Schur's theorem Nov 23 Dong Yeap Kang (KAIST) On the rational Turán exponents conjecture Nov 27 Robert Hancock (Czech academy of sciences) Solution-free sets of integers (Please note the unusual time and location) Nov 30 Andrey Kupavskii (Birmingham) Structure of intersecting families and juntas

Hypergraph saturation irregularities (Natalie Behague), 14:00, MS.04

We say that a graph $G$ is saturated with respect to some graph $F$ if $G$ doesn't contain any copies of $F$ but adding any new edge to $G$ creates some copy of $F$. The saturation number $\text{sat}(F,n)$ is the minimum number of edges an $F$-saturated graph on $n$ vertices can have. This forms an interesting counterpoint to the Turan number; the saturation number is in many ways less well-behaved. For example, Tuza conjectured that $\text{sat}(F,n)/n$ must tend to a limit as $n$ tends to infinity and this is still open. However, Pikhurko disproved a strengthening of Tuza's conjecture by finding a finite family of graphs, whose saturation number divided by $n$ does not tend to a limit. We will prove a similar result for hypergraphs and discuss some variants.

The dispersion time of random walks on finite graphs (John Sylvester), 14:00, MS.04

Consider two random processes on an $n$ vertex graph related to Internal diffusion-limited aggregation (IDLA). In each process $n$ particles perform independent random walks from a fixed origin until they reach an unvisited vertex, at which point they settle. In the first process only one particle moves until settling and then the next starts, in the second process all particles are released together. We study the dispersion time which is the time taken for the longest walk to settle.

We present a coupling which allows us to compare dispersion time across the two processes and show which is ''faster''. We show bounds on the dispersion time(s) in terms of more well studied parameters of random walks such as the cover time and mixing time. In addition we discuss how to determine the order of the dispersion time for many well known graphs such as expanders, complete binary trees, tori etc. This is joint work with Nicol\'{a}s Rivera, Alexandre Stauffer and Thomas Sauerwald.

A large number of m-coloured complete infinite subgraphs (António Girão), 14:00, MS.04

Ramsey Theorem states that for any positive integers $k$ and $m$, whenever the $k$-subsets of the natural numbers are coloured with $m$ colours there always exists an infinite subset $A$ of $\mathbb{N}$ such that $A^{(k)}$, the set of the $k$-subsets of $A$, is monochromatic. In 1975, Erd\H{o}s, Simonovits and S\H{o}s, started a new line of research, commonly known as Anti-Ramsey theory. The problems in this area lie at the opposite end of Ramsey theory, in here one is interested in finding large totally multicoloured (rainbow) substructures.

In this talk we are interested in understanding what happens in between these extremes. Given an edge colouring of a graph with a set of $m$ colours, we say
that the graph is $m$-coloured if all $m$ colours are used. For an $m$-colouring $\Delta$ of $\mathbb{N}^{(2)}$, the complete graph on $\mathbb{N}$, we denote by $\mathcal{F}_{\Delta}$ the set all values $\gamma$ for which there exists an infinite subset $X \subset\mathbb{N}$ such that $X^{(2)}$ is $\gamma$-coloured. Properties of this set were first studied by Erickson in 1994. Here, we are interested in estimating the minimum size of $\mathcal{F}_{\Delta}$ over all $m$-colourings $\Delta$ of $\mathbb{N}^{(2)}$. Indeed, we shall prove the following result. There exists an absolute constant $\alpha > 0$ such that for any positive integer $m \neq \left\{ {n \choose 2}+1, {n \choose 2}+2: n\geq 2\right\}$, $|\mathcal{F}_{\Delta}| \geq (1+\alpha)\sqrt{2m}$, for any $m$-colouring $\Delta$ of $\mathbb{N}^{(2)}$, thus proving a conjecture of Narayanan. This result is tight up to the order of the constant $\alpha$.

Phase transitions of the independence polynomial (Andreas Galanis), 14:00, MS.04

For a graph $G$, let $p_G(\lambda)$ denote the independence polynomial of $G$ with parameter $\lambda$. For which $\lambda$ can we approximate the value $p_G(\lambda)$ on graphs $G$ of maximum degree $\Delta$?

Recently, there have been significant developments in designing approximation algorithms for this problem by examining the location of zeros of the polynomial in the complex plane. In this talk, we will review these developments and establish barriers to the new methods coming from phase transitions in statistical physics and complex dynamics. Based on joint work with Ivona Bezakova, Leslie Ann Goldberg, and Daniel Stefankovic.

The Minimum Matching problem and a local exploration game (Joel Larsson), 14:00, MS.04

Consider the complete bipartite graph on $n+n$ vertices equipped with i.i.d. edge weights, and assume that their common cdf $F$ scales like $F(t)\sim t^q$ near $t=0$ for some $q>0$. The random assignment or minimum matching problem is to find a perfect matching that minimizes the total weight of all included edges. We let $M_n$ be this minimum.

The Mézard-Parisi conjecture states that the limit (in probability) of $M_n$ is $\pi^2/6$ for $q=1$, and more generally that the limit of $n^{-1+1/q} M_n$ exists. The conjecture was confirmed for $q=1$ by Aldous in ’01 and for $q>1$ by Wästlund in ’12. We extend those results to all $q>0$.

Almost connected configuration model (Lorenzo Federico), 14:00, MS.04

The configuration model is a simple and popular way to produce uniform random graphs with a fixed degree sequence. In this talk, we use it to formulate asymptotic conditions on the degree sequence ${d_1, d_2, ..., d_n}$ such that, in the graph generated, the largest component contains $n − o(n)$ vertices. We also provide stricter conditions under which the graph has a non-vanishing probability to be connected. We show that the relevant parameters in this regime are the number of vertices of degree $1$ and $2$, and the average degree, while vertices of higher degree play a minor role. We also derive sharp asymptotics for the number of vertices outside the giant, as a function of these parameters. Our proof uses the method of moments to compute the number of components that are lines or cycles, and employs an exploration algorithm to prove that other kinds of small components are rare. Based on joint work with Remco van der Hofstad and Fiona Sloothaak.

Weak* topology and graphons (Jan Grebik), 15:00, D1.07

I will present how the weak* topology can be used to show that the space of graphons with the cut distance is compact. This is a joint work with Dolezal, Hladky, Rocha and Rozhon.

Polynomial Schur's theorem (Hong Liu), 14:00, MS.04

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

Solution-free sets of integers (Robert Hancock), 15:00, D1.07

Given a linear equation $L$, a set $A$ which is a subset of $[n]:={1,...,n}$ is $L$-free if $A$ does not contain any 'non-trivial' solutions to $L$. We consider the following three general questions:
(i) What is the size of the largest $L$-free subset of $[n]$?
(ii) How many $L$-free subsets of $[n]$ are there?
(iii) How many maximal $L$-free subsets of $[n]$ are there?

We determine (i) precisely for several general classes of linear equations $L$ of the form $px+qy=rz$ for fixed positive integers $p, q, r$ where $p\ge q\ge r$. Further, up to a multiplicative constant, we answer (ii) for a wide class of such equations $L$, thereby refining a special case of a result of Green. For all such linear equations $L$, we give an upper bound for (iii). In the case when $p=q\ge 2$ and $r=1$ this bound is exact up to an error term in the exponent. We make use of container and removal lemmas of Green to prove this result. This is joint work with Andrew Treglown.

On the rational Turán exponents conjecture (Dong Yeap Kang), 14:00, MS.04

The extremal number ${\rm 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 ${\rm ex}(n , F) = \Theta(n^r)$. Several decades ago, Erdős and Simonovits conjectured that every rational number in $[1,2]$ is realisable. Despite decades of effort, the only known realisable numbers are $1, \frac{7}{5}, 2$, and the numbers of the form $1+\frac{1}{m}$, $2-\frac{1}{m}$, $2-\frac{2}{m}$ for integers $m \geq 1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers $1$ and $2$.

We discuss some progress on the conjecture of Erdős and Simonovits. First, we show that $2 - \frac{a}{b}$ is realisable for any integers $a,b \geq 1$ with $b>a$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known ones, and gives infinitely many limit points $2-\frac{1}{m}$ in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable. This is joint work with Jaehoon Kim and Hong Liu.

Structure of intersecting families and juntas (Andrey Kupavskii), 14:00, MS.04

A family of sets is intersecting if any two sets in the family have non-empty intersection. In this talk, I will summarize some of the recent advances in intersecting families. First, I will discuss one general structure theorem for large intersecting families. Next, I will talk about the use of juntas in the study of intersecting families and how to extend to the range n>Ck the results that were known to be valid for n>n_0(k). Finally, I will discuss sharp junta approximation results for shifted families (that are intersecting but not only).

The last part is based on a joint work with Peter Frankl.

Optimal packings of sparse graphs (Peter Allen), 14:00, MS.04

I will describe (another) randomised approach to finding perfect packings of sparse graphs in quasirandom or complete host graphs. The packing algorithm is simple and I will describe it completely; the analysis is not so simple. In particular, we prove that Ringel's Conjecture and the Tree Packing Conjecture are true for almost all trees (or sequences of trees, respectively).

This is joint work with Julia Boettcher, Dennis Clemens, Jan Hladky, Diana Piguet and Anusch Taraz.

The largest $K_s$-free induced subgraph in a $K_t$-free graph (Oliver Janzer), 14:00, MS.04

The Erdős-Rogers function measures how large a $K_s$-free induced subgraph there must be in a $K_t$-free graph on n vertices. Good estimates are known when $t=s+1$, but in general there are significant gaps between the best known lower and upper bounds. We have improved the best known upper bound for $s+2\le t\le 2s-1$. In this talk, I shall describe the construction, and sketch the proof that it has the required properties. This is joint work with Tim Gowers.

Partial Associativity in Latin Squares (Jason Long), 14:00, MS.04

Latin squares arise from the multiplication tables of groups, but the converse is not true in general. Given a Latin square $A$, we can define a group operation giving $A$ as its multiplication table only when $A$ satisfies a suitable associativity constraint. This observation leads to a natural question, originating with Hrushovski, concerning the '1%' version: if $A$ is only partially associative, can we still obtain something resembling a group structure? I will talk about some joint work with Timothy Gowers on this question.

Online Ramsey numbers (David Conlon), 14:00, MS.04

The online Ramsey game is a combinatorial game between two players, Builder and Painter. Starting from an infinite set of isolated vertices, Builder draws an edge at each step and Painter immediately paints the edge red or blue. Builder's goal is to force Painter to create a monochromatic $K_n$ using as few edges as possible. The online Ramsey number $\tilde{r}(n)$ is the minimum number of edges Builder needs to guarantee a win. We discuss recent advances in the study of this function, including an exponential improvement to the lower bound.

Partly based on joint work with Jacob Fox, Andrey Grinshpun and Xiaoyu He.

Nonlinear problems in arithmetic Ramsey theory (Sean Prendiville), 14:00, MS.04

Celebrated results of Rado and Szemerédi characterise which systems of linear equations are ‘unbreakable' with respect to finite partitions and passing to a dense subset (respectively). We discuss variants of these results of a nonlinear flavour.

The Brown-Erdos-Sos conjecture in groups (Mykhaylo Tyomkyn), 14:00, MS.04

The conjecture of Brown, Erdos and Sos from 1973 states that, for any k \geq 3, if a 3-uniform hypergraph H with n vertices does not contain a set of k+3 vertices spanning at least k edges then it has o(n^2) edges. The case k=3 of this conjecture is the celebrated (6,3)-theorem of Ruzsa and Szemeredi, but for all k \geq 4 the conjecture remains open.

Solymosi suggested to study the Brown-Erdos-Sos conjecture when H consists of triples (a, b, ab) in some finite group \Gamma. In this case he proved that the conjecture holds also for k = 4. We prove it in a strong form for all k, and establish a connection to isoperimetric problems on lattices in the process.

Joint work with R. Nenadov and B. Sudakov

Restricted subgraph embeddings (Felix Joos), 14:00, MS.04

In this talk I focus on restricted subgraph embeddings. To be more precise, we allow a host graph $G$ to have an edge colouring and we seek a subgraph $H$ such that every colour appears at most once on the edges of $H$. We only use two simply assumptions. Firstly, every colour appears not too often in $G$ so that it is guaranteed that the number of colours in $G$ is slightly larger than the number of edges of $H$. Secondly, one colour appears not too often at a particular vertex of $G$. Our main result implies in such a setting the existence of $H$ in quasirandom (multipartite) graphs $G$.

This directly implies approximate results of extensions from all trees to all bounded degree graphs of the harmonious labelling conjecture, the Orthogonal Double Cover conjecture, and Kotzig’s conjecture.

This is joint work with Stefan Ehard and Stefan Glock.

On the Erdos Covering Problem (Marius Tiba), 14:00, MS.04

Since their introduction by Erdos in 1950, covering systems (that is, finite collections of arithmetic progressions that cover the integers) have been extensively studied, and numerous questions and conjectures have been posed regarding the existence of covering systems with various properties. In particular, Erdos asked if the moduli can be distinct and all arbitrarily large, Erdos and Selfridge asked if the moduli can be distinct and all odd, and Schinzel conjectured that in any covering system there exists a pair of moduli, one of which divides the other.

Another beautiful conjecture, proposed by Erdos and Graham in 1980, states that if the moduli are distinct elements of the interval $[n,Cn]$, and $n$ is sufficiently large, then the density of integers uncovered by the union is bounded below by a constant (depending only on~$C$). This conjecture was confirmed (in a strong form) by Filaseta, Ford, Konyagin, Pomerance and Yu in 2007, who moreover asked whether the same conclusion holds if the moduli are distinct and sufficiently large, and $\sum_{i=1}^k \frac{1}{d_i} < C$. Although, as we shall see, this condition is not sufficiently strong to imply the desired conclusion, as one of the main results of this paper we will give an essentially best possible condition which is sufficient. More precisely, we show that if all of the moduli are sufficiently large, then the union misses a set of density at least $e^{-4C}/2$, where

$$C = \sum_{i=1}^k \frac{\mu(d_i)}{d_i}$$

and $\mu$ is a multiplicative function defined by $\mu(p^i)=1+(\log p)^{3+\epsilon}/p$ for some $\epsilon > 0$. We also show that no such lower bound (i.e., depending only on~$C$) on the density of the uncovered set holds when $\mu(p^i)$ is replaced by any function of the form $1+O(1/p)$.

Our method has a number of further applications. Most importantly, as our second main theorem, we prove the conjecture of Schinzel stated above, which was made in 1967. We moreover give an alternative (somewhat simpler) proof of a breakthrough result of Hough, who resolved Erdos' minimum modulus problem, with an improved bound on the smallest difference. Finally, we make further progress on the problem of Erdos and Selfridge.

Joint work with Paul Balister, Bela Bollobas, Robert Morris and Julian Sahasrabudhe.

The generalised Oberwolfach problem (Katherine Staden), 13:30, B3.01

Recently, much progress has been made on the general problem of decomposing a dense (usually complete) graph into a given family of sparse graphs (e.g. Hamilton cycles or trees). I will present a new result of this type: that any quasirandom dense large graph in which all degrees are equal and even can be decomposed into any given collection of two-factors (2-regular spanning subgraphs). A special case of this result gives a new proof of the Oberwolfach problem for large graphs.

This is joint work with Peter Keevash.

Eulerian walks in infinite graphs (Max Pitz), 14:00, MS.04

I explain the development of Eulerian walks in infinite graphs from Erdös et al (1938) via Nash-Williams (1960) to a fairly recent topological solution by Diestel and Kühn (2003), the first solution which restores in the infinite case the intuitive appeal that an Eulerian tour should return again, after visiting all edges, to its start vertex. Then I’ll talk about some new results of myself and co-authors that extend Diestel and Kühn's result to hyperbolic graphs and other graph-like structures.

An extremal problem concerning projective cubes (Adam Wagner), 14:00, MS.04

In the Boolean lattice, Sperner's, Erdos's, Kleitman's and Samotij's theorems state that families that do not contain many chains must have a
very specific layered structure. We show that if instead of $Z_2^n$ we work in $Z_{2^n}$, some analogous statements hold if one replaces the word $k$-chain
by projective cube of dimension $2^{k-1}$.

This is joint work with Jason Long.

Tilings in randomly perturbed graphs: bridging the gap between Hajnal--Szemer\'edi and Johansson--Kahn--Vu (Patrick Morris), 14:00, MS.04

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 $0< \alpha <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.

Oriented trees in tournaments and other dense digraphs (Richard Mycroft), 14:00, MS.04
There are numerous fascinating results and conjectures about finding oriented trees within tournaments or other digraphs, including several alluring open problems. I will begin by providing an overview of these, before giving more detail about the following recent developments.
(i) First, we prove that almost all oriented trees are \emph{unavoidable}, meaning that they are contained in every tournament on the same number of vertices. This verifies a 1988 conjecture of Bender and Wormald).
(ii) Second, we show that every oriented tree whose maximum degree is not too large is contained in every directed graph of large minimum semidegree on the same number of vertices. In fact our methods can be applied to some sparse digraphs other than trees.
This is joint work with Tassio Naia.

Minicourse on Nonstandard combinatorics (Lorenzo Luperi Baglini), May 14,15,16, 10:00-11:30, MS.04

Results in Ramsey theory can be studied using techniques coming from several different areas. In this minicourse, we will concentrate on two such areas: ultrafilters and nonstandard analysis.

In the first lecture, we will introduce the Stone–Čech compactification of N and the fundamental notion of idempotent ultrafilter. The relevance of ultrafilters in Ramsey theory will be motivated through several examples.

In the second lecture, we will give a short introduction to nonstandard analysis, focusing on those aspects more related with combinatorics, particularly the nonstandard versions of ultrafilters operations in iterated hyperextensions.

In the third lecture we will focus on several applications of ultrafilters and nonstandard analysis to the study of combinatorial properties of nonlinear Diophantine equations.

Partition regularity of nonlinear Diophantine equations (Lorenzo Luperi Baglini), 14:00, MS.04

In the recent past, several problems regarding the partition regularity of nonlinear configurations have been solved. In this talk, we want to present some general sufficient and necessary conditions for the partition regularity of Diophantine equations, which extend Rado’s Theorem and some other classic result by covering large classes of nonlinear equations. The techniques we use to obtain these conditions are twofold: sufficient conditions are obtained by exploiting algebraic properties in the space of ultrafilters βN, grounding on combinatorial properties of positive density sets and IP sets; necessary conditions are obtained by means of some algebraic considerations based on a nonstandard approach to ultrafilters.

Sets without four term progressions but rich in three term progressions (Oliver Roche-Newton), 14:00, MS.04

The main question that will be addressed in this talk is the following: given a set A which does not contain any four term arithmetic progressions, is it necessarily the case that there exists a large subset of A which does not contain any three term arithmetic progressions?

Perhaps one might guess that the answer is "yes", and that by deleting a relatively small number of elements from A we can destroy all progressions. In fact this rough intuition seems to be false, as we aim to show in this talk by constructing sets (in both the integers and finite field setting) with no 4APs but for which all large subsets contain a 3AP. Possible connections with quantitative bounds for Roth's Theorem will also be discussed. The proof uses the method of hypergraph containers.

This talk is based on ongoing joint work with Cosmin Pohoata

Vertex-isoperimetric stability in the hypercube (Alexander Roberts), 14:00, MS.04

Harper's Theorem states that in a hypercube the Hamming balls have minimal vertex boundaries with respect to set size. In this paper we prove a stability-like result for Harper's Theorem: if the vertex boundary of a set is close to minimal in the hypercube, then the set must be very close to a Hamming ball around some vertex.

Subgraph statistics (Tuan Tran), 15:00, MB0.08

Consider integers k and l such that 0 < l < k(k-1)/2. Given a large graph G, what is the fraction of k-vertex subsets of G which span exactly l edges? When G is empty or complete, and l is zero or k(k-1)/2, this fraction can be exactly 1. On the other hand if l is not one of these extreme values, then by Ramsey's theorem, this fraction is strictly smaller than 1. The systematic study of the above question was recently initiated by Alon, Hefetz, Krivelevich and Tyomkyn who proposed several natural conjectures. In this talk we present solutions of two of them (one asymptotically) and make first steps towards analogous questions for hypergraphs. Our proofs involve some Ramsey-type arguments, and a number of different probabilistic tools, such as polynomial anti-concentration inequalities, hypercontractivity, and a coupling argument.

Joint work with M. Kwan and B. Sudakov.

Population structure and evolution: A survey of the graph Moran process (John Lapinskas), 14:00, MS.04

The graph Moran process is an interacting particle system, somewhat similar to a randomised version of bootstrap percolation, introduced in 2005 as a way to model the spread of mutations in evolutionary biology. Individuals are modelled as vertices on a connected graph, allowing only adjacent individuals to interact. Initially, a single uniformly random vertex is a "mutant" and the remaining vertices are "non-mutants". The process evolves as a Markov chain, with vertices copying their states to their neighbours ("reproducing") at intervals. Mutants are either more or less likely to reproduce than non-mutants, corresponding to a beneficial or harmful initial mutation. Eventually, the entire graph will be filled with either mutants ("fixation") or non-mutants ("extinction"). This framing naturally lends itself to extremal questions, such as: How high can fixation probability be? How long can the process take to absorb? And how small a "jump" can there be between the performance of harmful and beneficial mutations? In this talk, I will survey a number of recent advances on these questions and others.

Colouring the smooth numbers (Peter Pal Pach), 14:00, MS.04

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, \dots, 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.

Distinct distances in Finite Fields (Sophie Stevens), 14:00, MS.04

Over the reals, Guth and Katz resolved the Erdos distance conjecture: how many distinct distances are guaranteed to arise in a set of points over the real plane. How does this problem change if the points are instead elements of two-dimensional vector spaces over finite fields? In joint work with Misha Rudnev and Brendan Murphy, we use tools from incidence geometry to study this problem.

Tutte polynomials and bialgebras (Iain Moffatt), 14:00, MS.04

This talk will focus on graph polynomials, which are polynomial valued graph invariants. Arguably, the most important and best studied graph polynomial is the Tutte polynomial. It is important not only because it encodes a large amount of combinatorial information about a graph, but also because of its applications to areas such as statistical physics (as the Ising and Potts models) and knot theory (as the Jones and homfly polynomials).

Because of its importance the Tutte polynomial has been extended to various classes of combinatorial object. For some objects there is more than one definition of a "Tutte polynomial". For example, there are three different definitions for the Tutte polynomial of graphs in surfaces: M. Las Vergnas' 1978 polynomial, B. Bollobas and O. Riordan's 2002 ribbon graph polynomial, and V. Kruskal's polynomial from 2011. On the other hand, for some objects, such as digraphs, there is no wholly satisfactory definition of a Tutte polynomial. Why is this? Why are there three different Tutte polynomials of graphs in surfaces? Which can claim to be the Tutte polynomial of a graph in a surface? More generally, what does it mean to be the Tutte polynomial of a class of combinatorial objects?

In this talk I will describe a way to canonically construct Tutte polynomials of combinatorial objects, and, using this framework, will offer answers to these questions. I'll initially take a combinatorial approach, before describing why it should be understood as a bialgebra construction.