Archive for the ‘2017’ Category

Jaehoon Kim (김재훈), Spanning trees in a randomly perturbed graphs

Thursday, December 21st, 2017
Spanning trees in a randomly perturbed graphs
Jaehoon Kim (김재훈)
School of Mathematics, Birmingham University, UK
2017/12/28 Thursday 2PM-3PM (Room 3433)
A classical result of Komlós, Sárközy and Szemerédi states that every n-vertex graph with minimum degree at least (1/2 +o(1))n contains every n-vertex tree with maximum degree at most O(n/log n) as a subgraph, and the bounds on the degree conditions are sharp.
On the other hand, Krivelevich, Kwan and Sudakov recently proved that for every n-vertex graph G with minimum degree at least αn for any fixed α>0 and every n-vertex tree T with bounded maximum degree, one can still find a copy of T in G with high probability after adding O(n) randomly-chosen edges to G.
We extend this result to trees with unbounded maximum degree. More precisely, for a given nε ≤ Δ≤ cn/log n and α>0, we determined the precise number (up to a constant factor) of random edges that we need to add to an arbitrary n-vertex graph G with minimum degree αn in order to guarantee with high probability a copy of any fixed T with maximum degree at most Δ. This is joint work with Felix Joos.

Hong Liu, On the maximum number of integer colourings with forbidden monochromatic sums

Sunday, December 3rd, 2017
On the maximum number of integer colourings with forbidden monochromatic sums
Hong Liu
Mathematics Institute, University of Warwick, Warwick, UK
2017/12/27 Wed 4PM-5PM (Room 3433)
Let f(n,r) denote the maximum number of colourings of A⊆{1,…,n} with r colours such that each colour class is sum-free. Here, a sum is a subset {x,y,z} such that x+y=z. We show that f(n,2) = 2⌈n/2⌉, and describe the extremal subsets. Further, using linear optimisation, we asymptotically determine the logarithm of f(n,r) for r≤5.

Jonathan Noel, The Best Way to Spread a Rumour in a High-Dimensional Grid

Wednesday, October 18th, 2017
The Best Way to Spread a Rumour in a High-Dimensional Grid
Jonathan Noel
University of Warwick, UK
2017/11/14 Tue 4PM-5PM (Room 3433, Bldg. E6-1)
Bootstrap percolation is a simple process which is used as a model of propagation phenomena in real world networks including, for example, the spread of a rumour in a social network, the dynamics of ferromagnetism and information processing in neural networks. Given a graph G and an integer r, the r-neighbour bootstrap process begins with a set of “infected” vertices and, in each step, a “healthy” vertex becomes infected if it has at least r infected neighbours. A central problem in the area is to determine the size of the smallest initial infection which will spread to every vertex of the graph. In this talk, I will present a trick for obtaining lower bounds on this quantity by transforming the problem into an infection problem on the edges of the graph and applying some basic facts from linear algebra. In particular, I will outline a proof of a conjecture of Balogh and Bollobás (2006) on the smallest infection which spreads to every vertex of a high-dimensional square lattice and mention some potential applications to analysing the behaviour of a random infection in this setting. This talk is based on joint work with Natasha Morrison.

Xavier Goaoc, Limits of order types

Thursday, September 7th, 2017
Limits of order types
Xavier Goaoc
Université Paris-Est, Marne-la-Vallée, France
2017/09/29 Fri 4PM-5PM (Room 3433, Bldg. E6-1)
The limits of converging sequences of graphs are natural objects from extremal graph theory that are also representable as measure-theoretic objects (graphons) or as algebraic objects (flag algebra homomorphisms). I will give an introduction to this theory via a geometric relative: its adaptation from graphs to a combinatorial encoding of planar point sets. This is based on joint work with Alfredo Hubard, Rémi de Joannis de Verclos, Jean-Sébastien Sereni and Jan Volec (http://drops.dagstuhl.de/opus/volltexte/2015/5126/). The talk will not assume any specific knowledge.

Sergio Cabello, Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

Thursday, September 7th, 2017
Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
Sergio Cabello
Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia
2017/09/26 Tue 4PM-5PM (Room 3433, Bldg. E6-1)
We show how to compute for n-vertex planar graphs in roughly O(n11/6) expected time the diameter and the sum of the pairwise distances. These are the first algorithms for these problems using time O(nc) for some constant c<2, even when restricted to undirected, unweighted planar graphs.