Which Vertical Graphs are Non VPHT Reconstructible?

Este artículo investiga la no inyectividad de la Transformada de Homología Persistente Verbose (VPHT) en grafos verticales con vértices colineales, identificando propiedades necesarias y suficientes para su no reconstruibilidad.

Lo esencial

Imagina que tienes un objeto tridimensional, como una escultura hecha de alambre (un grafo), y quieres describirlo completamente solo mirándolo desde diferentes ángulos.

En el mundo de las matemáticas y la ciencia de datos, existe una herramienta llamada Transformada de Homología Persistente Verbose (VPHT). Piensa en la VPHT como un "escáner mágico" que toma una foto de tu objeto desde todas las direcciones posibles (arriba, abajo, izquierda, derecha, en diagonal) y crea un "mapa de huellas digitales" topológico.

La gran pregunta de este artículo es: ¿Es posible reconstruir el objeto original solo con esas huellas digitales?

La respuesta corta es: Sí, casi siempre. Si tu objeto está en una posición "normal" (sus partes no están alineadas perfectamente), el escáner es tan detallado que puedes volver a armar el objeto pieza por pieza.

Pero, ¿qué pasa si el objeto es "raro" o "degenerado"? Los autores se centraron en un caso muy específico y simple: Gráficos Verticales.

La Analogía de la Escalera y los Pasos

Imagina que tienes varios puntos (nodos) pegados en una línea vertical, como escalones en una escalera muy estrecha. Ahora, imagina que conectas estos puntos con cuerdas (bordes).

1. El Escáner (VPHT): Cuando el escáner mira hacia arriba, ve cómo se van "encendiendo" los puntos y las cuerdas. Cuando mira hacia abajo, ve el proceso inverso.
2. El Problema: Los autores descubrieron que, en esta configuración vertical, existen dos objetos diferentes que, al ser escaneados desde arriba y desde abajo, producen exactamente el mismo mapa de huellas digitales.

Es como si tuvieras dos torres de Lego diferentes:

• Torre A: Tiene una estructura interna específica.
• Torre B: Tiene una estructura interna diferente.
• El Truco: Si miras ambas torres desde arriba o desde abajo, parecen tener exactamente la misma forma y el mismo número de piezas en cada nivel. El escáner no puede distinguir cuál es cuál.

¿Cómo es posible esto? (La Magia de los "Ciclos Alternados")

El secreto de estos objetos "indistinguibles" reside en algo que los autores llaman "Pares Colisionantes Simples" y "Ciclos Alternados".

Imagina un juego de ida y vuelta:

• Tienes dos grafos (dos conjuntos de cuerdas).
• Si tomas todas las cuerdas del Grafo 1 y las orientas hacia arriba, y tomas todas las cuerdas del Grafo 2 y las orientas hacia abajo, y las pones juntas, se forma un ciclo (un círculo) donde las cuerdas suben y bajan alternadamente: Sube, baja, sube, baja...

La metáfora del baile:
Piensa en dos parejas de bailarines (los dos grafos).

• En la Pareja A, el hombre da un paso adelante y la mujer uno atrás.
• En la Pareja B, la mujer da un paso adelante y el hombre uno atrás.
• Si los miras desde arriba (una vista cenital), ambos pares parecen estar haciendo el mismo movimiento circular. El escáner no puede decir quién es quién porque el "patrón de movimiento" (la topología) es idéntico.

¿Qué descubrieron los autores?

1. La Regla de los Números Pares: Para que dos grafos verticales sean indistinguibles, cada punto (nodo) debe tener un número par de conexiones que van hacia abajo y un número par de conexiones que van hacia arriba. Si un punto tiene un número impar de conexiones en alguna dirección, el escáner puede detectarlo y distinguir los grafos.
2. La Estructura Oculta: Si dos grafos son indistinguibles, sus uniones siempre forman estos "ciclos alternados" (sube-baja-sube-baja).
3. La Prueba Computacional: Usaron una computadora para probar miles de grafos pequeños (con hasta 7 puntos). Confirmaron que todos los casos donde el escáner fallaba en distinguir los grafos seguían esta regla de los "ciclos alternados".

¿Por qué importa esto?

Imagina que eres un ingeniero que intenta reconstruir un puente o un chip electrónico basándose solo en datos de sensores que miran desde ciertas direcciones.

• Advertencia: Si los puntos clave de tu estructura están alineados verticalmente (como en un rascacielos muy estrecho) y las conexiones siguen este patrón de "subir y bajar" alternado, tus sensores podrían engañarte. Podrías pensar que tienes el diseño A, cuando en realidad tienes el diseño B.
• Consejo: El papel nos dice que, para evitar este error, debemos elegir direcciones de escaneo que no vean los vértices y bordes en el mismo orden que estos "grafos verticales trampa".

En resumen

El artículo nos dice que, aunque la tecnología de escaneo topológico es muy poderosa, tiene un "punto ciego" muy específico: cuando los objetos están perfectamente alineados en una línea vertical y sus conexiones forman patrones de "subida y bajada" alternados. En esos casos, dos objetos diferentes pueden parecer idénticos al escáner, como dos gemelos que visten exactamente igual y caminan al mismo ritmo, haciendo imposible saber cuál es cuál sin mirar más de cerca.

Resumen técnico

Resumen Técnico: Grafos Verticales y la No Reconstructibilidad del VPHT

1. Planteamiento del Problema

El Transformado de Homología Persistente Verbose (VPHT, por sus siglas en inglés) es una herramienta topológica que resume la forma de objetos en el espacio euclidiano mediante diagramas de persistencia generados a partir de filtraciones de altura en todas las direcciones posibles.

