We will discuss three ways to bound the chromatic number on a Cayley graph. 1. If the connection set contains information about a smaller graph, then these two graphs are related. Using this information, we will show that Cayley graphs cannot have chromatic number three. 2. We will prove a general statement that all vertex-transitive maximal triangle-free graphs on <i>n</i> vertices with valency greater than <i>n</i>/3 are 3-colourable. Since Cayley graphs are vertex-transitive, the bound of general graphs also applies to Cayley graphs. 3. Since Cayley graphs for abelian groups arise from vector spaces, we can view the connection set as a set of points in a projective geometry. We will give a characterization of all large complete caps, from which we derive that all maximal triangle-free cubelike graphs on 2ⁿ vertices and valency greater than 2ⁿ/4 are either bipartite or 4-colourable.

No description available.

M.Sc. / Within the field of Graph Theory the many ways in which graphs can be coloured have received a lot of attention over the years. T.R. Jensen and B. Toft provided a summary in [8] of the most important results and research done in this field. These results were cited by R. Diestel in [5] as “The Four Colour Problem” wherein it is attempted to colour every map with four colours in such a way that adjacent countries will be assigned different colours. This was first noted as a problem by Francis Guthrie in 1852 and later, in 1878, by Cayley who presented it to the London Mathematical Society. In 1879 Kempe published a proof, but it was incorrect and lead to the adjustment by Heawood in 1890 to prove the five colour theorem. In 1977 Appel and Haken were the first to publish a solution for the four colour problem in [2] of which the proof was mostly based on work done by Birkhoff and Heesch. The proof is done in two steps that can be described as follows: firstly it is shown that every triangulation contains at least one of 1482 certain “unavoidable configurations” and secondly, by using a computer, it is shown that each of these configurations is “reducible”. In this context the term “reducible” is used in the sense that any plane triangulation containing such a configuration is 4-colourable by piecing together 4- colourings of smaller plane triangulations. These two steps resulted in an inductive proof that all plane triangulations and therefore all planar graphs are 4-colourable.

Thompson’s groups F, T, and V represent crucial examples of groups in geometric group theory that bridge it with other areas of mathematics such as logic, computer science, analysis, and geometry. One of the ways to study these groups is by understanding the geometric meaning of their actions. In this thesis we deal with Thompson’s group T that acts naturally on the unit circle S1, that is identified with the segment [0, 1] with the end points glued together. The main result of this work is the explicit construction of the Schreier graph of T with respect to the action on the orbit of 1/2. This is done by careful examination of patterns in how the generators of T act on binary words. As a main application, the nonamenability of the action of T on S1 is proved by defining injections on the set of vertices of the constructed graph that satisfy Gromov’s doubling condition. This gives an alternative proof of the known fact that T is nonamenable.

No description available.

We determine necessary and sufficient conditions for a Cayley digraph of the cyclic group of order n to have the property that any other Cayley digraph of a cyclic group of order n is isomorphic to the first if and only if an isomorphism between the two digraphs is a group automorphism of the cyclic group of order n.

No description available.

In this dissertation the Bays-Lambossy theorem is generalized to GF(pn). The Bays-Lambossy theorem states that if two Cayley objects each based on GF(p) are isomorphic then they are isomorphic by a multiplier map. We use this characterization to show that under certain conditions two isomorphic Cayley objects over GF(pn) must be isomorphic by a function on GF(pn) of a particular type.

Geometric semigroup theory means different things to different people, but it is agreed that it involves associating a geometric structure to a semigroup and deducing properties of the semigroup based on that structure. One such property is finite presentability. In geometric group theory, the geometric structure of choice is the Cayley graph of the group. It is known that in group theory finite presentability is an invariant under quasi-isometry of Cayley graphs. We choose to associate a metric space to a semigroup based on a Cayley graph of that semigroup. This metric space is constructed by removing directions, multiple edges and loops from the Cayley graph. We call this a skeleton of the semigroup. We show that finite presentability of certain types of direct products, completely (0-)simple, and Clifford semigroups is preserved under isomorphism of skeletons. A major tool employed in this is the Švarc-Milnor Lemma. We present an example that shows that in general, finite presentability is not an invariant property under isomorphism of skeletons of semigroups, and in fact is not an invariant property under quasi-isometry of Cayley graphs for semigroups. We give several skeletons and describe fully the semigroups that can be associated to these.

Cette thèse porte sur deux types de problèmes de mécanique statistique : il y est question de percolation sur les groupes et de modèles dirigés. Dans le premier cas,il s’agit de réaliser un groupe comme objet géométrique (via la notion de graphe de Cayley), puis de morceler ce dernier aléatoirement. L’étude de ce processus révèle des liens étroits entre les propriétés géométriques d’un groupe et le comportement de la percolation de Bernoulli sur celui-Ci. Dans le second cas, on s’intéresse à des modèles où haut et bas jouent des rôles différents, ce qui permet de rendre un certain nombre de questions accessibles à l’étude rigoureuse.Le chapitre 1 renforce le théorème d’indistinguabilité de Lyons et Schramm en percolation, lequel stipule que les composantes connexes infinies fournies par la percolation de Bernoulli sur un graphe de Cayley ont presque sûrement toutes la même allure. La non-Trivialité de ce renforcement est illustrée par un modèle dirigé qui vérifie la propriété d’indistinguabilité mais pas la propriété renforcée.Le chapitre 2 est le fruit d’un travail réalisé en collaboration avec Vincent Tassion.On y démontre que la valeur du paramètre critique pour la percolation de Bernoulli ne dépend essentiellement que de la structure locale du graphe de Cayley abélien considéré.Dans le chapitre 3, on introduit une version dirigée du modèle DLA, pour laquelle on établit l’existence d’une dynamique en volume infini, un contrôle sur la propagation d’information et des inégalités asymptotiques sur la largeur et la hauteur de l’agrégat. / This thesis deals with two kinds of statistical mechanics problems: percolation ongroups and directed models. In the first case, we realise the group under considerationas a geometric object (via the notion of Cayley graph) before breaking it apartrandomly. The study of this process reveals deep connections between the geometricproperties of a group and the behaviour of Bernoulli percolation on it. In the secondcase, we focus on models where up and down play different roles, which makes severalquestions less hard to tackle.Chapter 1 strengthens the Indistinguishability Theorem of Lyons-Schramm, whichstates that the infinite clusters yielded by a Bernoulli percolation on a Cayley graphalmost surely all look alike. The non-Triviality of this strengthening is illustrated bya directed model that satisfies the Indistinguishability Property but not the StrongIndistinguishability Property.Chapter 2 has been obtained in collaboration with Vincent Tassion. We show thatthe value of the critical parameter for Bernoulli percolation essentially only dependson the local structure of the considered abelian Cayley graph.In Chapter 3, we introduce a directed version of the DLA model, for which weestablish the existence of an infinite volume dynamics, control the propagation ofinformation and prove asymptotic inequalities on the width and height of the cluster.