2018-19
The seminars are held on Friday at 2pm-3pm |
Organisers: Jaehoon KimMaryam Sharifzadeh |
Term 1 2018/19 - Room MS.04
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) | |
Nov 09 | Lorenzo Federico (Warwick) | Almost connected configuration model |
Nov 16 | ||
Nov 23 | Dong Yeap Kang | On the rational Turán exponents conjecture |
Nov 30 | Andrey Kupavskii (Birmingham) | |
Dec 07 |
Hypergraph saturation irregularities (Natalie Behague)
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)
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)
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)
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.
Almost connected configuration model (Lorenzo Federico)
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.
On the rational Turán exponents conjecture (Dong Yeap Kang)
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.