teorema del radón

Dice que d+2 puntos en d dimensiones se pueden dividir en dos subconjuntos cuyos cascos convexos se cruzan

En geometría , el teorema de radón 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 cuyos cascos convexos se cruzan.

Un punto en la intersección de estos cascos convexos se llama punto de radón 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 resolviendo el sistema de tres ecuaciones lineales para estos puntos y las particiones de radón formadas al separar los puntos con multiplicadores positivos del puntos con multiplicadores negativos.

Por ejemplo, en el caso d  = 2, cualquier conjunto de cuatro puntos en el plano euclidiano se puede dividir de dos maneras. Puede formar un triple y un singleton, donde el casco convexo del triple (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 cruzan .

Prueba y construcción

Considere cualquier conjunto de d  + 2 puntos en un espacio d -dimensional. Entonces existe un conjunto de multiplicadores a ₁ , ...,  a _{d  + 2} , no todos los cuales son cero, resolviendo 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 sólo 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). Fije 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 negativos o cero. Luego , forme la partición requerida de los puntos en dos subconjuntos con cascos convexos que se cruzan. ${\displaystyle I\subseteq X}$ ${\displaystyle J=X\setminus I}$ ${\displaystyle I}$ ${\displaystyle J}$

Los cascos convexos de y deben intersectarse, porque ambos 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 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 tanto, pertenece a ambos cascos convexos, completando la prueba. ${\displaystyle p}$ ${\displaystyle I}$ ${\displaystyle J}$ ${\displaystyle p}$

Este método de prueba permite la construcción eficiente de un punto de radón, en una cantidad de tiempo de dimensión polinómica , mediante el uso de 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 del radón es:

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

