XavierGoaoc

Archive of posts with tag 'XavierGoaoc'

  • 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:

  • 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:

  • [Lecture series]Xavier Goaoc, Topological methods for discrete geometry

    MFRS Lecture Series

    Topological methods for discrete geometry
    Xavier Goaoc
    Université Paris-Est Marne-la-Vallée, France
    2016/11/04 Fri 5PM-6PM (Lecture 1)
    2016/11/07 Mon 4PM-5PM (Lecture 2)
    Helly’s theorem, a classical result in discrete geometry, asserts that if n>d convex subsets of R^d have empty intersection, some d+1 of them must already have empty intersection. I will discuss some topological generalizations of Helly’s theorem, where convexity is replaced by connectivity assumptions on the nonempty intersections, that lead to non-embeddability results of Borsuk-Ulam type and to variations on Leray’s acyclic cover theorem (or the Nerve theorem).
    Tags:

  • Xavier Goaoc, Embedding complete graphs in surfaces: what about higher dimensions?
    Embedding complete graphs in surfaces: what about higher dimensions?
    Xavier Goaoc
    Université Paris-Est Marne-la-Vallée, France
    2016/11/02 Wed 4PM-5PM
    The fact that the complete graph K5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that Kn embeds in a closed surface M if and only if (n − 3)(n − 4) ≤ 6b1(M), where b1(M) is the first Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of Kn+1 embeds in R2k if and only if n ≤ 2k + 1.
    I will discuss a conjecture of Kuhnel that generalizes both the Heawood inequality and the van Kampen-Flores theorem, and present some partial results toward this conjecture.
    Tags:

  • Xavier Goaoc, Simplifying inclusion-exclusion formulas
    Simplifying inclusion-exclusion formulas
    Xavier Goaoc
    LORIA, INRIA Nancy – Grand Est, Villers-Lès-Nancy cedex, France.
    2012/12/7 Fri 4PM-5PM
    I’ll explain how to construct, given a set system, an inclusion-exclusion formula valid for that set system and with size sensitive to the size of the Venn diagram of the set system. The main ingredient of the proof are random simplicial complexes. The talk will start from first principle.
    This is joint work with J. Matousek, M. Tancer, Z. Safernova and P. Patak from Charles university.
    Tags:

  • Xavier Goaoc, Helly numbers and nerve theorems
    Helly numbers and nerve theorems
    Xavier Goaoc
    LORIA, INRIA Nancy – Grand Est, Villers-Lès-Nancy cedex, France.
    2010/12/10 Fri 4PM-5PM

    The Helly number of a collection of sets is the size of its largest inclusionwise minimal subfamily with empty intersection. The precise conditions that lead to bounded Helly numbers have been studied since the 1920’s, when Helly showed that the Helly number of any collection of compact convex sets in Rd has Helly number at most d+1.

    I will discuss a proof that any collection of subsets of Rd where the intersection of any subfamily consists of at most r connected components, each of which is contractible, has Helly number at most r(d+1). I will show how this implies, in a unified manner, quantitative bounds for several Helly-type theorems in geometric transversal theory.

    Our main ingredients are a new variant of the nerve, a “homological nerve theorem” for this structure and an extension of a projection theorem of Kalai and Meshulam.

    This is joint work with Eric Colin de Verdiere and Gregory Ginot.

    Tags:

Monthly Archives