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

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

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

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.

Xavier Goaoc, Shatter functions of (geometric) hypergraphs

September 7th, 2017
Shatter functions of (geometric) hypergraphs
Xavier Goaoc
Université Paris-Est, Marne-la-Vallée, France
2017/09/25 Mon 4PM-5PM (Room 3433, Bldg. E6-1)
In combinatorial and computational geometry, the complexity of a system of sets is often studied via its shatter function. I will introduce these functions, and discuss how their asymptotic growth rate is governed from a single of its values, in the spirit of the classical notion of “Vapnik-Chernonenkis dimension” of hypergraphs. In particular, I will describe a probabilistic construction that refutes a conjecture of Bondy and Hajnal. This is joint work with Boris Bukh (https://arxiv.org/abs/1701.06632). The talk will start from first principles.

Jaehoon Kim (김재훈), Property testing for hypergraphs

July 15th, 2017
Property testing for hypergraphs
Jaehoon Kim (김재훈)
School of Mathematics, Birmingham University, UK
2017/7/27 Thu 4PM-5PM
We provide a combinatorial characterization of all testable properties of k-graphs (i.e. k-uniform hypergraphs).
Here, a k-graph property 𝒫 is testable if there is a randomized algorithm which quickly distinguishes with high probability between k-graphs that satisfy 𝒫 and those that are far from satisfying 𝒫. For the 2-graph case, such a combinatorial characterization was obtained by Alon, Fischer, Newman and Shapira. This is joint work with Felix Joos, Deryk Osthus and Daniela Kühn.