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.

Edgardo Roldán-Pensado, On the colourful Helly theorem

June 26th, 2017
On the colourful Helly theorem
Edgardo Roldán-Pensado
Instituto de Matemáticas, UNAM, Mexico
2017/07/07 Fri 4PM-5PM
Let F be a family of convex sets in R^d coloured using d+1 colours. Lovasz’s Colourful Helly Theorem states that if any colourful subfamily of convex sets is intersecting, then one of the monochromatic families is intersecting. We study what happens with the rest of the families.