• Contexto: Se sabe que para complejos simpliciales en posición general (donde los vértices no son colineales), el VPHT es inyectivo, lo que significa que la forma original se puede reconstruir a partir del transformado.
• El Problema: Este trabajo investiga el caso opuesto: ¿bajo qué condiciones el VPHT no es inyectivo? Específicamente, se centran en configuraciones degeneradas simples: grafos verticales, donde todos los vértices son colineales (alineados en una línea vertical). El objetivo es identificar familias de grafos que, a pesar de ser distintos, produzcan el mismo VPHT, haciéndolos no reconstructibles.

2. Metodología

Los autores combinan un análisis teórico riguroso con una validación computacional exhaustiva.

• Definiciones Clave:

  • Grafo Vertical: Un grafo cuyos vértices están en una línea vertical. Se define un orden de altura $v_i < v_j$ si $v_j$ está por encima de $v_i$.
  • VPHT: El conjunto de diagramas de persistencia "verbose" (detallados) obtenidos filtrando el grafo en todas las direcciones. Los diagramas "verbose" incluyen puntos en la diagonal que corresponden a la creación instantánea y muerte de componentes conectados, proporcionando más información que los diagramas concisos estándar.
  • Pareja Colisionante Simple (Simple Colliding Pair): Dos grafos verticales $G_1$ y $G_2$ forman una pareja colisionante si, al orientar todas las aristas de $G_1$ hacia arriba y las de $G_2$ hacia abajo, su unión disjunta forma un ciclo alternante (una secuencia de aristas que alterna entre dirección "arriba" y "abajo").

• Enfoque Teórico:

  • Se demuestra que para grafos verticales, el VPHT completo puede deducirse de solo dos direcciones: "arriba" y "abajo".
  • Se utiliza la correspondencia biunívoca entre los vértices y los puntos de nacimiento de componentes conectados en el diagrama verbose, y entre las aristas y las muertes de componentes o nacimientos de ciclos.
  • Se emplea inducción y recursión sobre particiones de ciclos para analizar las propiedades de grado de los vértices.

• Enfoque Computacional:

  • Se desarrolló una herramienta de software (interfaz gráfica y algoritmos de búsqueda exhaustiva) para generar grafos verticales pequeños y calcular sus VPHT.
  • Se realizó una búsqueda de fuerza bruta en grafos con hasta 7 vértices para verificar si existen pares no reconstructibles que no cumplan con la estructura teórica propuesta.

3. Contribuciones Clave y Resultados Principales

A. Caracterización de Grafos No Reconstructibles (Teorema 9)
Los autores identifican una familia específica de grafos que son no reconstructibles:

• Si un grafo vertical $G$ puede particionarse en ciclos alternantes ($G_1, \dots, G_k$) tal que cada ciclo se divide en una pareja colisionante simple, y si cada vértice tiene a lo sumo dos vecinos inferiores y dos superiores, entonces los grafos resultantes de la partición ($G_1$ y $G_2$) tienen el mismo VPHT.
• Mecanismo: En estas configuraciones, la estructura de los componentes conectados y los ciclos en las direcciones "arriba" y "abajo" es idéntica para ambos grafos, a pesar de que sus conjuntos de aristas son diferentes.

B. Condiciones Necesarias (Teorema 11 y Lema 10)
Se establece una condición necesaria para la no reconstructibilidad:

• Lema 10: Un grafo vertical es de "tipo G" (particionable en ciclos alternantes) si y solo si, para todo vértice $v$, el número de aristas hacia abajo ($ldeg$) y hacia arriba ($hdeg$) son números pares.
• Teorema 11: Si un par de grafos verticales $(G_1, G_2)$ no es una pareja colisionante (es decir, no cumplen la estructura de ciclos alternantes), entonces sus VPHT son distintos. Esto implica que la condición de ser una pareja colisionante es esencial para la no reconstructibilidad en este contexto.

C. Validación Computacional (Lema 13 y Corolario 15)

• Mediante búsqueda exhaustiva en grafos con hasta 7 vértices, se confirmó que todos los pares de grafos verticales con el mismo VPHT son parejas colisionantes.
• Se verificó que existe una partición en ciclos alternantes donde las aristas comunes a ambos grafos forman ciclos de longitud dos. Esto sugiere fuertemente que la estructura de "pareja colisionante" es la única causa de no reconstructibilidad para grafos verticales pequeños.

D. Estabilidad bajo Adición de Ciclos (Lema 12)

• Se demuestra que agregar copias de ciclos alternantes a una pareja colisionante existente no altera su estado de no reconstructibilidad. Esto permite construir familias infinitas de grafos no reconstructibles a partir de ejemplos base.

4. Significado e Impacto

• Clasificación de la Degeneración: El trabajo avanza hacia una clasificación completa de cuándo falla la inyectividad del VPHT. Mientras que la posición general garantiza la reconstructibilidad, este estudio delimita exactamente cómo la colinealidad de los vértices puede ocultar la estructura del grafo.
• Implicaciones para el Análisis de Datos: Los resultados informan sobre la selección de direcciones de escaneo en aplicaciones prácticas de Análisis Topológico de Datos (TDA). Si una dirección de escaneo en un grafo general proyecta los vértices y aristas en un orden similar al de un grafo vertical no reconstructible, esa dirección por sí sola no será suficiente para determinar el conjunto de aristas del grafo original.
• Herramienta Práctica: La publicación del código fuente y la aplicación web permite a la comunidad explorar visualmente estas propiedades topológicas, facilitando la investigación futura en la relación entre la geometría de los datos y su representación topológica.

En conclusión, el paper demuestra que la no reconstructibilidad del VPHT en grafos verticales está intrínsecamente ligada a la existencia de ciclos alternantes que permiten "intercambiar" aristas entre dos grafos distintos sin alterar la firma topológica (VPHT) en ninguna dirección.