Una demostración del teorema de Tverberg

Caso k=3, d=2, 7 puntos.

El teorema de Tverberg es uno de mis teoremas favoritos en geometría combinatoria.  La idea detrás del teorema es que si uno tiene muchos puntos en \mathbb{R}^d, deberíamos poder partirlos en varios pedazos de tal forma que las envolventes convexas de cada uno tengan un punto en común.  Este teorema dice exactamente qué tantos puntos son necesarios para esto.

Desde que Tverberg dio la primer demostración de este hecho en 1966, han aparecido otras más cortas y más elegantes a lo largo de los años, con una demostración espectacular por Sarkaria en 1992.  La demostración de Sarkaria se ha difundido mucho, y encontrar textos o blogs muy buenos que la expliquen no es muy complicado (un buen ejemplo sería el blog de Gil Kalai).  Sin embargo, como no he visto ninguna versión de esto en español, y últimamente he trabajado con problemas “tipo Tverberg”, creo que vale la pena dedicarle una entrada.  Lo que dice el teorema es lo siguiente:

Teorema (Tverberg 1966) – Dado un conjunto S de (k-1)(d+1)+1 puntos en \mathbb{R}^d, es posible encontrar una partición A_1, A_2, \ldots, A_k de S en k pedazos de tal forma que

\displaystyle \bigcap_{i=1}^k \langle A_i \rangle \neq \emptyset

Donde \langle X \rangle significa la envolvente convexa de X.

El caso k=2 se conoce como el lema de Radon o el Teorema de Radon, y fue demostrado en 1921.  Para este nada más se necesita álgebra lineal básica.  Curiosamente lo que hace el argumento de Sarkaria es reducir la parte combinatoria del teorema a un problema métrico.  Lo que se necesita para esto son dos ingredientes.  El primero es el teorema de Carathéodory coloreado.

Teorema (Carathéodory coloreado) – Dadas d+1 familias de puntos \mathcal{F}_1, \mathcal{F}_2, \ldots, \mathcal{F}_{d+1} en \mathbb{R}^d tales que cada una de ellas atrapa al origen, podemos encontrar puntos x_1 \in \mathcal{F}_1, x_2 \in \mathcal{F}_2, \ldots, x_{d+1} \in \mathcal{F}_{d+1} de tal forma que el conjunto \{ x_1, x_2, \ldots, x_{d+1} \} también atrapa al origen.

Con decir que un conjunto X atrapa al origen nos referimos a que 0 \in \langle X \rangle.

Este teorema es realmente métrico.  Se le llama “coloreado” porque podemos pensar que cada familia \mathcal{F}_i está pintada de algún color, y lo que queremos es un simplejo heterocromático que atrapa al origen.  Si esto no sucede, podemos considerar el simplejo heterocromático más cercano al origen y ver qué color le falta a su cara más cercana al 0.  Si todo funciona bien, demostrar que los puntos de ese color no atrapan al origen debería ser fácil.

El segundo ingrediente es el producto tensorial.  Dados dos vectores x = (x_1, x_2, \ldots, x_m) \in \mathbb{R}^m, y = (y_1, y_2, \ldots, y_n)\in \mathbb{R}^n, el producto tensorial x \otimes y es un vector en \mathbb{R}^{m \times n} tal que la entrada (i,j)-ésima es x_i y_j.  Lo único que nos interesa de este producto por el momento es que es una función bilineal de \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R} ^{m \times n}.

Ahora sí, la idea brillante.  La idea brillante es considerar k vectores u_1, u_2, \ldots, u_k en \mathbb{R}^{k-1} que sean los vértices de un simplejo regular que atrapa al origen.  Que sea regular realmente no es tan importante, pero facilita muchísimo las cuentas.  Lo importante de estos vectores es que una combinación lineal de ellos satisface

\alpha_1 u_1 + \alpha_2 u_2 + \ldots + \alpha_k u_k = 0

si y solo si

\alpha_1 = \alpha_2 = \ldots = \alpha_k.

Consideremos n= (d+1)(k-1) y  a_1, a_2, \ldots, a_{n+1} nuestros puntos en \mathbb{R}^d.  Podemos agregarles a todos una entrada 1 al final.  Es decir, considerar los puntos b_i = (a_i, 1) \in \mathbb{R}^{d+1}.  Esto es un paso estándar para convertir problemas “afines” en problemas “lineales”, abusando un poco del lenguaje.  Ahora consideremos los puntos b_i \otimes u_j con 1 \le i \le n+1, 1 \le j \le k.  Estos son puntos que viven en \mathbb{R}^n.  Si los acomodamos como en la figura, notemos que cada columna atrapa al origen (porque los u_i lo hacían).

Entonces, por el teorema de Carathéodory coloreado, podemos elegir un elemento de cada columna de tal forma que el conjunto que obtenemos atrapa al origen.  Es decir, para cada 1 \le i \le n+1 existe un j(i) \in \{1,2, \ldots, k\} de tal forma que el conjunto \{ b_1 \otimes u_{j(1)}, b_2 \otimes u_{j(2)}, \ldots, b_{n+1} \otimes u_{j(n+1)}\} atrapa al origen.  Los j(i) van a definir nuestra partición, por lo que conviene considerar los conjuntos I_1, I_2, \ldots, I_k tales que

I_j = \{ i \in \{ 1,2, \ldots, n+1\} : j(i) = j\}

Ahora sí, como \{ b_1 \otimes u_{j(1)}, b_2 \otimes u_{j(2)}, \ldots, b_{n+1} \otimes u_{j(n+1)}\} atrapa al origen, tenemos que hay coeficientes no negativos \beta_i que suman 1 de tal forma que

\displaystyle \sum_{i=1}^n \beta_i (b_i \otimes u_{j(i)} ) = 0

Podemos usar la linealidad del producto tensorial para factorizar los u_j, de tal forma que

\displaystyle \sum_{j=1}^k \left[ \left( \sum_{i \in I_j} \beta_i b_i \right) \otimes u_j \right] = 0

(nota: si intentan escribir la ecuación de arriba expandiendo la primer suma, el compilador de \LaTeX de wordpress se niega a hacerlo, incluso si la parten en cachos).

La magia de la demostración es que la necesidad de que los coeficientes de una combinación de los u_j que de 0 sean iguales se transfiere directamente en el producto tensorial.  Es decir,

\displaystyle \sum_{i \in I_j} \beta_i b_i

es el mismo punto para cada j.

Viendo las primeras d coordenadas, obtenemos que \displaystyle \sum_{i \in I_j} \beta_i a_i es el mismo punto para cada j.  Usando que la última coordenada es 1, obtenemos que \displaystyle \sum_{i \in I_j} \beta_i tiene el mismo valor (positivo) para cada j, por lo que podemos suponer que es 1.

Con esto obtenemos que los pedazos A_j = \{ i : i \in I_j\} forman la partición que buscabamos.

About these ads

Etiquetas: , , , , , , ,

About pablosoberon

Mi twitter: www.twitter.com/pablosoberon

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

Únete a otros 25 seguidores

A %d blogueros les gusta esto: