Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth

Aquí presento un resumen técnico detallado del artículo "Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth" de Adler, Fluck, Seppelt y Spitzer.

1. Problema y Contexto

El artículo aborda la poder expresivo de la lógica de primer orden con cuantificadores de conteo (denotada como $C$), específicamente el fragmento $C^k_q$, que combina una restricción de $k$ variables y una profundidad de cuantificación $q$.

En la teoría de modelos finitos, es fundamental caracterizar la equivalencia lógica entre grafos mediante propiedades estructurales. Se sabe que:

• La equivalencia $C^k$ (solo límite de variables) corresponde a la indistinguibilidad por homomorfismos sobre la clase de grafos de **ancho de árbol ($treewidth$)$\le k-1$** ($TW_{k-1}$).
• La equivalencia $C^q$ (solo límite de profundidad) corresponde a la indistinguibilidad sobre la clase de grafos de **profundidad de árbol ($treedepth$)$\le q$** ($TD_q$).

La pregunta central de este trabajo es: ¿Corresponde la equivalencia en el fragmento intersección $C^k_q = C^k \cap C^q$ a la indistinguibilidad por homomorfismos sobre la intersección de las clases estructurales $TW_{k-1} \cap TD_q$?

La intuición inicial sugería que sí, pero los autores demuestran que esto es falso. Introducen una nueva clase de grafos, $T^k_q$, definida por "coberturas de bosques con $k$ fichas de profundidad $q$", y demuestran que esta clase es estrictamente más pequeña que la intersección $TW_{k-1} \cap TD_q$ cuando $q$ es significativamente mayor que $k$. Además, prueban que esta separación sintáctica implica una separación semántica en las relaciones de indistinguibilidad.

2. Metodología

Los autores emplean una combinación de técnicas de teoría de grafos, teoría de juegos y lógica matemática:

1. Reprueba Elemental: Reestablecen el resultado de Dawar, Jakl y Reggio (2021) que conecta $C^k_q$ con la clase $T^k_q$, utilizando técnicas elementales inspiradas en Dvořák en lugar del marco de comonadas categóricas.
2. Juegos de Búsqueda de Nodos (Cops-and-Robber): Introducen una variante del juego de "Policías y Ladrones" para caracterizar la clase $T^k_q$. Un resultado crucial es probar que la monotonía en este juego (donde el área despejada nunca necesita ser rebuscada) es equivalente a la existencia de una estrategia ganadora no monótona.
3. Descomposiciones Pre-Árbol (Pre-tree-decompositions): Para probar la monotonía, desarrollan una nueva herramienta basada en descomposiciones de matroides. Transforman una estrategia ganadora del juego en una "pre-descomposición de árbol" y aplican un procedimiento de "limpieza" (cleaning up) en orden de búsqueda en anchura (BFS) para convertirla en una descomposición exacta sin aumentar el ancho ni la profundidad.
4. Construcciones CFI (Cai-Fürer-Immerman): Utilizan grafos altamente similares (construcciones CFI) para separar semánticamente las clases. Si un grafo $G$ no pertenece a una clase $\mathcal{F}$, construyen dos grafos $G_0$ y $G_1$ que son indistinguibles sobre $\mathcal{F}$ pero distinguibles sobre grafos que contienen a $G$.
5. Cierre de Distinguibilidad por Homomorfismos: Demuestran que las clases $T^k_q$, $TD_q$ y $TW_{k-1}$ son "cerradas bajo distinguibilidad por homomorfismos" (homomorphism distinguishing closed), validando una conjetura de Roberson para estas clases.

3. Contribuciones Clave

A. Caracterización Lógica y Estructural

Definen la clase $T^k_q$ de tres maneras equivalentes, estableciendo un puente entre lógica, descomposición y juegos:

1. Lógica: Grafos que admiten un árbol de construcción $k$-etiquetado de profundidad de eliminación $q$.
2. Estructural: Grafos que admiten una descomposición de árbol de ancho $\le k-1$ y profundidad $\le q$ (definida de manera robusta, no solo por la altura del árbol).
3. Juegos: Grafos donde el jugador "Policía" tiene una estrategia ganadora en el juego de $k$ policías y $q$ rondas (Cops-and-Robber).

