Teorema de Radon

Dice que d+2 puntos en d dimensiones se pueden dividir en dos subconjuntos cuyas envolturas convexas se intersecan

En geometría , el teorema de Radon sobre conjuntos convexos , publicado por Johann Radon en 1921, establece que:

Cualquier conjunto de d + 2 puntos en R ^d se puede dividir en dos conjuntos cuyas envolturas convexas se intersecan.

Un punto en la intersección de estas envolturas convexas se llama punto Radon del conjunto.

Dos conjuntos de cuatro puntos en el plano (los vértices de un cuadrado y un triángulo equilátero con su centroide), los multiplicadores que resuelven el sistema de tres ecuaciones lineales para estos puntos, y las particiones de Radon formadas al separar los puntos con multiplicadores positivos de los puntos con multiplicadores negativos.

Por ejemplo, en el caso de d  = 2, cualquier conjunto de cuatro puntos en el plano euclidiano se puede dividir de una de dos maneras: puede formar una terna y un singleton, donde la envoltura convexa de la terna (un triángulo) contiene el singleton; alternativamente, puede formar dos pares de puntos que forman los puntos finales de dos segmentos de línea que se intersecan .

Prueba y construcción

Consideremos cualquier conjunto de d  + 2 puntos en un espacio de dimensión d . Entonces existe un conjunto de multiplicadores a ₁ , ...,  a _{d  + 2} , no todos ellos cero, que resuelven el sistema de ecuaciones lineales ${\displaystyle X=\{x_{1},x_{2},\dots ,x_{d+2}\}\subset \mathbf {R} ^{d}}$

${\displaystyle \sum _{i=1}^{d+2}a_{i}x_{i}=0,\quad \sum _{i=1}^{d+2}a_{i}=0,}$

porque hay d  + 2 incógnitas (los multiplicadores) pero solo d  + 1 ecuaciones que deben satisfacer (una para cada coordenada de los puntos, junto con una ecuación final que requiere que la suma de los multiplicadores sea cero). Fijemos alguna solución particular distinta de cero a ₁ , ...,  a _{d  + 2} . Sea el conjunto de puntos con multiplicadores positivos, y sea el conjunto de puntos con multiplicadores que son negativos o cero. Luego y forme la partición requerida de los puntos en dos subconjuntos con envolturas convexas que se intersecan. ${\displaystyle I\subseteq X}$ ${\displaystyle J=X\setminus I}$ ${\displaystyle I}$ ${\displaystyle J}$

Las envolturas convexas de y deben intersecarse, porque ambas contienen el punto ${\displaystyle I}$ ${\displaystyle J}$

${\displaystyle p=\sum _{x_{i}\in I}{\frac {a_{i}}{A}}x_{i}=\sum _{x_{j}\in J}{\frac {-a_{j}}{A}}x_{j},}$

dónde

${\displaystyle A=\sum _{x_{i}\in I}a_{i}=-\sum _{x_{j}\in J}a_{j}.}$

El lado izquierdo de la fórmula para expresa este punto como una combinación convexa de los puntos en , y el lado derecho lo expresa como una combinación convexa de los puntos en . Por lo tanto, pertenece a ambas envolturas convexas, lo que completa la prueba. ${\displaystyle p}$ ${\displaystyle I}$ ${\displaystyle J}$ ${\displaystyle p}$

Este método de prueba permite la construcción eficiente de un punto Radon, en una cantidad de tiempo que es polinomial en la dimensión, utilizando la eliminación gaussiana u otros algoritmos eficientes para resolver el sistema de ecuaciones para los multiplicadores. ^[1]

Teorema topológico del radón

Una formulación equivalente del teorema de Radon es:

Si ƒ es cualquier función afín de un símplex de dimensión ( d  + 1) Δ ^d+1 a R ^d , entonces hay dos caras disjuntas de Δ ^d+1 cuyas imágenes bajo ƒ se intersecan.

