La lógica de los conjuntos convexos

Question

Permítanme comenzar con el teorema de Helly: Sea $A_1$ , $A_2$ , ..., $A_{n+2}$ sea $n+2$ subconjuntos convexos de $\mathbb R^n$ . Si cualquier $n+1$ de estos subconjuntos se cruzan (esto significa: tienen una intersección no vacía), lo mismo ocurre con todos $n+2$ .

Esta afirmación es, lógicamente, una cláusula definida: Todas las condiciones son de la forma "algunos subconjuntos se intersecan", y así es la afirmación. En general, una cláusula definida sobre la intersección de conjuntos convexos tiene el siguiente aspecto: Dados unos conjuntos $S_1$ , $S_2$ , ..., $S_k$ y $T$ y una familia $\left(F_a\right)_{a\in S_1\cup S_2\cup ...\cup S_k\cup T}$ de subconjuntos convexos de $\mathbb R^n$ indexado por los elementos de $S_1\cup S_2\cup ...\cup S_k\cup T$ afirmamos que si cada $i\in\left\lbrace 1,2,...,k\right\rbrace$ satisface $\bigcap\limits_{a\in S_i}F_a\neq\emptyset$ entonces $\bigcap\limits_{a\in T}F_a\neq\emptyset$ .

Ahora es un ejercicio fácil ver que toda cláusula definida tautológica (= verdadera para toda elección de subconjuntos convexos) sobre la intersección de conjuntos convexos es derivable usando propiedades triviales de la intersección (como $A\cap A=A$ , $A\cap B=B\cap A$ y $A\cap \left(B\cap C\right)=\left(A\cap B\right)\cap C$ ) y el teorema de Helly solamente. (Obsérvese que consideramos $n$ como dado a priori y fijado durante nuestra prueba, por lo que no podemos proyectar en un subespacio y utilizar Helly para un $n$ por ejemplo. Realmente sólo podemos manipular las intersecciones y utilizar Helly para varias intersecciones de subconjuntos convexos. Podría escribir lo que podemos hacer como un sistema de deducción natural, pero es bastante obvio).

Ahora bien, ¿qué pasa si permitimos las cláusulas indefinidas? Se trata de enunciados de la forma Dados unos conjuntos $S_1$ , $S_2$ , ..., $S_k$ y $T_1$ , $T_2$ , ..., $T_l$ y una familia $\left(F_a\right)_{a\in S_1\cup S_2\cup ...\cup S_k\cup T_1\cup T_2\cup ...\cup T_l}$ de subconjuntos convexos de $\mathbb R^n$ indexado por los elementos de $S_1\cup S_2\cup ...\cup S_k\cup T_1\cup T_2\cup ...\cup T_l$ afirmamos que si cada $i\in\left\lbrace 1,2,...,k\right\rbrace$ satisface $\bigcap\limits_{a\in S_i}F_a\neq\emptyset$ entonces al menos ALGUNO $j\in\left\lbrace 1,2,...,l\right\rbrace$ satisface $\bigcap\limits_{a\in T_j}F_a\neq\emptyset$ .

¿Qué conjunto de "axiomas" (como el teorema de Helly) necesitamos para demostrar tales cláusulas indefinidas, si son tautológicas? Por "demostrar" me refiero a demostrar sin utilizar la convexidad de los conjuntos o que los conjuntos son conjuntos en absoluto (un enfoque sin puntos, por así decirlo) - sólo utilizando las propiedades formales de $\cap$ La lógica (digamos constructiva) y estos axiomas. Obviamente, Helly por sí solo ya no es suficiente; por ejemplo, para $n=1$ tenemos esto aquí: Si $A$ , $B$ , $C$ , $D$ son cuatro subconjuntos convexos de $\mathbb R^n$ tal que $A\cap B$ , $B\cap C$ , $C\cap D$ y $D\cap A$ son no vacíos, entonces al menos uno de los conjuntos $A\cap C$ y $B\cap D$ son no vacíos.

Una conexión con la lógica temporal es posible, pero para ser sincero no tengo ni idea de lógica temporal; si alguien pudiera indicarme una referencia que sea de ayuda aquí esto podría cambiar...

Answer 1

Esta es una pregunta interesante. (Aunque no exista una lista finita de "axiomas").

Por ejemplo, lo siguiente es cierto: Supongamos que se tiene un politopo de (d+1) dimensiones P. Asocie un conjunto convexo en $R^d$ a cada faceta de P, y supongamos que toda intersección no vacía entre las facetas implica una intersección no vacía para los conjuntos correspondientes. Entonces hay algún conjunto de facetas del politopo con intersección vacía para que los conjuntos convexos correspondientes tengan intersección no vacía. Esta es una gran colección de afirmaciones del tipo que has preguntado que ya incluye el teorema de Helly.

