Introducción
Como última entradaen esta parte de geometría, hablaremos de algunos temas de geometría discreta. Esta área de las matemáticas se dedica a estudiar propiedades combinatorias de familias de objetos geométricos. Estos objetos pueden ser puntos, rectas, rectángulos, convexos, politopos, etc. Las relaciones que nos interesan son que formen un tipo de acomodo especial, que se intersecten, que podamos contar ciertas configuraciones, etc.
Sólo hablaremos superficialmente de un área que es profunda y bastante interesante. Un libro genial que cubre varios temas de geometría discreta de manera sistemática es Lectures on Discrete Geometry de Jiří Matoušek.
Convexos y el teorema de Helly
Un convexo de es un conjunto tal que cualquier segmento recto definido por dos de sus puntos queda totalmente contenido en el conjunto. Por ejemplo, los convexos de
son los intervalos, mientras que en el plano hay muchos más ejemplos, como lo muestra la figura.

Si tenemos un conjunto de
, su envolvente convexa es el conjunto convexo más pequeño (por contención), que contiene a
. Cuando
es un conjunto de puntos, tenemos algo como lo de la figura. Si todos los puntos de
están sobre la frontera de su envolvente convexa, y no hay tres alineados, decimos que
son puntos en posición convexa.


Los conjuntos convexos son especiales en muchos sentidos. Uno de ellos es que la intersección de una familia de convexos se puede detectar «localmente».
Problema. A una plática de matemáticas de una hora asistieron una cantidad finita de matemáticos. La plática estaba tan aburrida, que cada matemático se durmió en cierto intervalo de tiempo de esa hora, pero sólo una vez. A la hora del café, los matemáticos platicaron entre sí, y si se dieron cuenta de que para cualesquiera dos de ellos, y
, hubo un momento en el que
y
estuvieron dormidos simultáneamente. Muestra que hubo un momento de la plática en la que todos los matemáticos estuvieron dormidos.
Sugerencia pre-solución. Hay muchas soluciones. Una es mediante un argumento de maximalidad.
Solución. En términos matemáticos, queremos ver que si tenemos una cantidad finita de intervalos acotados y cerrados en la recta real que se intersectan de dos en dos, entonces todos ellos se intersectan.
Tomemos el intervalo cuyo extremo derecho sea mínimo. Llamemos
a este extremo derecho. Afirmamos que cualquier otro intervalo tiene a
. Sea
cualquiera de estos intervalos, con extremo izquierdo
y extremo derecho
.

Por la minimalidad de , tenemos que
. Si
, entonces
no intersecta a
y se contradice la hipótesis. Entonces, para que
pueda intersectar a
, necesitamos que
. Pero entonces
queda entre los extremos del intervalo
y por lo tanto
está en
. Esto termina la prueba.
En dimensiones más altas, tenemos el siguiente resultado.
Teorema (Helly). Sea una familia finita de al menos
conjuntos convexos compactos en
. Si cada subfamilia de
de
convexos tiene intersección no vacía, entonces
tiene intersección no vacía.
El teorema de Helly es una de las piedras angulares de la geometría discreta. Una cantidad de enorme de investigación ha resultado de considerar variantes del teorema con hipótesis más débiles o más fuertes.
Politopos y la fórmula de Euler
Otra área muy rica de la geometría discreta es la teoría de politopos. Un politopo es la generalización a altas dimensiones de un polígono, o de un poliedro. Hay dos formas de definir politopos. Una es tomar puntos en y considerar su envolvente convexa. Esto es un
-politopo. Para la otra necesitamos algunas definiciones adicionales.
Un subespacio afín de es la traslación de un subespacio lineal, y su dimensión es la dimensión del subespacio lineal trasladado. Por ejemplo, cualquier punto de
es un subespacio afín de dimensión
pues es la traslación del subespacio trivial
. Las rectas en
, incluso aquellas que no pasan por el
, son subespacios afines de dimensión
. A los subespacios afines de dimensión
les llamamos hiperplanos. Así, las líneas son los hiperplanos de
, los planos los hiperplanos de
, etc.
Si es un hiperplano de
, un semiespacio definido por
es todo lo que queda en uno de los lados de
. Si es abierto, no incluye a
, y si es cerrado, sí incluye a
. Un hiperplano siempre define dos semiespacios abiertos, y dos cerrados.
Hay otra forma de pensar a los politopos: tomamos una cantidad finita de semiespacios cerrados y los intersectamos. Si esa intersección está acotada, entonces a lo que obtenemos le llamamos un -politopo. Piensa, por ejemplo, en los hiperplanos que determinan las caras de un cubo, y en los semiespacios «hacia adentro».
Un resultado clásico es que todo -politopo es un
-politopo, así que podemos usar la descripción que nos convenga de acuerdo al problema que estemos resolviendo.
Un hiperplano es hiperplano soporte de un politopo
si el politopo se queda totalmente contenido en alguno de los semiespacios definidos por
. Una cara de
es la intersección de
con alguno de sus hiperplanos soporte. Resulta que las caras de politopos son politopos. Para que todo funcione bien, debemos considerar al vacío como un politopo.
La dimensión de un politopo es la menor dimensión de un subespacio afín que lo contiene. Por definición, la dimensión del vacío es . Si una cara de un politopo es
, entonces la llamamos una
-cara. Los valores de
sólo pueden ir de
a
. A las
-caras les llamamos los vértices de
. A las
-caras les llamamos las aristas.
Para cada de
a
, usamos
para denotar la cantidad de
caras del politopo, y a

