Prueba del teorema de Caratheodory (para conjuntos convexos) usando el lema de Radon

Question

Prueba del teorema de Caratheodory (para conjuntos convexos) usando el lema de Radon

geometría
Matemáticas
cascos convexos
análisis convexo
geometría discreta
Matemáticas discretas

benjamin bray

Estoy estudiando algo de geometría discreta / análisis convexo. Muchas descripciones del Teorema de Caratheodory para conjuntos convexos mencionan que el Lema de Radon se puede usar para simplificar la prueba, pero no lo he visto hecho. Como referencia, aquí está el Lema de Radon:

Lema (radón). Dejar $A \subset \mathbb{R}^d$ contener $d+2$ puntos. Entonces existen dos subconjuntos disjuntos $A_1, A_2 \subset A$ cuyos cascos convexos tienen intersección no vacía.

Intentaré probar:

Teorema (Caratheodory). Dejar $X \subset \mathbb{R}^d$ . Entonces cada punto de $\mathrm{conv}(X)$ se puede escribir como una combinación convexa de a lo sumo $d+1$ puntos en $X$ .

Intento de prueba. Cada $y \in \mathrm{conv}(X)$ es una combinación convexa $y = \sum_{k=1}^m \alpha_k x_k$ de un número finito de puntos $x_1, \dots, x_m \in X$ , dónde $\alpha_k > 0$ y $\sum_{k=1}^m \alpha_k = 1$ . Asumir $m \geq d+2$ , de lo contrario hemos terminado. Supongamos además hacia la contradicción que $m$ es mínimo, es decir, $y$ no puede escribirse como la combinación convexa de menos de $m$ puntos de $X$ .

Luego, los puntos $x_1, \dots, x_m$ son afinemente dependientes, siendo $m \geq d+2$ puntos en $\mathbb{R}^d$ ; por lo tanto un punto, digamos $x_m$ , es una combinación afín del resto. Aplicar el Lema de Radon al conjunto $A = \{ y, x_1, \dots, x_{m-1} \}$ , dando dos conjuntos $A_1, A_2 \subset A$ cuyos cascos convexos tienen intersección no vacía....?

¿Es esta la idea correcta? ¿Cómo podría continuar?

Respuestas (2)

Prueba del teorema de Caratheodory (para conjuntos convexos) usando el lema de Radon

Decano Gurvitz · Answer 1

Empezaste bien, sobre todo asumiendo $m$ es mínimo Esta no es una prueba simple, y resolverlo todo por su cuenta puede ser muy desafiante. En lugar de tratar de usar la dependencia afín de los puntos directamente, como se hizo en la prueba del teorema de Radon, puede aplicar el teorema mismo en el conjunto $\{x_1,...,x_m\}$ (ya que, como dijiste, $m\geq n+2$ ). Esto nos da disjuntos $I,J\subseteq [m]$ y combinaciones convexas equivalentes:

\sum_{h \in I} X_{h} m_{h} = \sum_{h \in j} X_{h} m_{h}, \sum_{h \in I} m_{h} = \sum_{h \in j} m_{h} = 1

$\sum_{h\in I}x_h\mu_h=\sum_{h\in J}x_h\mu_h,\sum_{h\in I}\mu_h=\sum_{h\in J}\mu_h=1$ Podemos renombrar los puntos, y WLOG asume

I = {1, . . ., k}, J = {k + 1, . . ., l}

$I=\{1,...,k\},J=\{k+1,...,l\}$ , y además:

\frac{α_{1}}{m_{1}} = min_{i \in I} \frac{α_{i}}{m_{i}} := t

$\frac{\alpha_1}{\mu_1}=\min_{i\in I}{\frac{\alpha_i}{\mu_i}}:=t$ (aquí, los coeficientes

α_{i}

$\alpha_i$ son los mismos coeficientes que definiste para el dado

y

$y$ en tu pregunta). Esto nos da:

y = \sum_{i = 1}^{metro} α_{i} X_{i} = \sum_{i = 1}^{metro} α_{i} X_{i} - t \sum_{i = 1}^{k} m_{i} X_{i} + t \sum_{j = k + 1}^{yo} m_{i} X_{i} =

$y=\sum_{i=1}^m\alpha_ix_i=\sum_{i=1}^m\alpha_ix_i-t\sum_{i=1}^k\mu_ix_i+t\sum_{j=k+1}^l\mu_ix_i=$

