¿Un árbol de conjuntos convexos?

Question

Esto fue sugerido por un problema en el #math de FreeNode hace un tiempo...

Construir un grafo dirigido $\Gamma$ con el conjunto de vértices el conjunto de conjuntos convexos compactos en $\mathbb R^2$ y una flecha $A\to B$ si $A$ y $B$ son disjuntos y hay un punto $a$ en $A$ y un $t>0$ tal que $a+(t,0)$ está en $B$ .

Supongo que no hay ciclos orientados en $\Gamma$ por lo que es un grafo acíclico dirigido. ¿Puedes dar una prueba que no sea fea?

Más tarde: El ejemplo de Rahul, más abajo, demuestra que esto es demasiado esperar. De hecho, lo que realmente es saber si el subgrafo abarcado por cada conjunto finito de conjuntos convexos disjuntos tiene no ciclos.

Answer 1

¿Estoy entendiendo mal las condiciones del problema o se trata de un contraejemplo?

Más tarde: Creo que la respuesta a tu pregunta actualizada es sí -- o mejor dicho, no, cualquier subgrafo inducido por conjuntos convexos disjuntos no tiene ciclos. (Sin embargo, eso lo convertiría en un gráfico acíclico dirigido o DAG, y no un árbol, a no ser que se trate de terminología informática). Tengo un esbozo de lo que creo que debería ser una prueba válida, pero completar los detalles es un poco feo. Desgraciadamente, creo que no hay una prueba completamente no fea, por dos razones:

1. El poder de la convexidad se pierde un poco porque los hiperplanos de separación no son de ayuda aquí. Si $A \rightarrow B \rightarrow C$ no existe necesariamente un hiperplano que separe $C$ de $A \cup B$ .

2. La proposición no es válida en más de 2 dimensiones, por lo que cualquier prueba debe depender fundamentalmente de la naturaleza 2D del problema.

Dicho esto, aquí está la prueba bastante fea que conseguí. Supongamos, en aras de la contradicción, que existe un ciclo de conjuntos convexos compactos disjuntos, $A_1 \rightarrow A_2 \rightarrow \cdots \rightarrow A_n \rightarrow A_1$ . Cada conjunto $A_i$ contiene un par de puntos $p_i$ y $q_i$ tal que $q_{i-1} \rightarrow p_i$ y $q_i \rightarrow p_{i+1}$ (donde $i+1$ y $i-1$ son modulo $n$ por supuesto). Por lo tanto, basta con demostrar la imposibilidad de un ciclo en los segmentos de la línea $p_1 q_1 \rightarrow p_2 q_2 \rightarrow \cdots \rightarrow p_n q_n \rightarrow p_1 q_1$ .

Considere la "franja" más a la derecha de la primera $i$ segmentos, en función de $y$ es decir, que $f_{i}(y) = \sup \\{x : (x,y) \in p_1 q_1 \cup p_2 q_2 \cup \cdots \cup p_i q_i\\}$ . Mientras que $f_i$ no es continua, creo que se puede demostrar por inducción que si $p_1 q_1 \rightarrow p_2 q_2 \rightarrow \cdots \rightarrow p_i q_i \rightarrow p_{i+1} q_{i+1}$ entonces las discontinuidades de $f_i$ no son "visibles" para $p_{i+1}$ . Lo que quiero decir es que $f_i$ salta hacia la izquierda en lugar de hacia la derecha a medida que avanza $y$ lejos de $p_{i+1}$ , por lo que no hay manera de que $q_{i+1}$ para colarse a la izquierda de $f_i$ sin el segmento $p_{i+1}q_{i+1}$ intersección de $f_i$ en alguna parte. Por lo tanto, cada $p_{i+1}$ y $q_{i+1}$ está a la derecha de $f_i$ . En particular, $q_n$ está a la derecha de $f_{n-1}$ . Pero $p_1$ está en o a la izquierda de $f_{n-1}$ Así que $q_n \rightarrow p_1$ es imposible.

Answer 2

He aquí una prueba sencilla de que el grafo dirigido inducido por conjuntos convexos disjuntos es acíclico.

Supongamos que hay un contraejemplo, entonces debe haber uno con el menor número de conjuntos convexos involucrados. Supongamos que dicho contraejemplo viene dado por los conjuntos convexos $C_1,C_2,\dots,C_n$ . Entonces el ciclo dirigido debe contener todos los $C_i$ por la suposición de minimidad (si no, basta con desechar los que no están en el ciclo para obtener un contraejemplo más pequeño). WLOG, asume que el gráfico contiene $C_1\to C_2\to \cdots \to C_n\to C_1$ .

Lemma: No hay otras aristas en este gráfico.

Prueba de ello: Si tuviéramos $A_k\to A_r$ con $k\neq r-1 \pmod{n}$ entonces $A_k\to A_r\to A_{r+1}\to \cdots \to A_k$ sería un ciclo más corto, lo que contradice nuestra hipótesis de minimalidad.

Hasta ahora no hemos utilizado que se trata de conjuntos convexos. Ahora el truco está en que si no hay $A_k$ que interseca el casco convexo de $A_r \cup A_{r+1}$ entonces sustituyendo $A_r$ y $A_{r+1}$ con su casco convexo da una colección más pequeña de conjuntos convexos con un ciclo.

Ahora aplicando el lema se deduce que para demostrar que no hay tal $A_k$ puede existir, basta con demostrar que si $A_k$ interseca el casco convexo de $A_r \cup A_{r+1}$ entonces $A_r \to A_k$ o $A_k \to A_{r+1}$ pero esto es obvio si se hace el dibujo, así que lo dejaré como ejercicio :)

Como no hay dos conjuntos convexos $A\to B \to A$ hemos terminado.