Colored combinatorial structures: homomorphisms and counting

Author

Montejano Cantoral, Amanda

Director

Serra Albó, Oriol

Tutor

Hurtado, Ferran

Date of defense

2009-06-09

ISBN

9788469470480

Legal Deposit

B. 27887-2011

Pages

153 p.



Department/Institute

Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística

Abstract

A partir del problema de los cuatro colores se inicia el estudio de coloraciones en grafos; teoría que ha existido ya por más de 150 años, y se ocupa del problema fundamental de partir un conjunto en clases de acuerdo con ciertas reglas. Con esta modesta base, dicha teoría se sitúa en un punto central de las matemáticas discretas con una gran cantidad de generalizaciones y aplicaciones contemporáneas. En esta tesis, centramos nuestro interés en dos áreas muy activas de investigación, que provienen de problemas en coloraciones: la teoría de Homomorfismos, y la teoría de Ramsey. La teoría de homomorfismos se ocupa del estudio de los morfismos naturales entre objetos pertenecientes a clases de estructuras combinatorias. El número cromático de un grafo simple G, se puede definir, en este contexto, como el orden mínimo de un grafo completo que admita un homomorfismo desde G. Por esta razón, la teoría de homomorfismos se ha estudiado extensamente como generalización de la teoría de coloraciones. Una excelente referencia en este tema es el libro de Hell y Nesetril {Graphs and homomorphisms, Oxf. Univ. Press, 2004}. La teoría de Ramsey estudia la existencia de ciertos patrones de color en estructuras coloreadas. A partir de los teoremas de Ramsey, Hilbert, Schur y van der Waerden, dicha teoría se ha desarrollado como una bella y amplia área de la combinatoria, donde se usan una gran variedad de técnicas provenientes de diversas ramas de la matemática, y cuyos resultados forman una parte muy importante de la teoría de grafos y la combinatoria en general. Una buena referencia en esta área es el libro de Langman y Robertson {Ramsey Theory on the Integers, Stud. Math. Lib. 24, AMS, 2003}. El trabajo en esta tesis está organizado en dos partes. La primera, se ocupa del estudio de homomorfismos de grafos mixtos coloreados, que son grafos con vértices unidos tanto por arcos coloreados como por aristas coloreadas. El número cromático de un grafo mixto coloreado G, se define como el mínimo orden do otro grafo mixto coloreado H, con la propiedad de que existe un homomorfismo (que preserva colores) de G en H. Estas nociones fueron introducidas por Nesetril y Raspaud en {Colored homomorphisms of colored mixed graphs, J. C. T. Ser. B 80 (2000)}. Generalizando algunos resultados de grafos orientados, estudiamos el número cromático mixto coloreado de las siguientes clases de grafos: caminos, árboles, grafos con número cromático acíclico acotado, k-árboles parciales, grafos planos, grafos outerplanos y grafos escasos en aristas. Motivados por la conjetura de la dicotomía en sistemas relacionales, nos interesamos en el estudio de la clases de grafos 2-coloreados en aristas y su relación con los grafos orientados. La segunda parte de la tesis se ubica dentro de la teoría de Ramsey aritmética. Estudiamos la existencia y enumeración de estructuras coloreadas, sobre todo monocromáticas y heterocromáticas, en coloraciones de grupos abelianos. Las estructuras que consideramos son soluciones de sistemas de ecuaciones en grupos, siendo los ejemplos más importantes las progresiones aritméticas y las ternas de Schur. En esta parte damos una descripción estructural de aquellas coloraciones en grupos abelianos que no contengan progresiones aritmeticas heterocromáticas de tamaño 3. Dicha descripción prueba una conjetura de Jungic et al. {Rainbow Ramsey Theory. Integers: E. J. C. N. T. 5(2) A9. (2005)} concerniente al tamaño de la clase cromática mas pequeña en dichas coloraciones de grupos cíclicos.


Starting with the four color problem, the theory of graph coloring has existed for more than 150 years. It deals with the fundamental problem of partitioning a set of objects into classes according to certain rules. From this modest beginning, the theory has become central in discrete mathematics, with many contemporary generalizations and applications. In this thesis, our particular interest is in two very active areas of research which have emerged from coloring problems: Graph Homomorphism Theory and Arithmetic Ramsey Theory. Graph Homomorphism Theory can be described as the study of classes of combinatorial structures under natural morphisms. The chromatic number of a simple graph G can be stated, in this context, as the smallest complete graph to which G admits a homomorphism. Thus Graph Homomorphism Theory has been extensively studied as a generalization of colorings. An excellent reference in the subject is the book by Hell and Nesetril {Graphs and homomorphisms, Oxf. Univ. Press, 2004}. Ramsey Theory studies the existence of particular color patterns in colored structures. Starting with the Theorems of Ramsey, Hilbert, Schur and van der Waerden, the theory has developed as a wide and beautiful area of combinatorics, in which a great variety of techniques are used from many branches of mathematics. Many of the classical results in the area are arithmetic versions of the theory and we are interested in this particular branch of Ramsey Theory. A good reference in the area is the book of Langman and Robertson {Ramsey Theory on the Integers, Stud. Math. Lib. 24, AMS, 2003}. This thesis is organized in two parts. The first part deals with the study of homomorphisms in the class of colored mixed graphs, which are graphs with vertices linked by both colored arcs and colored edges. The chromatic number of such a graph G is defined as the smallest order of a colored mixed graph H such that there exists a (color preserving) homomorphism from G to H. These notions were introduced by Nesetril and Raspaud in {Colored homomorphisms of colored mixed graphs, J. C. T. Ser. B 80 (2000)}. Generalizing known results for the class of oriented graphs we study the colored mixed chromatic number of paths, trees, graphs with bounded acyclic chromatic number, graphs of bounded treewidth, planar graphs, outerplanar graphs and sparse graphs. In particular we give the exact chormatic number of planar graphs and of partial 2-trees with appropriately large girth. Motivated by the dichotomy conjecture for relational structures we focuss on the class of 2-edge colored graphs and study its relationship with the class of oriented graphs. In particular we consider the characterization of cores and of duality pairs in this class. The second part of the thesis is related to Arithmetic Ramsey Theory. We consider the existence and the enumeration of colored structures, mainly monochromatic or rainbow structures, in colorings of finite groups. The structures under consideration can be described as solutions of systems of equations in the group, the main examples being arithmetic progressions and Schur triples. We give a structural description of those colorings in abelian groups which do not contain 3-term arithmetic progressions with its members having pairwise distinct colors. This structural description proves a conjecture of Jungic et al. {Rainbow Ramsey Theory. Integers: E. J. C. N. T. 5(2) A9. (2005)} on the size of the smallest chromatic class of such colorings in cyclic groups.

Subjects

51 - Mathematics

Documents

TAMC1de2.pdf

10.69Mb

TAMC2de2.pdf

5.660Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)