Séminaire en optimisation GERAD/CRC-ONDI : Combinatorial, computational, and geometric approaches to the colourful simplicial depth

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's 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, and verify that the conjectured lower bound is tight for dimension 4. Computational approaches for small dimensions and the colourful linear programming feasibility problem introduced by Bárány and Onn are discussed.
Based on joint works with Frédéric Meunier (ENPC Paris), Tamon Stephen (Simon Fraser), Pauline Sarrabezolles (ENPC Paris), and Feng Xie (Microsoft)
---------------------------------------
Important
Ce séminaire vous permettra d’échanger avec le conférencier et les chercheurs présents autour de boissons et de collations.
Nous vous remercions de confirmer votre présence (http://doodle.com/hz2sf8g6khh4nnqn)