B. Separación Sintáctica y Semántica

• Teorema 1.2: Demuestran que $T^k_q \subsetneq TW_{k-1} \cap TD_q$ cuando $q$ es suficientemente mayor que $k$. Esto significa que tener un ancho de árbol pequeño y una profundidad de árbol pequeña por separado no garantiza la existencia de una descomposición que satisfaga ambos límites simultáneamente.
• Teorema 1.4 y 1.3: Prueban que las clases $T^k_q$ y $TD_q$ son cerradas bajo distinguibilidad por homomorfismos. Esto es fundamental porque permite elevar la separación sintáctica de las clases a una separación semántica de sus relaciones de indistinguibilidad.
• Corolario 1.5: La relación de indistinguibilidad sobre $T^k_q$ es estrictamente más gruesa que la sobre $TW_{k-1} \cap TD_q$. Es decir, existen grafos que son lógicamente equivalentes en $C^k_q$ pero distinguibles si se consideran grafos de la intersección $TW \cap TD$.

C. Lógica de Conteo Guardada (Guarded Counting Logic)

Extienden sus resultados a la lógica de conteo guardada ($GC^k_q$), donde los cuantificadores están restringidos a vecinos de un vértice. Introducen una clase de grafos etiquetados $GT^k_q$ y pruevan que la equivalencia en $GC^k_q$ corresponde exactamente a la indistinguibilidad por homomorfismos sobre $GT^k_q$.

4. Resultados Principales

1. Equivalencia Lógica: Dos grafos son equivalentes en el fragmento $C^k_q$ si y solo si son indistinguibles por homomorfismos sobre la clase $T^k_q$ (Teorema 5.9).
2. Separación de Clases: Para $q \gg k$, la clase $T^k_q$ es un subconjunto propio de $TW_{k-1} \cap TD_q$. La intuición de que $C^k \cap C^q$ se caracteriza por $TW_{k-1} \cap TD_q$ es incorrecta.
3. Monotonía del Juego: Se prueba que para la clase $T^k_q$, la existencia de una estrategia ganadora para el jugador Policía implica la existencia de una estrategia ganadora monótona. Esto se logra mediante la construcción de una pre-descomposición de árbol y un procedimiento de limpieza que preserva el ancho y la profundidad.
4. Validación de Conjeturas: Se confirma la conjetura de Roberson para las clases $T^k_q$ y $TD_q$, demostrando que son cerradas bajo distinguibilidad por homomorfismos.

5. Significado e Impacto

• Teoría de Modelos Finitos: El trabajo refina nuestra comprensión de cómo las restricciones de variables y profundidad interactúan en la lógica de conteo. Muestra que la intersección de clases estructurales no siempre corresponde a la intersección de sus poderes expresivos lógicos.
• Redes Neuronales de Grafos (GNNs): Dado que la lógica $C^k$ y sus fragmentos están estrechamente relacionados con la capacidad expresiva de las GNNs (específicamente el algoritmo Weisfeiler-Leman), estos resultados tienen implicaciones para entender qué tipos de conteo de subgrafos y propiedades estructurales pueden ser capturados por modelos de aprendizaje profundo con recursos limitados.
• Herramientas Nuevas: La introducción de las pre-descomposiciones de árbol y el procedimiento de limpieza para probar la monotonía en juegos de búsqueda de nodos ofrece nuevas herramientas técnicas que podrían aplicarse a otros parámetros de grafos o juegos relacionados (como el ancho de árbol dirigido o el ancho hiperárbol).
• Conexión Juegos-Lógica: Refuerza la conexión profunda entre juegos de modelo (pebble games) y juegos de búsqueda de nodos (Cops-and-Robber), mostrando cómo estrategias en un juego pueden transformarse en descomposiciones estructurales y viceversa.

En resumen, el artículo proporciona una caracterización completa y precisa de la lógica de conteo con límites de variables y profundidad, desmintiendo una intuición común sobre la intersección de ancho y profundidad de árbol, y estableciendo nuevas bases para el estudio de la indistinguibilidad por homomorfismos en clases de grafos estructurados.