Son equivalentes porque cualquier función afín en un simplex está determinada únicamente 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 sus imágenes bajo ƒ . Según la formulación original, se puede dividir en dos subconjuntos disjuntos, por ejemplo ( xi ₎ i _{en I} y ( xj ) _{j en J,} con casco convexo superpuesto _. Debido a que f es afín, la cáscara convexa de ( xi ₎ i _{en I} es la imagen de la cara atravesada por los vértices ( vi ₎ i _{en I} , y de manera similar la cáscara 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 están separadas y sus imágenes bajo f se cruzan, como afirma la nueva formulación. El teorema topológico del radón generaliza esta formulación. 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 simplex ( d  + 1) dimensional Δ ^d+1 a R ^d , entonces hay dos caras disjuntas de Δ ^d+1 cuyas imágenes bajo ƒ se cruzan.

De manera más general, si K es cualquier  conjunto convexo compacto ( d + 1) dimensional, y ƒ es cualquier función continua desde K hasta el espacio d -dimensional, 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 de que K sea un simplex, las dos caras simplex formadas por los puntos máximo y mínimo de g deben ser entonces dos caras disjuntas cuyas imágenes tengan una intersección no vacía. Esta misma afirmación general, cuando se aplica a una hiperesfera en lugar de a una simplex, da el teorema de Borsuk-Ulam , que ƒ debe asignar dos puntos opuestos de la esfera al mismo punto. ^[2]

Pruebas

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

• Construya un mapa continuo g desde S ^{d (la} esfera d-dimensional ) 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} .
• Aplique 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 asigna al mismo punto de R ^d . Esto implica que las imágenes de estas dos caras disjuntas se cruzan.

Lovasz y Schrijver dieron otra prueba. ^[3] Matousek da una tercera prueba: ^{[4] : ​​115}

• Sea K el simplex Δ ^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 del radón se deriva del siguiente teorema más general. Para cualquier complejo simplicial K , si el índice Z ₂ de es mayor que d , entonces para cada mapeo continuo de || K || a R ^d , las imágenes de dos caras disjuntas de K se cruzan. ${\displaystyle K_{\Delta }^{*2}}$

Aplicaciones

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

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

El teorema del radón también se puede utilizar para calcular la dimensión VC de puntos d -dimensionales con respecto a separaciones lineales. Existen conjuntos de d  + 1 puntos (por ejemplo, los puntos de un simplex regular) tales que cada dos subconjuntos no vacíos pueden separarse entre sí mediante un hiperplano. Sin embargo, no importa qué conjunto de puntos d  + 2 se dé, los dos subconjuntos de una partición de radón 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 de radón para calcular una aproximación a un punto central de cualquier conjunto de puntos, en una cantidad de tiempo que es polinómica tanto en el número de puntos como en la dimensión. ^[1]

Conceptos relacionados

Mediana geométrica . El punto de radón de tres puntos en un espacio unidimensional es solo su mediana . La mediana geométrica de un conjunto de puntos es el punto que minimiza la suma de 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 estadísticas sólidas . Para conjuntos de cuatro puntos en el plano, la mediana geométrica coincide con el punto de radón.

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

El teorema de Carathéodory establece que cualquier punto en la capa convexa de algún conjunto de puntos también está dentro de la capa 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 para examinar soluciones de sistemas de ecuaciones lineales, similar a la prueba del teorema de Radon, para eliminar un punto a la vez hasta que quede como máximo d  + 1.

Geometrías convexas . También se han considerado conceptos relacionados con el teorema de radón para las geometrías convexas , familias de conjuntos finitos con las propiedades de que la intersección de dos conjuntos cualesquiera de la familia permanece en la familia, y que el conjunto vacío y la unión de todos los conjuntos pertenecen al familia. En este contexto más general, la cáscara convexa de un conjunto S es la intersección de los miembros de la familia que contienen S , y el número de radón de un espacio es el r más pequeño tal que cualesquiera r puntos tengan dos subconjuntos cuyas cáscaras convexas se intersequen. 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 del radón para gráficas . En un gráfico arbitrario no dirigido , 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 gráfico se puede dividir en dos subconjuntos cuyos cascos convexos se cruzan, y ω + 1 es el número mínimo para el cual esto es posible, donde ω es el número de camarilla del gráfico dado. ^[10] Para resultados relacionados que involucran caminos más cortos en lugar de caminos inducidos, ver Chepoi (1986) y Bandelt & Pesch (1989).

Notas

1. Clarkson y col. (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, Alejandro (1998). "Un teorema de Borsuk para enlaces antípodas y una caracterización espectral de gráficos integrables sin enlaces". Actas de la Sociedad Matemática Estadounidense . 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 : conferencias sobre métodos topológicos en combinatoria y geometría (2ª ed.). Berlín-Heidelberg: Springer-Verlag. ISBN 978-3-540-00362-5. Escrito 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), "Problemas de ubicación de Fermat de cuatro puntos revisados. 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. Epsilon-nets y VC-dimension, Apuntes de conferencias de Marco Pellegrini, 2004.
9. Kay y Womble (1971).
10. Duchat (1987).

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 gráficos triangulados", Mat. Emitido. (en ruso), 87 : 164-177. Según lo citado por Bandelt y Pesch (1989).
• Clarkson, Kenneth L .; Eppstein, David ; Miller, Gary L .; Sturtivante, Carl; Teng, Shang-Hua (1996), "Aproximación de puntos centrales con puntos de radón iterados", Revista internacional de aplicaciones y geometría computacional , 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", Convexidad , Proc. Síntoma. Matemáticas puras, vol. 7, Sociedad Estadounidense de Matemáticas , págs. 101-179.
• Duchet, Pierre (1987), "Conjuntos convexos en gráficos. 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 , Señor  0310766.
• Matoušek, J. (2002), "1.3 Lema del radón y teorema de Helly", Conferencias sobre geometría discreta , 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 integrabilidad: una introducción", uso del teorema de Borsuk-Ulam: conferencias sobre métodos topológicos en combinatoria y geometría , Springer-Verlag, págs..
• 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 del radón" (PDF) , Journal of the London Mathematical Society , 41 : 123–128, doi :10.1112/jlms/s1-41.1.123^{[ enlace muerto ]} .