Profundidad simplicial coloreada (¡finalmente resuelto!)


Un resultado clásico de Bárány en geometría discreta dice lo siguiente (donde \langle S \rangle se refiere a la envolvente convex de S)

Teorema (Carathéodory coloreado, Bárány 1982).

Dados d+1 conjuntos A_1, A_2, \ldots, A_{d+1} en \mathbb{R}^d y un punto y tal que y \in \langle A_i \rangle para cada i, existen puntos x_1 \in A_1, x_2 \in A_2, \ldots, x_{d+1} \in A_{d+1} de tal forma que y \in \langle x_1, x_2, \ldots, x_{d+1}\rangle.

Por ejemplo, en el plano, si hay 3 triángulos monocromáticos que contienen un punto, hay un triángulo heterocromático que también lo atrapa.

Por ejemplo, en el plano, si hay 3 triángulos monocromáticos que contienen un punto, hay un triángulo heterocromático que también lo atrapa.

Una pregunta natural es: si se puede garantizar que hay un simplejo heterocromático que atrapa al punto, ¿cuál es la mínima cantidad \mu (d) de simplejos con esa propiedad que puedo garantizar?  Para esto vamos a suponer que cada conjunto contiene d+1 puntos y y está en el interior de las envolventes convexas (si no, considerando d+1 copias de y, solo obtenemos un simplejo atrapando al punto, por lo que sin suponer algún tipo de posición general el problema no es interesante).

El teorema que mencioné muestra que \mu (d) \ge 1, y la mejor cota superior que se conocía es \mu (d) \le d^2+1, por una construcción de Deza et al. [1], quienes conjeturaban que esta cota era óptima.  Hace poco acaba de salir un manuscrito de Pauline Sarrabezolles, dando una respuesta afirmativa a la conjetura.  Es decir, \mu (d) = d^2+1.

La idea de la demostración se basa en una reducción del problema geométrico a uno combinatorio, estudiando lo que se llaman “configuraciones octaedrales”.  La idea de la reducción nace a partir de las siguientes dos observaciones

  • Una versión fuerte del teorema de Carathéodory coloreado demuestra que solo es esencial que d de los colores contengan al origen [2].  Entonces, para cada vértice de la configuración de puntos, hay un simplejo heterocromático que usa ese vértice y contiene a y.  Esto demuestra automáticamente que \mu (d) \ge d+1, pero queremos más.
  • Si consideramos 2 puntos de cada color, podemos representarlos como los vértices de un octaedro en \mathbb{R}^{d+1}.  Como los simplejos heterocromáticos representan la imagen de las caras de dicho octaedro (el cual es isomorfo a una esfera), cada punto en \mathbb{R}^d está cubierto una cantidad par de veces por dichos simplejos.
Podemos ver a cada simplejo heterocromático como la imagen de alguna cara de un octaedro.

Podemos ver a cada simplejo heterocromático como la imagen de alguna cara de un octaedro.

Entonces uno puede definir una hipergráfica a partir del problema con un vértices por cada punto considerado en \mathbb{R}^d y una hiperarista (de tamaño d+1) por cada simplejo heterocromático que atrapa al punto que queremos.  Entonces, tenemos una hipergráfica con d+1 clases de vértices de tamaño al menos d+1 cada uno de tal forma que

  • Cada vértice está en al menos una arista
  • Si consideramos dos vértices de cada clase, la hipergráfica inducida por ellos tiene una cantidad par de vértices.

La idea es probar que cada hipergráfica de este tipo tiene al menos d^2+1 aristas.  Esto es lo que demuestra Sararabezolles, olvidándose de la primer condición y usando inducción sobre el mínimo número de aristas garantizadas si dicha condición sucede sólo para los vértices de k de las clases.

Les dejo el enlace al artículo de Sarrabezolles.

[1] Deza A., Huang S., Stephen T., and Terlaky T. (2006) Colourful simplicial depth. Discrete and Computational Geometry, 35, pp.597–604.

[2] Arocha, J. L., Bárány, I., Bracho, J., Fabila, R., & Montejano, L. (2009). Very colorful theorems. Discrete & Computational Geometry42(2), pp.142-154.

Anuncios

3 ideas padres para el fin de año


