LIAFA Laboratoire d'Informatique Algorithmique: Fondements et Applications CNRS UMR 7089, Université Paris Diderot - Paris 7, Case 701475205 Paris Cedex 13 - Tél: +33(0)1.57.27.92.56 - Fax: +33(0)1.57.27.94.09
 Staff Contact How to get to LIAFA Teaching Webmail

 Seminars

• Date: 2010-11-30/2010-11-30 [14h00]
• Author: Antoine Deza (McMaster University, Hamilton, Ontario, Canada)
• Title: More Colourful Simplices
• Summary:
• A point $p \in R^d$ has {\it simplicial depth} $q$ relative to a set $S$ if it is contained in $q$ closed simplices generated by $(d+1)$ sets of $S$. More generally, we consider {\it colourful simplicial depth}, where the single set $S$ is replaced by $(d+1)$ sets, or colours, ${\bf S}_1,\dots,{\bf S}_{d+1}$, and the {\em colourful} simplices containing $p$ are generated by taking one point from each set. Assuming that the convex hulls of the ${\bf S}_i$'s contain $p$ in their interior, B\a'ar\a'any's colourful Carath\'eodory Theorem (1982) shows that $p$ must be contained in some colourful simplex. We are interested in determining the minimum number of colourful simplices that can contain $p$ for sets satisfying these conditions. That is, we would like to determine $\mu(d)$, the minimum number of colourful simplices drawn from ${\bf S}_1, \dots, {\bf S}_{d+1}$ that contain $p \in R^d$ given that $p \in {\rm int}({\rm conv}({\bf S}_i))$ for each $i$. Without loss of generality, we assume that the points in $\bigcup_i {\bf S}_i \cup\{p\}$ are in general position. The quantity $\mu(d)$ was investigated in Deza et al (2006), where it is shown that $2d \leq \mu(d) \leq d^2+1$, that $\mu(d)$ is even for odd $d$, and that $\mu(2)=5$. This paper also conjectures that $\mu(d)= d^2+1$. Subsequently, B\a'ar\a'any and Matou\v{s}ek (2007) verified the conjecture for $d=3$ and provided a quadratic lower bound for $\mu(d)$, while Stephen and Thomas (2008) independently provided a stronger quadratic lower bound of $\mu(d)$. We further strengthen the previously known lower bounds for $\mu(d)$.

Joint work with Tamon Stephen (Simon Fraser) and Feng Xie (McMaster).

 ©  LIAFA 1995, Last updating: 2013, May webmestre[at]liafa.univ-paris-diderot.fr