Teorema (fórmula de Euler). Sea un politopo de dimensión
en
. Entonces
Observa que siempre es
pues la única
cara de un politopo
de dimensión
es
mismo.
En esta fórmula no es tan útil, pues simplemente nos dice que si un polígono tiene
vértices y
aristas, entonces
, es decir, que tiene la misma cantidad de vértices y aristas, lo cual es inmediato.
En la fórmula nos dice que si un poliedros tiene
vértices,
aristas y
caras, entonces
Problema. Muestra que el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro son los únicos poliedros en tales que a cada vértice una misma cantidad
de caras, y cada cara consiste de la misma cantidad
de vértices.
Sugerencia pre-solución. Usa notación adecuada, poniendo la cantidad de vértices, aristas y caras en términos de y
. Usa la fórmula de Euler. Luego, da un argumento de desigualdades.
Solución. A cada vértice llegan por lo menos caras, y cada cara tiene por lo menos
vértices. Así,
y
.
Si hay aristas, entonces tanto
como
cuentan la cantidad de parejas
donde
es una arista y
una cara que lo tiene. Esto se debe a que cada arista está exactamente en dos caras, y a que como cada cara tiene
vértices, entonces tiene
aristas. Por lo tanto,
, de donde
De manera similar, si hay vértices y
caras, entonces tanto
como
cuentan la cantidad de parejas
, donde
es un vértice y
es una cara que lo tiene. De esta forma,
, de lo cual
Por la fórmula de Euler, tenemos entonces que





Si multiplicamos por de ambos lados, y sumamos
de ambos lados, tenemos que
(1)
Como , entonces
. De este modo,
Esto muestra que , de modo que
. Por simetría,
. Podemos entonces simplemente estudiar los casos
y
.
Si , entonces la desigualdad (1) se cumple sólo si
. Si
, la desigualdad (1) se cumple sólo si
. Finalmente, si
, la desigualdad se cumple para
. De este modo, las únicas parejas de
que sirven son:
, que nos da el tetraedro.
, que nos da el cubo.
, que nos da el octaedro.
, que nos da el dodecaedro.
, que nos da el icosaedro.
La fórmula de Euler es sólo una de las relaciones lineales que satisfacen las entradas del -vector de un politopo. Otros dos resultados interesantes del área son:
- Las relaciones de Dehn-Sommerville, que dan otras relaciones lineales que satisfacen las entradas del
-vector.
- El teorema de la cota superior que para
,
y
fijas acota el número de
-caras que puede tener un politopo de dimensión
con
-vértices.
Un libro canónico para aprender de politopos de manera sistemática es el Lectures on Polytopes de Günter M. Ziegler.
Conjuntos de puntos y teoremas extremales
La última área de la que hablaremos serán los problemas extremales en geometría discreta. Nos enfocaremos únicamente en problemas sobre conjuntos de puntos, pero se podrían hacer preguntas análogas para otras familias de objetos geométricos. De manera informal, pero intuitiva, un problema extremal de geometría consiste en mostrar que si un número es suficientemente grande, entonces empiezan a pasar cosas interesantes con ciertos objetos geométricos.
Uno de los resultados clásicos es el teorema de Erdős-Szekeres. A grandes rasgos, lo que dice es que si tenemos muchos puntos en posición general en el plano (no hay tres colineales), entonces siempre es posible encontrar un subconjunto grande de ellos que está en posición convexa.
Teorema (Erdős-Szekeres). Sea un entero positivo. Entonces, existe un entero
tal que si se tiene un conjunto
con
o más puntos en el plano en posición general, entonces hay un subconjunto de tamaño
de
que consiste de puntos en posición convexa.
Típicamente, es bastante difícil encontrar los valores exactos de las funciones involucradas en problemas extremales de geometría discreta. El tipo de resultados de interés para la investigación matemática es encontrar las mejores «cotas asintóticas», que digan, más o menos, cómo se comporta la función que se está estudiando. En el caso del teorema de Erdős-Szekeres, las mejores cotas se enuncian así:
La notación quiere decir que
cuando
.
Aunque sea difícil determinar los valores exactos de para toda
, hay algunos valores pequeños que sí se pueden determinar.
Problema. Demuestra que , es decir:
- Que hay conjuntos de
puntos en posición general en el plano que no tienen subconjuntos de tamaño
en posición convexa.
- Que cualquier subconjunto de
puntos en posición general en el plano tiene un subconjunto de
puntos en posición convexa.
Sugerencia pre-solución. Encontrar el ejemplo para el primer punto es fácil, simplemente explora el problema haciendo varias figuras. Divide el problema en casos de acuerdo a la cantidad de puntos que forman la envolvente convexa. Para uno de los casos, usa el principio de las casillas.
Solución. El siguiente ejemplo son puntos que no están en posición convexa, y que por lo tanto no tienen subconjuntos de tamaño
en posición convexa.

