Polinomio de tutte de teselaciones regulares

Abstract

En eta memoria estudiamos diversos aspectos del polinomio de Tutte de una teselación regular. Comenzamos introduciendo algunas definiciones y resultados significativos de Teoría de Grafos.

En primer lugar nos centramos en el cálculo del polinomio de Tutte de Teselaciones o masaicos del plano mediante cuadrados, triángulos , hexágonos y las posibles combinaciones de estos tres tipos de polígonos regulares, además de estudiar diversos problemas de enumeración en varias áreas de matemáticas relacionados con dicho polinomio. Ofrecemos un sistema que permite codificar estructuras en principio tan dispares como las teselaciones regualeres del plano, y un algoritmo efectivo que automatiza la llamada definición recursiva del polinomio de Tutte, y que permite el cálculo de dicho polinomio de fragmentos de teselaciones de grandes dimensiones. Hacemos hincapié en la importancia de este algoritmo ya que permite por primera vez alcanza dimensiones considerables, no solo en fragmentos de la malla cuadrada, sino en fragmentos de cualquier teselación plana mediante cuadrados, triángulos y hexágonos. Este avance supone el poder mejorar cotas de límites aasintóticos y el poder obtener importantes resultados en problemas de enumeración en Teoría de Grafos: el cálculo de orientaciones acíclicas y el cálculo de números de Whitney; y en dos problemas clásicos de Geometría, el cálculo del número de celdas en que arreglos de hiperplanos dividen a espacios euclídeos de altas dimensiones y el cálculo del número de vértices de un zonotopo.

Dejando a un lado los problemas de enumeración, nos preguntamos hasta qué punto el polinomio de Tutte determina el grafo al cual está asociado. Esta cuestión surge debido a la cantidad de invariantes asociados a un grafo contenidos en el polinomio de Tutte. En esta memoria demostramos la existencia de grandes familias de grafos que tienen esta propiedad de unicidad, a la que denominamos Tutte unicidad. Las tres familias estudiadas son los grafos localmente cuadriculados, las teselaciones hexagonales y los grafos localmente C6. Todas ellas tienen en común la propiedad de ser localmente planas y esto va a permitir probar que todas estas familias de grafos son localmente orientables, herramienta necesaria para demostrar su Tutte unicidad. En primar lugar probamos que los grafos locamente cuadriculados están unívocamente determinados por su polinomio de Tutte. A continuación clasificamos las teselaciones hexagonales y los grafos localmente C6. Estas clasificaciones adquieren gran importancia, a partir de por su propia complejidad, por ser la rectificación de la clasificación dada por Thomassen en 1991. Estudiamos además distintos invariantes asociados a estas familias de grafos y demostramos la existencia de una relación de menor con los grafos localmente cuadriculados. Por último, establecemos toda la maquinaria necesaria para demostrar la Tutte unicidad de estas familias y debido a la similitud del resto de los casos, que no aportan nada nuevo desde el punto de vista matemático, nos centramos en demostrar la Tutte unicidad de la teselación hexagonal toroidal. Con la demostración de la Tutte unicidad de los grafos localmente cuadriculados, las teselaciones hexagonales y los grafos localmente C6, es la primera vez que se prueba que existen grandes familias de grafos Tutte únicas. Como ya hemos comentado, la Tutte unicidad en matroides ha sido muy estudiada y se conocen grandes familias de matroides Tutte únicas. En el caso de los grafos, se ha estudiado la Tutte unicidad de algunas familias como los grafos multipartitos completos, hipercubos etc; pero los grafos localmente cuadriculados, las teselaciones hexagonales y los grafos localmente C6 se presentan como las primeras grandes familias de grafos Tutte únicas. Nos parece importante señalar que las dos familias de teselaciones hexagonales construidas a partir de las estructuras definidas como cilindros hexagonales torcidos, han completado el estudio realizado por Thomassen acerca de esta familia de grafos. Además, la clasificación de las teselaciones hexagonales permite la clasificación de los gráfos localmente C6; estableciéndose una relación de menor muy potente entre las tres familias de grafos estudiadas en esta parte de la memoria. Queremos resaltar que aunque, en el Capítulo 7, hemos demostrado únicamente la Tutte unicidad de la teselación hexagonal toroidal, la técnica desarrollada permite la demostración de la Tutte unicidad del resto de las teselaciones hexagonales. Además, esta técnica se puede reproducir para los grafos localmente C6, calculando las longitudes mínimas de los ciclos esenciales y el número de ciclos de dicha longitud. Pero nos gustaría ir más allá y demostrar la Tutte unicidad de estos grafos aprovechando la relación de dualidad que mantiene con las teselaciones hexagonales. En otras palabras, pensamos que al igual que en grafos planos, en los cuales se demustra que T (G; x, y) = T(G*; y, x), podemos probar una relación del tipo: T (G; x, y) = ƒ(x, y)T(G*, x, y) Siendo G un grafo localmente cuadriculado, una teselación hexagonal o un grafo localmente C6; y ƒ una función en dos variables que no dependa del grafo. Esta creencia se basa en el hecho de que todos los grafos pertenecientes a estas tres familias son localmente planos. Por otra parte, demostramos que los grafos localmente cuadriculados son Tutte único para p, q ≥ 6 pero nuestra técnica no se puede aplicar a los casos p = 3,4,5. Además, sería interesante demostrar que p’ ((q^'+ δ-1)¦δ) no es una potencia de 2. Esta demostración nos proporcionaría un resultado más general de la Tutte unicidad de T_(p,q)^δ y S_(p,q).