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: álgebra lineal, Caratheodory, Convexos, Geometría combinatoria, Producto Tensorial, Sarkaria, Truco, Tverberg

Esta entrada fue publicada el septiembre 13, 2012 en 2:19 pm y está archivada dentro de Combinatoria, Geometría, LaTeX, Matemáticas Universitarias. Puedes seguir las respuestas de esta entrada a través de sindicación RSS 2.0. Puedes dejar una respuesta, o trackback desde tu propio sitio.

Deja un comentario Cancelar respuesta

Añade tu comentario aquí...

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

Correo electrónico (obligatorio) (La dirección no se hará pública)

Nombre (obligatorio)

Sitio web

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

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

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

Cancelar

Conectando a %s

Blog de Pablo