Antes de finalizar el año, me gustaría compartir 3 artículos bonitos que he leído últimamente cuyos resultados me han gustado mucho.  Probablemente merecería cada uno una entrada, pero debido a la falta de uso que le he dado a este blog prefiero mencionarlos juntos.  Solo uno es de este año, pero los 3 son bastante recientes, basados en ideas bonitas y con resultados que me llamaron la atención.

1.  Szemerédi’s Lemma for the Analyst (L. Lovász y B. Szegedi, GAFA 2007)

El lema de Szemerédi es un resultado de teoría de gráficas, que poco a poco se ha vuelto uno de los resultados centrales del área.  Básicamente dice que si “vemos una gráfica de lejos”, se parece mucho una gráfica formada juntando pocas gráficas aleatorias.  Como la estructura de la gráficas aleatorias se conoce muy bien, este resultado nos dice mucho de la estructura de las gráficas sin tener que añadir ninguna hipótesis.  Esto es especialmente útil a la hora de trabajar con gráficas grandes, ya que la información que da este lema es mucho más útil.

El problema de este resultado es que la demostración original es bastante difícil de seguir.  En el artículo que menciono, los autores demuestran un resultado de análisis que resulta ser una generalización de este lemma (y de muchas otras cosas).  Lo sorprendente de esto es que la demostración es de un párrafo, y que la idea central es que dado \epsilon > 0, en cualquier sucesión infinita decreciente de reales no negativos, hay dos términos consecutivos cuya diferencia absoluta es menor que \epsilon.

2. Simple Proofs of Classical Theorems in Discrete Geometry via the Guth-Katz Polynomial Partitioning Techinque (H. Kaplan, J. Matoušek, M. Sharir, DCG 2012)

Los resultados relacionados con particiones de medidas abundan en la geometría discreta.  La idea es encontrar condiciones para que un conjunto grande de medidas en \mathbb{R}^d se puedan partir de manera bonita simultáneamente con una partición de \mathbb{R}^d que cumpla ciertas condiciones.  El enunciado anterior es extremadamente vago, debido a que los resultados de este tipo son extremadamente diversos.

El resultado de particiones de Guth y Katz dice que una medida \mu en \mathbb{R}^d, se puede partir en pedazos conexos de medida a lo más \frac{\mu(\mathbb{R}^d)}{r} usando un polinomio de grado a los más O(r^{1/d}).  Lo más sorprendente de este resultado es la cantidad de aplicaciones que tiene para resolver problemas difíciles.

Guth y Katz lo usaron para resolver casi completamente el problema de Erdös de distancias diferentes, que llevaba abierto casi 70 años.  En este artículo los autores usan esta técnica para dar demostraciones sencillas de resultados clásicos, sobre todo problemas de incidencia, y está escrito de manera que sea auto-contenido.

3.  Erdös-Szekeres Theorem for Lines (I. Bárány, G. Tóth, E. Roldán-Pensado,  2013)

Uno de los teoremas de Erdös y Szekeres más famosos es el siguiente: Para cada mexiste un n=n(m) tal que entre cualesquiera n puntos en el plano en posición general hay m de ellos que están en posición convexa.  Se conjetura que n= 2^{m-2}+1 debe ser la cota óptima, pero actualmente sigue siendo un problema abierto.  Las cotas superiores actuales dan n=O(4^m/\sqrt{m}), lo cual está bastante lejos de la conjetura anterior.

El artículo mencionado habla del mismo problema para líneas en vez de puntos.  Es decir, demuestran que para cada m, existe un l=l(m) tal que entre cualesquiera l líneas en el plano en posición general hay m de ellas que determinan un polígono convexo.  Las cotas obtenidas para l dan l=O(4^m/\sqrt{m}) y sorprendentemente l = \Omega ( 4^m / m).  Esto puede significar una de dos cosas:

  •  Las conjeturas del problema para puntos están lejos de la verdad, o
  • El problema para líneas es mucho más diferente del problema para puntos de lo que uno esperaría.

Yo creo en la segunda, pero no soy bueno haciendo conjeturas.

familias de líneas

De cualquier forma, espero que disfruten de estos artículos (si no los habían leído ya) y que tengan un 2014 muy productivo.

