Contributions relating graph coloring to topics in ergodic theory and arithmetic combinatorics

Abstract

Los resultados presentados en esta tesis contribuyen a la teoría de grafos y a la teoría combinatoria de números, mediante el desarrollo de conexiones (establecidas recientemente) entre temas en estas áreas y herramientas centrales de teoría ergódica y geometría de números. Respecto a la teoría de grafos, la tesis contribuye al tema de coloración de vértices de grafos con nuevas nociones que refinan los números cromáticos fraccionario y circular. En particular, formalizamos y estudiamos el nuevo concepto de girocoloración de grafos. Nuestros resultados muestran que esta noción y su número cromático asociado (el número girocromático), son conceptos naturales y robustos con propiedades interesantes. Los aspectos analíticos no triviales del número girocromático también nos condujeron a otra noción de coloración natural y más manejable, en la que los vértices de un grafo G se colorean por traslaciones de una caja en el toro de dimensión d, refinando el número cromático circular mediante el número cromático d-toral, y estableciendo conexiones con problemas conocidos relativos a recubrimientos de toros. Los diversos resultados que obtuvimos sobre los números girocromático y d-torales también conducen a problemas abiertos que motivan futuras investigaciones. En cuanto a la teoría combinatoria de números, la tesis contribuye al tema del problema de Motzkin, una cuestión muy natural y conocida en este ámbito, que se viene estudiando desde los años 1970. Mientras que los numerosos trabajos anteriores sobre este problema se centraron en el entorno original de los números enteros, y se trataron varios casos especiales del problema con técnicas muy específicas a cada caso, en esta tesis adoptamos un enfoque amplio del problema general, estudiándolo en otros grupos abelianos y relacionándolo con herramientas de la teoría ergódica (como el lema de Rokhlin) y de la geometría de los números. Ilustramos esto considerando el análogo del problema de Motzkin en el grupo circular (que subsume el problema original), obteniendo en particular una solución exacta cuando el conjunto de diferencias prohibidas tiene dos elementos, al menos uno de los cuales es irracional. En el caso en que las diferencias prohibidas sean todas racionales, el enfoque geométrico que utilizamos conduce a estimaciones asintóticamente exactas de la ratio de independencia de un grafo circulante de 2 saltos, en términos de la circunferencia impar del grafo, abriendo interesantes perspectivas de estudios similares para grafos circulantes de d saltos con d>2