Teorema de la cuadrícula de Halin

En la teoría de grafos , una rama de las matemáticas, el teorema de la cuadrícula de Halin afirma que los grafos infinitos con extremos gruesos son exactamente los grafos que contienen subdivisiones del teselado hexagonal del plano. ^{[ 1 ]} Fue publicado por Rudolf Halin ( 1965 ) y es un precursor del trabajo de Robertson y Seymour que vincula el ancho de árbol con los menores de cuadrícula grandes , lo que se convirtió en un componente importante de la teoría algorítmica de la bidimensionalidad . 

En un grafo infinito, un rayo es un camino semiinfinito : un subgrafo infinito conexo en el que un vértice tiene grado uno y el resto tienen grado dos. Halin (1964) definió dos rayos.${\displaystyle r_{0}}$y${\displaystyle r_{1}}$ser equivalente si existe un rayo${\displaystyle r_{2}}$que incluye infinitos vértices de cada uno de ellos. Esta es una relación de equivalencia , y sus clases de equivalencia (conjuntos de rayos mutuamente equivalentes) se denominan extremos del grafo. Halin (1965) definió un extremo grueso de un grafo como un extremo que contiene infinitos rayos que, a pesar de ser equivalentes, son disjuntos entre sí.

Un ejemplo de grafo con un extremo grueso lo proporciona el teselado hexagonal del plano euclidiano . Sus vértices y aristas forman un grafo cúbico planar infinito , que contiene muchos rayos. Por ejemplo, algunos de sus rayos forman caminos hamiltonianos que se extienden en espiral desde un vértice central inicial y cubren todos los vértices del grafo. Uno de estos rayos en espiral puede usarse como rayo${\displaystyle r_{2}}$en la definición de equivalencia de rayos (sin importar qué rayos)${\displaystyle r_{0}}$y${\displaystyle r_{1}}$Se dan), lo que demuestra que cada par de rayos son equivalentes y que este grafo tiene un único extremo. También existen conjuntos infinitos de rayos que son todos disjuntos entre sí, por ejemplo, los conjuntos de rayos que utilizan solo dos de las seis direcciones que puede seguir un camino dentro del teselado. Debido a que tiene infinitos rayos disjuntos por pares, todos equivalentes entre sí, este grafo tiene un extremo grueso.

El teorema de Halin afirma que este ejemplo es universal: todo grafo con un extremo grueso contiene como subgrafo o bien el propio grafo, o bien un grafo formado a partir de él modificándolo de forma sencilla, subdividiendo algunas de sus aristas en caminos finitos. El subgrafo de esta forma puede elegirse de manera que sus rayos pertenezcan al extremo grueso dado. Recíprocamente, siempre que un grafo infinito contiene una subdivisión del teselado hexagonal, debe tener un extremo grueso, es decir, el extremo que contiene todos los rayos que son subgrafos de esta subdivisión. ^{[ 1 ]}

Como parte de su trabajo sobre menores de grafos que condujo al teorema de Robertson-Seymour y al teorema de estructura de grafos , Neil Robertson y Paul Seymour demostraron que una familia${\displaystyle {\mathcal {F}}}$de grafos finitos tiene ancho de árbol ilimitado si y solo si los menores de grafos en${\displaystyle {\mathcal {F}}}$Incluyen grafos de cuadrícula cuadrada arbitrariamente grandes , o equivalentemente subgrafos del teselado hexagonal formado al intersecarlo con discos arbitrariamente grandes. Aunque la relación precisa entre el ancho del árbol y el tamaño del menor de la cuadrícula sigue siendo esquiva, este resultado se convirtió en una piedra angular en la teoría de la bidimensionalidad , una caracterización de ciertos parámetros de grafos que tienen algoritmos tratables de parámetros fijos particularmente eficientes y esquemas de aproximación de tiempo polinomial . ^{[ 2 ]}

Para grafos finitos, el ancho del árbol siempre es uno menos que el orden máximo de un refugio , donde un refugio describe un cierto tipo de estrategia para que un ladrón escape de la policía en un juego de persecución-evasión jugado en el grafo, y el orden del refugio da el número de policías necesarios para atrapar a un ladrón usando esta estrategia. ^{[ 3 ]} Por lo tanto, la relación entre el ancho del árbol y los menores de la cuadrícula se puede reformular: en una familia de grafos finitos, el orden de los refugios es ilimitado si y solo si el tamaño de los menores de la cuadrícula es ilimitado. Para grafos infinitos, la equivalencia entre el ancho del árbol y el orden de los refugios ya no es cierta, sino que los refugios están íntimamente conectados a los extremos: los extremos de un grafo están en correspondencia biunívoca con los refugios cuyo orden es el número aleph.${\displaystyle \aleph _{0}}$. ^{[ 4 ]} No siempre es cierto que un grafo infinito tenga un refugio de orden infinito si y solo si tiene un menor de cuadrícula de tamaño infinito, pero el teorema de Halin proporciona una condición adicional (el grosor del extremo correspondiente al refugio) bajo la cual se vuelve verdadero.

• Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2005), "Bidimensionalidad: nuevas conexiones entre algoritmos FPT y PTAS", Actas del 16.º Simposio ACM-SIAM sobre Algoritmos Discretos (SODA) (PDF) , págs. 590–601 , MR 2298309  .
• Diestel, Reinhard (2004), "Una breve demostración del teorema de la cuadrícula de Halin", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 74 : 237– 242, doi : 10.1007/BF02941538 , MR 2112834 .
• Diestel, Reinhard; Kühn, Daniela (2003), "Graph-theoretical versus topological ends of graphs", Journal of Combinatorial Theory , Serie B, 87 (1): 197–206 , doi : 10.1016/S0095-8956(02)00034-5 , MR 1967888 .
• Halin, Rudolf (1964), "Über unendliche Wege in Graphen", Mathematische Annalen , 157 (2): 125– 137, doi : 10.1007/bf01362670 , hdl : 10338.dmlcz/102294 , MR 0170340 .
• Halin, Rudolf (1965), "Über die Maximalzahl fremder unendlicher Wege in Graphen", Mathematische Nachrichten , 30 ( 1– 2): 63– 85, doi : 10.1002/mana.19650300106 , SEÑOR 0190031 .
• Seymour, Paul D.; Thomas , Robin (1993), "Búsqueda en grafos y un teorema min-max para el ancho de árbol", Journal of Combinatorial Theory , Serie B, 58 (1): 22–33 , doi : 10.1006/jctb.1993.1027.