marzo 3, 2014  

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 Geometry, 42(2), pp.142-154.

diciembre 31, 2013  

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 m, existe 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.

septiembre 20, 2013  

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

abril 6, 2013  

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.

 

febrero 13, 2013  

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.

septiembre 25, 2012  

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.

septiembre 13, 2012  

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.

julio 22, 2012  

Helly para conjuntos finitos


Cuando empecé a escribir este blog mencioné el teorema de Helly, lo que dice es lo siguiente

Teorema 1 (Helly 1924): Sea \mathcal{F} una familia finita de conjuntos convexos en \mathbb{R}^d.  Si cada d+1 de ellos tienen un punto en común, todos los conjuntos de \mathbb{F} tienen un punto en común.

Si uno quita la condición de que los conjuntos sean convexos el teorema se vuelve claramente falso.  La idea general detrás de este teorema es la siguiente.

Dada una familia \mathcal{F} de conjuntos que satisfacen cierta propiedad \phi, propiedades «locales» sobre sus intersecciones tienen consecuencias globales sobre sus intersecciones.  El teorema de Helly es el ejemplo clásico, dónde \phi es «ser conjuntos convexos».  Los teoremas de intersecciones de convexos no son el único lugar donde este tipo de teoremas aparece.  Por ejemplo, si en vez de convexidad le pedimos a los conjuntos que ciertos grupos de homología sean triviales, el teorem se mantiene [1].  Si queremos relajar un poco la condición del teorema, ya no obtenemos una intersección de todos los conjuntos.   Sin embargo, sigue siendo interesante (y usualmente muy difícil) poder demostrar que con pocos puntos podemos interesectar a toda la familia \mathcal{F}.

Lo que quería presentar en esta entrada es una versión de este teorema pero fuera de un sentido geométrico.  Así como en \mathbb{R}^d la condición que funciona para conjuntos finitos es que todos tengan la misma cantidad de elementos.  El teorema es el siguiente:

Teorema 2 (Bollobás 1965):  Sea \mathcal{F} una familia finita de conjuntos de tamaño r.  Si para cada {{r+s}\choose{s}} de ellos existe un conjunto S' de tamaño s que los intersecta a todos, entonces existe un conjunto de S de tamaño s que intersecta a todo \mathcal{F}.

Para ver que el número {{r+s}\choose{s}} es óptimo, basta considerar \mathcal{F} como todos los subconjuntos de tamaño r de un conjunto de r+s elementos.  No es posible intersectar todos con un conjunto de tamaño s, pero sí es posible hacerlo para cualesquiera {{r+s}\choose{s}}-1.

Si el teorema no fuera cierto, podemos ir quitando conjuntos de \mathcal{F} hasta que sin importar cuál conjunto quitemos, podamos encontrar dicho conjunto S.  Supongamos que en este momento los elementos de \mathcal{F} que quedan son A_1, A_2, \ldots, A_m.  Sabemos que al quitar cualquier A_i podermos encontrar un conjunto B_i de tamaño s que intersecta a todos los otros A_j.  Como todo \mathcal{F} no podía ser intersectada con un conjunto de tamaño s, tenemos que A_i y B_i son disjuntos.  Además, sabemos que m > {{r+s}\choose{s}}.  Con esto, basta demostrar lo siguiente:

Teorema 3 (Bollobás 1965).  Sean A_1, A_2, \ldots, A_m conjuntos de tamaño r y B_1, B_2, \ldots, B_m conjuntos de tamaño s tales que A_i \cap B_j \neq \emptyset si y solo si i \neq j.  Entonces m \le {{r+s}\choose{s}}.

La siguiente demostración es de Lovász y hace uso del álgebra exterior (cosa que es sorprendente si consideramos que el problema es completamente combinatorio).

Demostración: Sea X la unión de todos los A_i y B_i.  Sin pérdida de generalidad podemos considerar que X es un subconjunto de \mathbb{R}^{r+s} de tal forma que cualesquiera r+s puntos de X son linealmente independientes.  Dado U = \{u_1, u_2, \ldots, u_k\} definimos \wedge_U = u_1 \wedge u_2 \wedge \cdots \wedge u_k el producto exterior de sus elementos.  Vamos a demostrar que \wedge_{A_1}, \wedge_{A_2}, \ldots, \wedge_{A_m} son linealmente independientes.  Para eso consideremos una combinación lineal de ellos que dé 0, es decir

( \lambda_1 \wedge_{A_1}) + \lambda_2 (\wedge_{A_2}) + \ldots + \lambda_m (\wedge_{A_m}) = 0

Si consideramos el producto exterior con \wedge _{B_i} tenemos que (\wedge_{A_j})\wedge (\wedge_{B_i}) es el producto exterior de todos los elementos de A_j y B_i.  Si i \neq j, hay al menos un elemento repetido en este producto exterior, por lo que da 0.  Esto implica que

\lambda_i [(\wedge_{A_i})\wedge(\wedge_{B_i})] = 0.  Como A_i \cup B_i es un conjunto linealmente independiente, el producto exterior de sus elementos no es 0, por lo que \lambda_i = 0.  Con esto tenemos que todos los coeficientes son 0, por lo que los \wedge_{A_i} son linealmente independientes.

Sin embargo, cada uno de ellos es el producto exterior de r elementos de W, por lo que están en un espacio vectorial de dimensión {{\mbox{dim }W}\choose{r}} = {{r+s}\choose{s}}.  Con esto, no puede haber más de  $latex {{r+s}\choose{s}}$ de ellos, como se quería probar.