Son equivalentes porque cualquier función afín en un símplex está determinada de forma única por las imágenes de sus vértices. Formalmente, sea ƒ una función afín de Δ ^d+1 a R ^d . Sean los vértices de Δ ^d+1 , y sean sus imágenes bajo ƒ . Por la formulación original, se puede dividir en dos subconjuntos disjuntos, p. ej. ( x _i ) _{i en I} y ( x _j ) _{j en J,} con envoltura convexa superpuesta. Como f es afín, la envoltura convexa de ( x _i ) _{i en I} es la imagen de la cara abarcada por los vértices ( v _i ) _{i en I} , y de manera similar la envoltura convexa de ( x _j )j _{en J} es la imagen de la cara abarcada por los vértices ( v _j )j _{en j} . Estas dos caras son disjuntas y sus imágenes bajo f se intersecan, como afirma la nueva formulación. El teorema topológico de Radon generaliza esta formulación y permite que f sea cualquier función continua, no necesariamente afín: ^[2] ${\displaystyle v_{1},v_{2},\dots ,v_{d+2}}$ ${\displaystyle x_{1},x_{2},\dots ,x_{d+2}}$ ${\displaystyle x_{1},x_{2},\dots ,x_{d+2}}$

Si ƒ es cualquier función continua desde un símplex de dimensión ( d  + 1) Δ ^d+1 hasta R ^d , entonces hay dos caras disjuntas de Δ ^d+1 cuyas imágenes bajo ƒ se intersecan.

En términos más generales, si K es cualquier conjunto convexo compacto de dimensión ( d  + 1) y ƒ es cualquier función continua desde el espacio de dimensión K hasta el de dimensión d , entonces existe una función lineal g tal que algún punto donde g alcanza su valor máximo y algún otro punto donde g alcanza su valor mínimo son mapeados por ƒ al mismo punto. En el caso donde K es un símplex, las dos caras del símplex formadas por los puntos máximo y mínimo de g deben ser entonces dos caras disjuntas cuyas imágenes tienen una intersección no vacía. Esta misma afirmación general, cuando se aplica a una hiperesfera en lugar de a un símplex, da el teorema de Borsuk–Ulam , según el cual ƒ debe mapear dos puntos opuestos de la esfera al mismo punto. ^[2]

Pruebas

El teorema topológico de Radon fue demostrado originalmente por Bajmoczy y Barany ^[2] de la siguiente manera:

• Construya una función continua g desde S ^{d (la} esfera de dimensión d ) hasta Δ ^d+1 , tal que para cada punto x en la esfera, g ( x ) y g (- x ) estén en dos caras disjuntas de Δ ^d+1 .
• Apliquemos el teorema de Borsuk-Ulam a la función , que es una función continua desde S ^d hasta R ^d . El teorema dice que, para cualquier función de este tipo, existe algún punto y en S ^d , tal que f(g(y)) = f(g(-y)). ${\displaystyle f\circ g}$
• Los puntos g(y) y g(-y) están en dos caras disjuntas de Δ ^{d+1 , y} f los mapea al mismo punto de R ^d . Esto implica que las imágenes de estas dos caras disjuntas se intersecan.

Otra prueba fue dada por Lovasz y Schrijver. ^[3] Una tercera prueba fue dada por Matousek: ^{[4] : 115}

• Sea K el símplex Δ ^d+1 , y sea la unión eliminada de K consigo mismo. ${\displaystyle K_{\Delta }^{*2}}$
• La realización geométrica de es homeomorfa a la esfera S ^d+1 . ${\displaystyle K_{\Delta }^{*2}}$
• Por lo tanto, el índice Z2 de es igual a d +1. ${\displaystyle K_{\Delta }^{*2}}$
• El teorema topológico de Radon se desprende del siguiente teorema más general. Para cualquier complejo simplicial K , si el índice Z ₂ de es mayor que d , entonces para cada aplicación continua de || K || a R ^d , las imágenes de dos caras disjuntas de K se intersecan. ${\displaystyle K_{\Delta }^{*2}}$

Aplicaciones

El punto Radon de cuatro puntos cualesquiera en el plano es su mediana geométrica , el punto que minimiza la suma de las distancias a los otros puntos. ^{[5] [6]}

El teorema de Radon constituye un paso clave de una prueba estándar del teorema de Helly sobre intersecciones de conjuntos convexos; ^[7] esta prueba fue la motivación para el descubrimiento original del teorema de Radon.