Un problema de generatrices


En enero Javier Cilleruelo me platicó el siguiente problema.

Problema:
Decide si existe un entero k y una sucesión crecientes de enteros a_1, a_2, \ldots de tal forma que para todo entero n suficientemente grande, el número de soluciones a_i + a_j = n, i \le j sea exactamente k

Hay una solución muy bonita usando generatrices, la dejo incluida en la imagen adjunta. El tema está muy relacionado con lo que se conocen como sucesiones de Sidon, pero para hablar de eso probablemente haga una entrada independiente.

Saludos!
Pablo

20130919-223402.jpg

Problem-solving methods in combinatorics


Hace un par de días recibí la noticia de que la versión de mi libro de combinatoria en inglés salió publicada.  El objetivo del libro es mostrar cuales son las técnicas necesarias para resolver problemas de combinatoria, usando constantemente problemas de concursos como ejemplos.  Se cubren los temas necesarios para poder resolver prácticamente cualquier problema de olimpiada pre-universitaria, y creo que todas las ideas que se muestran son aquellas que uno debería tener en mente a la hora de “hacer combinatoria” en general.

978-3-0348-0596-4

 

Hay una versión en español que vende la olimpiada mexicana de matemáticas, pero esta tiene más problemas, más secciones y menos errores.  Si les interesa les dejo el link de Birkhäuser y de amazon.

 

Desahogo: hiperplanos transversales