[1] Debrunner, H. (1970). Helly type theorems derived from basic singular homology. The American Mathematical Monthly, 77(4), 375–380.

May 3, 2012  

Teoría de conjuntos y geometría


Hace poco me encontré con un survey de Péter Komjáth acerca de construcciones tipo teoría de conjuntos en el plano (o espacios Euclidianos) que dan lugar a conjuntos con propiedades geométricas significativas.

Esto me llamó la atención porque es de las pocas aplicaciones que he visto del axioma de elección (y otras herramientas) que no usan la versión «lema de Zorn y el orden dado por contención», y dan lugar a conjuntos con propiedades bastante raras.  Creo que la construcción conjuntista relacionada a geometría más famosa es la paradoja de Banach-Tarski, pero todas las que voy a mencionar a continuación son muy diferentes.

Para motivar una de estas construcciones, aquí va un teorema bastante bonito acerca de colinearidad.

Teorema (Silvester-Gallai 1944):  Dado un conjunto finito H de puntos en el plano, si por cada dos puntos de H hay otro punto de H colineal con ellos, entonces todos son colineales.

Es decir, si cada línea que pasa por dos de ellos contiene al menos tres del conjunto, todos deben ser colineales.  Es muy fácil ver que la condición de que el conjunto sea finito es absolutamente necesaria, ya si consideramos todo el plano obtenemos un conjunto dónde cada línea que pasa por dos de ellos (es decir, cualquier línea) contiene al menos 3 de ellos.  Si quieren un conjunto más chico, la latiz de puntos con coordenadas enteras sirve.  Sin embargo, usando el axioma de elección podemos hacer una construcción bastante más peculiar.

Teorema (Mazurkiewicz 1914): Existe un conjunto H del plano de tal forma que intersecta a cada línea en exactamente 3 puntos.

La idea de la demostración es sencilla (si no saben sobre inducción con ordinales, pueden saltarse este párrafo).  Primero, consideramos \omega_1 el menor ordinal de tamaño | \mathbb{R}^2| y ordenamos al conjunto de líneas como \{ L_\alpha : \alpha < \omega_1\} (los \alpha son ordinales).  Ahora queremos usar inducción transfinita para elegir puntos en cada L_\alpha de tal manera que en cada línea haya 3 puntos.  Lo único con lo que tenemos que tener cuidado al completar L_\alpha no pongamos puntos colineales con al menos 2 puntos ya elegidos.  Sin embargo, al llegar a la línea L_\alpha hay a lo más | \alpha| ^2 = |\alpha | < |\mathbb{R}^2| = |\mathbb{R}| parejas de este tipo, y cada una niega a lo más un punto de L_\alpha.  Con esto podemos evitarnos los problemas y seguir construyendo el conjunto.

Con este tipo de ideas se pueden generar mucho más conjuntos raros, por ejemplo se consiguen los siguientes

Teorema (Sierpinski 1958): Existen dos subconjuntos A, B del plano de tal manera que para cualquier traslación \phi, el conjunto \phi (A) \cap B tiene exactamente un elemento.

Un problema tipo olimpiada es demostrar que el espacio se puede ver como la unión de círculos ajenos.  Esto se puede hacer con estas técnicas, pidiendo además que los planos que generan a estos círculos estén en posición general, o que todos los círculos tengan radio 1.

Cabe destacar que hay casos en los que este tipo de inducción no es suficiente, pero con trucos de este estilo se obtienen teoremas más fuertes.  Un ejemplo particularmente bonito es el siguiente

Teorema (Erdös, Hajnal 1969):  Se puede colorear el plano con una cantidad numerable de colores de tal manera que no hay dos puntos diferentes cuya distancia es racional y estén coloreados del mismo color.

La inducción en ordinales como la que se usa en el caso anterior no funciona, pero los detalles técnicos se arreglan sin usar herramientas más avanzadas.  Curiosamente si cambiamos la palabra «racional» por «entero», no se sabe si se puede reducir el número de colores a una cantidad finita.  Es decir,

Problema (David Larman): Decidir si existe un entero $late N$ de tal manera que el plano se puede colorear con N colores de tal manera que no haya parejas de puntos diferentes del mismo color cuya distancia sea un entero.

De hecho si uno cambia la condición de prohibir distancias enteras por prohibir distancias 1, el valor de $late N$ no se sabe, nada más se conoce 4 \le N \le 7.

Con este tipo de ideas incluso se pueden encontrar formas equivalentes de la hipótesis del contínuo, como la siguiente:

Teorema (Sierpinski): La hipótesis del contínuo es equivalente a la afirmación de que R^2 es la unión de dos conjuntos A, B de tal forma que cada línea horizontal intersecta a A en una cantidad a lo más numerable de puntos y cada línea vertical intersecta a B en una cantidad a lo más numerable de puntos.

abril 17, 2012  

El premio Abel 2012


Escribí una nota sobre el premio Abel del 2012 (que fue otorgado a Endre Szemerédi).  Es una noticia importante, en especial porque ahora este tipo de reconocimientos se están dando también a matemáticos que trabajan en áreas discretas.  Les dejo el enlace para no quitarle visitas a los hijos de la malinche con un reblog.

http://www.loshijosdelamalinche.com/ciencia/el-premio-abel-16042012

« Older Posts