El teorema de Radon también se puede utilizar para calcular la dimensión VC de puntos de dimensión d con respecto a separaciones lineales. Existen conjuntos de puntos d  + 1 (por ejemplo, los puntos de un símplex regular) tales que cada dos subconjuntos no vacíos se pueden separar entre sí por un hiperplano. Sin embargo, sin importar qué conjunto de puntos d  + 2 se dé, los dos subconjuntos de una partición de Radon no se pueden separar linealmente. Por lo tanto, la dimensión VC de este sistema es exactamente d  + 1. ^[8]

 Se puede utilizar un algoritmo aleatorio que reemplaza repetidamente conjuntos de d + 2 puntos por su punto Radon para calcular una aproximación a un punto central de cualquier conjunto de puntos, en una cantidad de tiempo que sea polinomial tanto en el número de puntos como en la dimensión. ^[1]

Conceptos relacionados

Mediana geométrica . El punto Radon de tres puntos en un espacio unidimensional es simplemente su mediana . La mediana geométrica de un conjunto de puntos es el punto que minimiza la suma de las distancias a los puntos del conjunto; generaliza la mediana unidimensional y se ha estudiado tanto desde el punto de vista de la ubicación de las instalaciones como de las estadísticas robustas . Para conjuntos de cuatro puntos en el plano, la mediana geométrica coincide con el punto Radon.

Teorema de Tverberg . Helge Tverberg (1966) dio una generalización para la partición en r conjuntos,  que ahora se conoce como teorema de Tverberg . Establece que para cualquier conjunto de puntos en el d -espacio euclidiano, existe una partición en r subconjuntos cuyas envolturas convexas se intersecan en al menos un punto común. ${\displaystyle (d+1)(r-1)+1\ }$

El teorema de Carathéodory establece que cualquier punto en la envoltura convexa de un conjunto de puntos también está dentro de la envoltura convexa de un subconjunto de, como máximo, d  + 1 de los puntos; es decir, que el punto dado es parte de una partición de Radon en la que es un singleton. Una prueba del teorema de Carathéodory utiliza una técnica de examen de soluciones a sistemas de ecuaciones lineales, similar a la prueba del teorema de Radon, para eliminar un punto a la vez hasta que, como máximo, queden d  + 1.

Geometrías convexas . Los conceptos relacionados con el teorema de Radon también se han considerado para las geometrías convexas , familias de conjuntos finitos con las propiedades de que la intersección de dos conjuntos cualesquiera en la familia permanece en la familia, y que el conjunto vacío y la unión de todos los conjuntos pertenecen a la familia. En este contexto más general, la envoltura convexa de un conjunto S es la intersección de los miembros de la familia que contienen a S , y el número de Radon de un espacio es el r más pequeño tal que cualesquiera r puntos tienen dos subconjuntos cuyas envolturas convexas se intersecan. De manera similar, se puede definir el número de Helly h y el número de Carathéodory c por analogía con sus definiciones para conjuntos convexos en espacios euclidianos, y se puede demostrar que estos números satisfacen las desigualdades h  <  r  ≤  ch  + 1. ^[9]

Teorema de Radon para grafos . En un grafo no dirigido arbitrario , se puede definir un conjunto convexo como un conjunto de vértices que incluye cada camino inducido que conecta un par de vértices en el conjunto. Con esta definición, cada conjunto de ω + 1 vértices en el grafo se puede dividir en dos subconjuntos cuyas envolturas convexas se intersecan, y ω + 1 es el número mínimo para el cual esto es posible, donde ω es el número de camarilla del grafo dado. ^[10] Para resultados relacionados que involucran caminos más cortos en lugar de caminos inducidos, consulte Chepoi (1986) y Bandelt & Pesch (1989).

Notas