Tenga en cuenta que el teorema del nervio le da mucha información sobre los patrones de intersección que no se pueden realizar. (Incluyendo la afirmación hecha anteriormente).

Una afirmación más fuerte para el caso descrito anteriormente es la siguiente: Supongamos que 0 está en el interior de P. Entonces se pueden encontrar dos caras de F y G de P de forma que 0 esté en su casco convexo y la intersección de todos los conjuntos correspondientes a las facetas que contienen a F y todos los conjuntos correspondientes a las facetas que contienen a G sea no vacía. Esto se puede derivar del teorema de Borsuk-Ulam.

Otro resultado bien conocido del tipo que preguntas es el colorido teorema de Helly (demostrado por Lovasz y una versión dual de Caratheodory fue demostrada independientemente por Barany). Dice que si tienes d+1 colecciones de conjuntos convexos en R^d, y si para cada elección de un conjunto de cada colección hay un punto común a todos los conjuntos elegidos, entonces hay una colección cuyos miembros tienen un punto en común.

Para n=1 existe un teorema de Lekkerker y Boland que caracteriza a los grafos de intervalo. La caracterización se basa en dos requisitos: (1) no hay ciclos inducidos de longitud >3. (Esto nos deja con grafos acordes.) (2) para cada 3 vértices, uno de los vértices es vecino de un vértice en cada camino entre los otros dos. Esto da un conjunto infinito de "axiomas" en el sentido planteado en la pregunta. Supongo que no existe una lista finita.

Así que, en general, hay muchos teoremas interesantes del tipo que has descrito, y este es un área muy rica. Pero una descripción completa para dimensión > 1 no parece realista.

Una cuestión más general es estudiar la situación en la que se permiten ambas operaciones: (1) tomar la intersección (2) tomar el casco convexo. Esto hace que el problema sea aún mucho más complicado y no se sabe mucho. Un ejemplo de un resultado reciente en esta situación más general es el siguiente teorema de Novick: Dados 7,2k conjuntos convexos disjuntos en el plano, hay un conjunto de la familia que es disjunto al casco convexo de otros k conjuntos de la familia.

Answer 2

Tengo una especie de razón heurística por la que el caso $n=2$ es difícil, es decir, para $n=2$ no existe un conjunto finito de reglas de deducción a partir del cual podamos derivar cada cláusula de Horn sobre los conjuntos convexos (sin utilizar ninguna otra propiedad de los conjuntos convexos). Esto no es una prueba, pero es lo suficientemente convincente para que deje de considerar la $n\geq 2$ caso. En cuanto a $n=1$ No tengo ni idea.

Este es el argumento. Para cualquier gráfico $G$ con un conjunto de vértices (finito) $V$ y conjunto de bordes $E$ podemos fijar un orden total en el conjunto $V$ y considera la siguiente cláusula de Horn:

La cláusula de planaridad del gráfico $G$ : LET $P_{u,v}$ sea un conjunto convexo para dos vértices cualesquiera $u$ y $v$ de $G$ satisfaciendo $u < v$ . SI $P_{u,v}\cap P_{t,r}\neq\emptyset$ siempre que los conjuntos $\left\lbrace u,v\right\rbrace$ y $\left\lbrace t,r\right\rbrace$ tienen un elemento común, ENTONCES tenemos $P_{u,v}\cap P_{t,r}\neq\emptyset$ para al menos un cuádruple $\left(u,v,t,r\right)$ de vértices de $G$ tal que los conjuntos $\left\lbrace u,v\right\rbrace$ y $\left\lbrace t,r\right\rbrace$ no tienen ningún elemento común.

Podemos encontrar fácilmente que la cláusula de planaridad del gráfico $G$ siempre se satisface si y sólo si el gráfico $G$ no es planar. (Lo que realmente estamos utilizando aquí es Teorema de Fáry .) Ahora bien, el teorema de Kuratowski nos muestra que tenemos grafos no planos de tamaño arbitrariamente grande que sólo pueden demostrarse planos mirando TODOS sus vértices juntos. Por ejemplo, tomemos $K_5$ y lo "ampliamos" sustituyendo cada arista por una secuencia $\cdot - \cdot - \cdot - \cdot - ... - \cdot$ de pequeños bordes. Si eliminamos cualquiera de las aristas, obtenemos un grafo plano, por lo que si existiera una familia finita de reglas de la que se derivaran todas las tautologías, al menos una de estas reglas hablaría de un gran número de conjuntos convexos (es decir, al menos tantos como aristas tengas en tu grafo $K_5$ ). Contradicción.

Como he dicho, no sé si esto es realmente un argumento sólido, e incluso si lo es, el caso $n=1$ sigue abierta.