Tutte seminar - Antoine Deza

Combinatorial, computational, and geometric approaches to the colourful simplicial depth

Abstract:

In statistics, there are several measures of the depth of a point p relative to a fixed set S of sample points in dimension d. One of the most intuitive is the simplicial depth of p introduced by Liu (1990), which is the number of simplices generated by points in S that contain p. Obtaining a lower bound for the simplicial depth is a challenging problem. Carathéodory Theorem can be restated as: The simplicial depth is at least 1 if p belongs to the convex hull of S. Bárány (1982) showed that the simplicial depth is a least a fraction of all possible simplices generated from S. Gromov (2010) improved the fraction via a topological approach. Bárány's result uses a colourful version of Carathéodory Theorem leading to the associated colourful simplicial depth. We present recent generalizations of the Colourful Carathéodory Theorem due to Arocha et al. and Holmsen et al. and our strengthening of these. We provide a new lower bound for the colourful simplicial depth improving the earlier bounds of Bárány and Matoušek and of Stephen and Thomas. Computational approaches for small dimensions and the colourful linear programming feasibility problem introduced by Bárány and Onn are discussed. 

Based on joint work with Frédéric Meunier (ENPC Paris), Tamon Stephen (Simon Fraser), Pauline Sarrabezolles (ENPC Paris), and Feng Xie (Microsoft).