1. Clarkson y otros (1996).
2. Bajmóczy, por ejemplo; Bárány, I. (1 de septiembre de 1979). "Sobre una generalización común del teorema de Borsuk y del radón". Acta Mathematica Academiae Scientiarum Hungaricae . 34 (3): 347–350. doi :10.1007/BF01896131. ISSN  1588-2632. S2CID  12971298.
3. Lovász, László; Schrijver, Alexander (1998). "Un teorema de Borsuk para enlaces antípodas y una caracterización espectral de grafos incrustables sin enlaces". Actas de la American Mathematical Society . 126 (5): 1275–1285. doi : 10.1090/S0002-9939-98-04244-0 . ISSN  0002-9939. S2CID  7790459.
4. Matoušek, Jiří (2007). Uso del teorema de Borsuk-Ulam : lecciones sobre métodos topológicos en combinatoria y geometría (2.ª ed.). Berlín-Heidelberg: Springer-Verlag. ISBN 978-3-540-00362-5Escrito en colaboración con Anders Björner y Günter M. Ziegler, Sección 4.3
5. Cieslik, Dietmar (2006), Conectividad más corta: una introducción con aplicaciones en filogenia, Optimización combinatoria, vol. 17, Springer, pág. 6, ISBN 9780387235394.
6. Plastria, Frank (2006), "Revisión de los problemas de ubicación de Fermat de cuatro puntos. Nuevas pruebas y extensiones de resultados antiguos" (PDF) , IMA Journal of Management Mathematics , 17 (4): 387–396, doi :10.1093/imaman/dpl007, Zbl  1126.90046.
7. Matoušek (2002), pág. 11.
8. Redes épsilon y dimensión VC, notas de clase de Marco Pellegrini, 2004.
9. Kay y Womble (1971).
10. Delhi (1986).

Referencias

• Bajmóczy, EG; Bárány, I. (1979), "Una generalización común del teorema de Borsuk y Radón", Acta Mathematica Hungarica , 34 (3–4): 347–350, doi :10.1007/BF01896131, S2CID  12971298.
• Bandelt, H.-J.; Pesch, E. (1989), "Un teorema del radón para gráficos de Helly", Archiv der Mathematik , 52 (1): 95–98, doi :10.1007/BF01197978, S2CID  120983560.
• Chepoi, VD (1986), "Algunas propiedades de la d-convexidad en grafos triangulados", Mat. Issled. (en ruso), 87 : 164–177. Según lo citado por Bandelt y Pesch (1989).
• Clarkson, Kenneth L .; Eppstein, David ; Miller, Gary L .; Sturtivant, Carl; Teng, Shang-Hua (1996), "Aproximación de puntos centrales con puntos de Radon iterados", International Journal of Computational Geometry & Applications , 6 (3): 357–377, doi :10.1142/s021819599600023x, MR  1409651.
• Danzer, L.; Grünbaum, B .; Klee, V. (1963), "El teorema de Helly y sus parientes", Convexity , Proc. Symp. Pure Math., vol. 7, American Mathematical Society , págs. 101–179.
• Duchet, Pierre (1987), "Conjuntos convexos en grafos. II. Convexidad de trayectoria mínima", Journal of Combinatorial Theory, Serie A , 44 (3): 307–316, doi : 10.1016/0095-8956(88)90039-1. Según lo citado por Bandelt y Pesch (1989).
• Eckhoff, J. (1993), "Teoremas de tipo Helly, Radon y Carathéodory", Handbook of Convex Geometry , vol. A, B, Ámsterdam: Holanda Septentrional, págs. 389–448.
• Kay, David C.; Womble, Eugene W. (1971), "Teoría de la convexidad axiomática y relaciones entre los números de Carathéodory, Helly y Radon", Pacific Journal of Mathematics , 38 (2): 471–485, doi : 10.2140/pjm.1971.38.471 , MR  0310766.
• Matoušek, J. (2002), "1.3 El lema de Radon y el teorema de Helly", Lectures on Discrete Geometry , Textos de posgrado en matemáticas , vol. 212, Springer-Verlag, págs. 9-12, ISBN 978-0-387-95373-1.
• Matoušek, J. (2003), "5.1 Teoremas de no incrustabilidad: una introducción", Uso del teorema de Borsuk-Ulam: lecciones sobre métodos topológicos en combinatoria y geometría , Springer-Verlag, págs. 88-92.
• Radon, J. (1921), "Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten", Mathematische Annalen , 83 (1–2): 113–115, doi :10.1007/BF01464231, S2CID  121627696.
• Tverberg, H. (1966), "Una generalización del teorema de Radon", Journal of the London Mathematical Society , 41 : 123–128, doi :10.1112/jlms/s1-41.1.123.