Bueno, llevo un rato largo sin escribir en este blog, y creo que voy a usar esta entrada como desahogo (desahogo en matmáticas, claro está) más que para comentar algo que considere realmente interesante.  Aquí va una serie de cosas en las que me estuve peleado hace relativamente poco y que de vez en cuando me causan conflicto (probablemente con partes repetidas de entradas interiores.

Dada una familia de conjuntos convexos en \mathbb{R}^d, decidir si hay un hiperplano que intersecta a todos resulta ser un problema bastante complejo.  Esto es porque, a diferencia de tener tener un punto en común (incluso podríamos abusar ligeramente del lenguaje y decir tener un punto transversal), la propiedad tener un hiperplano transversal no adminte un teorema tipo Helly.

Es decir, dada una dimensión d > 1, no existe un número n tal que toda familia \mathcal{F} tal que cada n elementos de \mathcal{F} tienen un hiperplano transversal admite un hiperplano transversal.  Hay que especificar d >1 porque justamente en la línea un punto y un hiperplano son lo mismo (y entonces n=2 funciona).

De aquí uno puede preguntarse por qué falla esto e intentar básicamente dos cosas.  La primera es preguntarse qué es lo que le falta a \mathcal{F} para que se cumpla un teorema de este estilo.  Esto da lugar a teoremas como el siguiente

Teorema de Hadwiger.  Dada una familia de intervalos paralelos en el plano, si cada 3 de ellos tienen una línea transfersal, toda la familia tiene una línea transversal.

El teorema anterior está presentado en su forma más sencilla, y no se necesita mucha herramienta para resolverlo.  Lo que está haciendo el trabajo es que detrás de la familia hay un orden (según cómo están colocados los intervalos) y cualquier transversal parcial intersecta a la familia respetando este orden.  Esto se puede generalizar a dimensiones más grandes, pidiendo que haya cierta estructura en la familia, y que cada transversal parcial la respete.  No voy a meterme en detalles con esto, porque simplemente definir bien cuales son las estructuras buenas llevaría más de una entrada de blog, pero se puede encontrar en [1].

La otra cosa que uno puede hacer es no pelearse con \mathcal{F}, pero con la propiedad que se le está exigiendo al conjunto.  Si pedir que haya un hiperplano transversal es mucho, entonces ¿cuántos hiperplanos necesitamos para intersectar a toda \mathcal{F}?.  A este número lo llamamos h(\mathcal{F}).  A pesar de que las familias \mathcal{F} tales que h(\mathcal{F})=1 se resisten a tener una caracterización bonita, es un parámetro que sí está afectado por propiedades locales.  De manera concreta, admite un teorema tipo (p,q)

Teorema (Alon, Kalai 1995 [2]) .- Dados p \ge q \ge d+1, existe una constante c=c(p,q,d) tal que para toda familia \mathcal{F} de conjuntos convexos en \mathbb{R}^d tal que de cualesquiera p conjuntos de \mathcal{F} hay q de ellos que admiten un hiperplano transversal, se tiene que h(\mathcal{F}) \le c.

En general, buscar familias para las cuales \pi(\mathcal{F}) >1 y encontrar propiedades que implican \pi(\mathcal{F}) = 1 son problemas sorprendentemente diferentes.  En parte porque de un lado queremos checar cada hiperplano para ver que no le pega a toda la familia, y del otro queremos construir un hiperplano particular que le pegue a todos los conjuntos.

Esto da lugar a problemas como el siguiente.

Problema (Lovász): Consideremos X un conjunto de n puntos en \mathbb{R}^d.  Sea \mathcal{F}(X) el mínimo número de simplejos con vértices en X que no tengan un hiperplano transversal.  Consideremos

\displaystyle f(n) = \max \{ f(X) : |X|=n\}

¿Qué tan grande debe ser n para que f(n) sea chico (en términos de d)?

Es claro que si n es suficientemente grande, f(n) \le d+1, pero qué tan grande tiene que ser para tener esa cota (o alguna cota polinomial fija) es una pregunta interesante.  Esto es en parte porque f(2d+1) es exponencial, aunque no tengo la referencia para ello.

Una pergunta un poco semenjante es la siguiente (sobre la que me parece que ya había escrito una entrada),

Problema: ¿Cuál es el menor entero n tal que para cualquier medida \mu en \mathbb{R}^d podemos partir a \mathbb{R}^d en n pedazos de tal forma que

  • cada pedazo tenga la misma medida y
  • no haya ningún hiperplano que le pegue a todos los pedazos?

En este caso, n \le 2^d es un teorema clásico por Yao y Yao, y se sabe que existe una constante C tal que n tiene que ser mayor que C \cdot 2^{d/2}.

Esto significa que en cierto sentido, el espacio de particiones que no tienen un hiperplano transversal es bastante pobre, considerando que es muy dificil usar una partición de ese tipo para dividir homogeneamente a una medida dada.

Peor aún, uno puede emocionarse mucho por el teorema del sándwich de jamón y preguntarse lo siguiente

Pregunta:  ¿Dado un entero positivo d, cuál es el mayor entero positivo n tal que cualesquiera n medidas bonitas en \mathbb{R}^d, uno siempre puede partir \mathbb{R}^d en 4 pedazos distintos usando 2 hiperplanos, de tal forma que cada medida se parte en 4 pedazos iguales?

Suena como que debería funcionar n = d-1, ¿no? Resulta que en muchos casos, lo mejor que se puede obtener es n \sim \frac{2}{3}d [3].  Si uno quiere saber cual es la dimensión d más chica en la que j medidas se pueden partir usando k hiperplanos en 2^k pedazos del mismo tamaño en todas las medidas, se puede obtener d \ge \frac{j(2^k-1)}{k} [4] (que es casi el número de pedazos, lo cual es un poco decepcionante).

En general la impresión que me da es que querer partir medidas con pocos hiperplanos es pedirle demasiado a la geometría.  Esto significa que para problemas de este tipo se necesitan espacios de particiones que permitan mucho más flexibilidad, e incluso querer partir \mathbb{R}^d en pedazos convexos puede que sea un problema (a juzgar por la cantidad de resultados positivos que son mucho más eficientes usando particiones usando polinomios [5]).

[1] Arocha, J. L., Bracho, J., Montejano, L., Oliveros, D., & Strausz, R. (2002). Separoids, Their Categories and a Hadwiger-Type Theorem for Transversals. Discrete & Computational Geometry, 27(3), 377–385. doi:10.1007/s00454-001-0075-2

[2] Alon, N., & Kalai, G. (1995). Bounding the piercing number. Discrete & Computational Geometry, 13(1), 245–256. doi:10.1007/BF02574042

[3] Živaljević, R. T. (2011, November 7). Equipartitions of measures by two hyperplanes. http://arxiv.org/abs/1111.1608

[4] Ramos, E. A. (1996). Equipartition of mass distributions by hyperplanes. Discrete & Computational Geometry, 15(2), 147–167. doi:10.1007/BF02717729

[5] Kaplan, H., Sharir, M., & Matoušek, J. (2011, February 26). Simple Proofs of Classical Theorems in Discrete Geometry via the Guth–Katz Polynomial Partitioning Technique. arXiv.org.

El teorema de Erdös-Ko-Rado


Si n=8, k=4, cualquier familia \mathcal{F} de 35 conjuntos que no contenga dos complementarios funciona (en la figura no hay 35).

Hace poco estuve escribiendo sobre problemas donde la estructura local de intersección de familias de conjuntos tienen consecuencias globales en la familia en sí.  Otro ejemplo muy bueno de esto es el teorema de Erdös-Ko-Rado, que habla de familias de conjuntos de tamaño fijo donde cada par de ellos se intersectan.

Lo sorprendente de este teorema es que hay una solución por Katona [1] basada en un conteo doble muy elegante, de tal manera que hace que el teorema parezca problema de olimpiada.  Lo que dice el teorema es el siguiente

Teorema (Erdös, Ko, Rado 1961) – Sean X un conjunto con n elementos y \mathcal{F} una familia de subconjuntos de X de tamaño k.  Si cada par de conjuntos en \mathcal{F} se intersectan y k \le \lfloor \frac{n}{2} \rfloor, entonces

|\mathcal{F}| \le {{n-1}\choose{k-1}}.

Ver que hay familias con {{n-1}\choose{k-1}} conjuntos es muy fácil.  Basta considerar todos los conjuntos de k elementos que tengan a cierto elemento x_0 fijo.

La idea de Katona consiste en ordenar los elementos de X en un círculo y usar el siguiente lema.

Lema – Sea X un conjunto de n elementos en un círculo.  Si \mathcal{F} es una familia de intervalos de k elementos seguidos, cada dos de ellos se intersectan y k \le \lfloor \frac{n}{2}\rfloor entonces

|\mathcal{F}| \le k.

Probar el lema no es difícil.  Una manera de hacerlo es considerar un intervalo I_0 y dividir \mathcal{F} en los intervalos que contienen al último elemento de I_0 y los que no.  Esto se puede usar para obtener la cota superior del número de intervalos.  Otra manera de hacerlo (y más referencias) se pueden encontrar en [2].

Ya con esto, probar el teorema es bastante sencillo.  Por cada manera de ordenar los conjuntos en un círculo, podemos contar cuántos conjuntos de \mathcal{F} quedan como elementos consecutivos.  Por el lema sabemos que hay a lo más k.  En el círculo hay n intervalos de k elementos consecutivos.  Entonces, si por cada manera de ordenar X en un círculo nos fijamos en los conjuntos de k elementos que están como intervalos de k elementos consecutivos, cada conjunto de k elementos está siendo contado la misma cantidad de veces.  Esto quiere decir que a lo más una proporción \frac{k}{n} de todos esos conjuntos están en \mathcal{F}.  Es decir,

|\mathcal{F}| \le \frac{k}{n}{{n}\choose{k}} = {{n-1}\choose{k-1}}.

Cabe destacar que si le imponemos más condiciones al tipo de intersecciones de los conjuntos, obtenemos condiciones mucho más fuertes sobre el tamaño de la familia.  Por ejemplo, si hay un m tal que cualesquiera dos conjuntos una familia \mathcal{F} de subconjuntos (¡de cualquier tamaño!) de X tienen exactamente m elmentos en común, entonces |\mathcal{F}| \le n.

Lo bonito de estos teoremas es que, en general, las ideas con las que se resuelven son muy elegantes.  La mejor exposición que he visto hasta ahora al respecto es por Frankl y Babai en un libro que (todavía) no sale publicado sobre métodos de álgebra lineal en problemas de combinatoria.  Conseguirlo es una lata, pero es una joya que verdaderamente la pena.

[1] – Katona, G. O. H. (1972). A simple proof of the Erdös-Chao Ko-Rado theorem. Journal of Combinatorial Theory, Series B, 13(2), 183–184.

[2] – Brouwer, A. E., & Schrijver, A. (1979). Uniform hypergraphs. Packing and Covering in Combinatorics, Mathematical Centre Tracts, 106, 39–73.

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.