Realización geométrica de gráficas.

Question

Dada una gráfica $G = (V,A)$ (posiblemente infinita) entiendo como una realización geométrica de $G$ una función $r: V \to \mathbb{R}^n$ (para alguna $n$) de tal suerte que los segmentos de recta determinados por los elementos de $A$ no se intersecten. 

1. ¿Toda gráfica finita tiene realización geométrica?
2. ¿Qué pasa con las gráficas inifinitas?

Answer 1

Todas las gráficas tal que la cardinalidad del conjunto de sus vértices es menor o igual a la cardinalidad del continuo se pueden realizar en $\mathbb{R}^3$. En particular, todas las gráficas finitas o numerables caben cómodamente en $\mathbb{R}^3$ y lo que dice Carlos acerca del simplejo en el cubo de Hilbert no es cierto. (Y claramente si una gráfica tiene más vértices que la cardinalidad del continuo, ¡no cabe en ningún $\mathbb{R}^n$!)

El truco es usar una curva famosa en $\mathbb{R}^3$ llamada la cúbica torcida: la curva parametrizada por $t \mapsto (t^3, t^2, t)$. No hay cuatro puntos coplanares sobre esa curva pues la intersección de una plano $ax+by+cz+d=0$ con la cúbica torcida se obtiene resolviendo la ecuación cúbica $at^3+bt^2+ct+d=0$ que tiene a lo más tres soluciones. Si tomas puntos sobre la cúbica torcida no solo los segmentos que une pares de ellos no solo no se cortan, ni siquiera las rectas completas se cortan.

Comments

No le he pensado mucho, pero supongo que el mismo argumento funciona para encajar hipergráficas en el adecuado $\mathbb{R}^n$.
Por ejemplo, la 2-hipergráfica regular completa de $n$ vértices tiene como aristas cada triángulo (tiene ${n \choose 3}$ hiperaristas). Así, cada cara es de dimensión 2. Cada par de puntos vive en $n-2$ hiperaristas. Puedes permitir que se intersecten dos hiperaristas en sus respectivas fronteras, pero no el los interiores (notemos que aquí, el interior lo vemos en un objeto de dimensión 2, el análogo para gráficas es que no permitimos cruces).
¿Cuál es la mínima dimensión donde cabe sin que se "autointersecte"?
Saludos.

---

La mera verdad, esta respuesta sí me dejó boquiabierto... primero dices que cualquier gráfica con a lo más $\mathfrak c$ vértices cabe en $\mathbb R^3$, lo cual es sorprendente. Apenas me voy recobrando de la impresión, y voy comenzando a pensar: "claro, debe ser posible hacer algo por inducción transfinita"... ¡y entonces todavía sacas la cúbica torcida, la cual es por supuesto mucho más simple!

Answer 2

Para cada $n$, considera en $\mathbb{R}^n$, el $n+1$ simplejo generado por la envolvente convexa del origen y los $n$ vectores canónicos $e_i$ (que tienen 1 en la i-ésima coordenada y ceros en otra parte). Las aristas de este $n$ simplejo es la realización geométrica de una gráfica completa de $n+1$ vertices. Toda grafica finita se puede ver dentro de la  gráfica completa con el mismo número de vertices, la realización anterior induce una realización geométrica de cualquier subgrafica.

Con la misma anterior, las aristas del simplejo generado por los $e_i$ en el cubo de Hilbert, es una gráfica infinita, que no puede realizarse dentro de ningún espacio Euclideano.

Comments

Vientos, aunque yo llamaría $n$-simplejo al de $n+1$ vértices. Cuestión de nombres.

---

Creo que tienes razón y esa es la notación estandard. Sin embargo, si notas que el triángulo es el simplejo en dimensión dos y el tetraedro en dimensión tres. Se antoja que el $n+1$ simplejo viva en $\mathbb{R}^n$. :)

---

Lo que dices sobre la gráfica completa numerable es falso, se puede realizar en $\mathbb{R}^3$ usando puntos sobre la cúbica torcida. Ya puse una respuesta explicándolo.

---

Gracias Omar. :)