Mostraremos ahora que puntos en posición general en el plano siempre tienen un subconjunto de tamaño
en posición convexa. Procedemos por casos de acuerdo a la cantidad de puntos que están en la frontera de la envolvente convexa. Si son
ó
, entonces inmediatamente entre ellos hay
en posición convexa.
Si son , entonces llamemos
,
,
a esos puntos y
y
a los otros dos, que quedan dentro de
. La recta
divide al plano en dos semiplanos. Por principio de las casillas, hay dos puntos de entre
,
y
que yacen en el mismo semiplano, digamos
y
.

Como la recta no corta al segmento
(por estar
y
en el mismo semiplano), y la recta
no corta al segmento
(por ser
un lado de la envolvente convexa), entonces los puntos
,
,
,
están en posición convexa.
Finalmente, presentamos un par de resultados más. También son problemas extremales, pero en vez de hablar de envolventes convexas, hablan acerca de distancias.
Si lo piensas un poco, es imposible colocar puntos distintos en el plano de modo que todas las parejas estén a distancia uno. Si tienes
puntos en el plano, entonces ellos definen
parejas de puntos. ¿Cuántos de ellos pueden estar a distancia
? Estudiar esta cantidad es un problema que fue propuesto por Paul Erdős. Si
denota este máximo, las mejores cotas que hay para el problema son
Aquí es una constante que sirve para toda
. La notación
se refiere a que existe una constante
tal que
para
suficientemente grande.
Por supuesto, la distancia no tiene nada de especial. En realidad, ninguna distancia puede repetirse demasiado. Ya que ninguna distancia aparece muchas veces, la intuición (por principio de las casillas), nos debe decir que entonces para un conjunto de puntos, sus parejas deben definir muchas distancias diferentes. Llamemos
a la cantidad de distancias diferentes que define un conjunto de
puntos en el plano. Erdős también preguntó, ¿cómo se comporta este número?. Las mejores cotas son
La notación se refiere a que existe una constante
tal que
para
suficientemente grande.
El problema de las distancias unitarias y el problema de las distancias diferentes. Han estimulado mucha de la investigación en geometría discreta. Las demostraciones de sus cotas, han introducido al área varias técnicas de teoría de números, del método probabilista y de geometría algebraica.
Un libro con mucho material de problemas extremales y otros temas es Combinatorial Geometry and its Algorithmic Applications de Janos Pach y Micha Sharir.
Más problemas
En resumen, en los siguientes libros hay bastante material para aprender los temas de esta entrada:
- Lectures on Discrete Geometry de Jiří Matoušek
- Lectures on Polytopes de Günter M. Ziegler
- Combinatorial Geometry and its Algorithmic Applications de Janos Pach y Micha Sharir