Seminars in September 2017

  • Xavier Goaoc, Limits of order types
    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.
    Tags:

  • Sergio Cabello, Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
    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.
    Tags:

  • Xavier Goaoc, Shatter functions of (geometric) hypergraphs
    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.
    Tags:

Monthly Archives