\sum_{i = 1}^{k} (α_{i} - t m_{i}) X + \sum_{j = k + 1}^{yo} (α_{i} + t m_{i}) X + \sum_{h = yo + 1}^{metro} α_{i} X_{i}

$\sum_{i=1}^k(\alpha_i-t\mu_i)x+\sum_{j=k+1}^l(\alpha_i+t\mu_i)x+\sum_{h=l+1}^m\alpha_ix_i$

t μ_{i} = \frac{α_{1} μ_{i}}{μ_{1}} \leq \frac{α_{i} μ_{i}}{μ_{i}}

$t\mu_i= \frac{\alpha_1\mu_i}{\mu_1}\leq\frac{\alpha_i\mu_i}{\mu_i}$ por lo que todos los coeficientes de esta suma son no negativos. También puedes verificar fácilmente que el primer coeficiente es

0

$0$ , y la suma de los coeficientes es

1

$1$ , y por lo tanto logramos presentar

y

$y$ como una combinación convexa de

m - 1

$m-1$ puntos, en contradicción con la minimalidad de

m

$m$ .

Mickel · Answer 2

Estás en la dirección correcta. Por inducción es suficiente probar que podemos reducir una combinación convexa de $n+2$ apunta a una combinación convexa de $n+1$ puntos. Supongamos que tenemos un punto $v\in\mathbb{R}^n$ y que es una combinación convexa de $n+2$ puntos. Esto significa que

v = \sum_{i = 1}^{norte + 2} α_{i} X_{i} .

$v=\sum_{i=1}^{n+2}\alpha_ix_i.$ Dónde

x_{i} \in X, \sum_{i} α_{i} = 1

$x_i\in X, ~\sum_i\alpha_i=1$ y

α_{i} \geq 0

$\alpha_i\geq 0$ . Desde cualquier

n + 2

$n+2$ puntos en

R^{n}

$\mathbb{R}^n$ son afinemente dependientes, entonces tenemos

\sum_{i = 1}^{norte + 2} β_{i} X_{i} = 0,

$\sum_{i=1}^{n+2}\beta_ix_i=0,$ dónde

\sum_{i} β_{i} = 1

$\sum_i\beta_i=1$ .

Ahora deja $\gamma=\min\{\frac{\alpha_i}{\beta_i}:\beta_i>0\}>0$ , sin pérdida de generalidad, supongamos que $\gamma=\frac{a_{n+2}}{\beta_{n+2}}$ y presta atención a lo siguiente

v = v - γ \cdot 0 = \sum_{i}^{norte + 2} (α_{i} - γ β_{i}) X_{i} = \sum_{i}^{norte + 1} (α_{i} - γ β_{i}) X_{i},

$v=v-\gamma\cdot 0=\sum_i^{n+2}(\alpha_i-\gamma\beta_i)x_i=\sum_i^{n+1}(\alpha_i-\gamma\beta_i)x_i,$

claramente, cada coeficiente es positivo y suman 1, lo que completa la demostración.

Esta es una buena explicación de la prueba habitual, pero ¿dónde se usa el lema de Radon?
Esa es la prueba directa, en realidad no responde la pregunta.
Creo que la propiedad que $\sum_i \beta_i=1$ no es una consecuencia directa de la dependencia afín, y prácticamente utiliza el teorema de Radon. Escribí esta parte con más detalle en mi respuesta.

Prueba del teorema de Caratheodory (para conjuntos convexos) usando el lema de Radon

benjamin bray

Respuestas (2)

Decano Gurvitz

Mickel

benjamin bray

narek bojikian

Decano Gurvitz

¿Existe una teoría para que los autómatas celulares propaguen señales en línea recta?

¿Cómo probar que la línea fuera de un polígono convexo, que tiene la suma mínima de distancias, es una de las aristas?

Rompecabezas: ¿Cortar tetraedro regular en tetraedros regulares de distintos tamaños?

Compruebe si el rayo se cruza con las partes internas de la faceta DDD

Mosaico del cuadrado unitario con triángulos rectángulos

Prueba rigurosa para un rayo que corta la frontera en un conjunto compacto convexo exactamente en un punto.

Volumen de la proyección del cubo unitario sobre un hiperplano

El casco convexo de los vértices de un hipercubo contiene el hipercubo

En una cuadrícula n × nn × nn \ veces n, con mosaicos blancos y negros: ¿siempre hay una ruta conectada a través de la cuadrícula?

Transformar de un sistema de coordenadas global a uno local