>Magister Scientiae - MSc / For integers n, k 2:: 1, and k ~ n, the graph r~has vertices the 2n vectors of lF2 and adjacency defined by two vectors being adjacent if they differ in k coordinate positions. In particular, r~is the classical n-cube, usually denoted by Hl (n, 2). This study examines the codes (both binary and p-ary for p an odd prime) of the row span of adjacency and incidence matrices of these graphs. We first examine codes of the adjacency matrices of the n-cube. These have been considered in [14]. We then consider codes generated by both incidence and adjacency matrices of the Hamming graphs Hl(n,3) [12]. We will also consider codes of the line graphs of the n-cube as in [13]. Further, the automorphism groups of the codes, designs and graphs will be examined, highlighting where there is an interplay. Where possible, suitable permutation decoding sets will be given.

We attempt to determine the structure of the automorphism group of a generic circulant graph. We first show that almost all circulant graphs have automorphism groups as small as possible. Dobson has conjectured that almost all of the remaining circulant (di)graphs (those whose automorphism groups are not as small as possible) are normal circulant (di)graphs. We show this conjecture is not true in general, but is true if we consider only those circulant (di)graphs whose orders are in a “large” subset of integers. We note that all non-normal circulant (di)graphs can be classified into two natural classes (generalized wreath products, and deleted wreath type), and show that neither of these classes contains almost every non-normal circulant digraph.

It is known that a Cayley digraph of an abelian group A is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup B of A such that the connection set without B is a union of cosets of B in A. We generalize this result to Cayley digraphs of nonabelian groups G by showing that such a digraph is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup H of G such that S without H is a union of double cosets of H in G. This result is proven in the more general situation of a double coset digraph (also known as a Sabidussi coset digraph.) We then give applications of this result which include obtaining a graph theoretic definition of double coset digraphs, and determining the relationship between a double coset digraph and its corresponding Cayley digraph. We further expand the result obtained for double coset digraphs to a collection of bipartite graphs called bi-coset graphs and the bipartite equivalent to Cayley graphs called Haar graphs. Instead of considering when this collection of graphs is a wreath product, we consider the more general graph product known as an X-join by showing that a connected bi-coset graph of a group G with respect to some subgroups L and R of G is isomorphic to an X-join of a collection of empty graphs if and only if the connection set is a union of double cosets of some subgroups N containing L and M containing R in G. The automorphism group of such -joins is also found. We also prove that disconnected bi-coset graphs are always isomorphic to a wreath product of an empty graph with a bi-coset graph.

Quantum walks have been utilized by many quantum algorithms which provide improved performance over their classical counterparts. Quantum search algorithms, the quantum analogues of spatial search algorithms, have been studied on a wide variety of structures. We study quantum walks and searches on the Cayley graphs of finitely-generated free groups. Return properties are analyzed via Green’s functions, and quantum searches are examined. Additionally, the stopping times and success rates of quantum searches on random networks are experimentally estimated. / Mathematics

We first introduce the octonions as an eight dimensional vector space over a field of characteristic zero with a multiplication defined using a table. We also show that the multiplication rules for octonions can be derived from a special graph with seven vertices call the Fano Plane. Next we explain the Cayley-Dickson construction, which exhibits the octonions as the set of ordered pairs of quaternions. This approach parallels the realization of the complex numbers as ordered pairs of real numbers. The rest of the thesis is devoted to following a paper by N. Jacobson written in 1939 entitled "Cayley Numbers and Normal Simple Lie Algebras of Type G". We prove that the algebra of derivations on the octonions is a Lie algebra of type G_2. The proof proceeds by showing the set of derivations on the octonions is a Lie algebra, has dimension fourteen, and is semisimple. Next, we complexify the algebra of derivations on the octonions and show the complexification is simple. This suffices to show the complexification of the algebra of derivations is isomorphic to g_2 since g_2 is the only semisimple complex Lie algebra of dimension fourteen. Finally, we conclude the algebra of derivations on the octonions is a simple Lie algebra of type G_2. / Master of Science

São estudados alguns aspectos das álgebras alternativas, como o bar-radical de uma álgebra bárica alternativa e as identidades de grau 4 e 5 nas álgebras de Cayley-Dickson. Neste estudo fazemos uso da decomposição de Peirce e de diversas propriedades importantes das álgebras alternativas. Concluímos mostrando que as únicas identidades de grau 4 são as triviais e as de grau 5 são conseqüência de outras duas identidades conhecidas / We studied some aspects of alternative algebras, in special the bar radical of an alternative baric algebra and identities of degree 4 and 5 of Cayley-Dickson algebras. We made significant use of the Peirce decomposition and several properties of the alternative algebras, in order to show that the only identities of degree four are the trivial ones, and the identities of degree five are consequences of other two known identities.

Ma thèse se situe à l'intersection de \textit {la théorie des groupes géométrique} et \textit{la théorie des groupes mesurée}. Une question majeure dans la théorie des groupes géométrique est d'étudier la classe de quasi-isométrie (QI) et la classe d'équivalence mesurée (ME) d'un groupe, respectivement. $L^p$-équivalence mesurée est une relation d'équivalence qui est définie en ajoutant des contraintes géométriques avec d'équivalence mesurée. En plus, QI est une condition géométrique. Il est une question naturelle, si deux groupes sont QI et ME, si elles sont $L^p$-ME pour certains $p>0$. Dans mon premier article, en collaboration avec R. Tessera, nous répondons négativement à cette question pour $p\geq 1$, montrant que l'extension centrale canonique d'un groupe surface de genre plus élevé ne sont pas $L^1$-ME pour le produit direct de ce groupe de surface avec $\mathbb{Z}$ (alors qu'ils sont à la fois quasi-isométrique et équivalente mesurée).Dans mon deuxième papier, j'ai observé un lien général entre la géométrie des expandeurs, defini comme une séquence des quotients finis ( l'espace de boîte) d'un groupe finiment engendré, et les propriétés mesurée theorique du groupe. Plus précisément, je l'ai prouvé que si deux <<espaces de boîte>> sont quasi-isométrique, les groupes correspondants doivent être <<mesurée équivalente uniformément >>, une notion qui combine à la fois QI et ME. Je prouve aussi une version de ce résultat pour le plongement grossière, ce qui permet de distinguer plusieurs classe des expandeurs. Par exemple, je montre que les expandeurs associé à $SL(m, \mathbb{Z})$ ne grossièrement plongent à les expandeurs associés à $SL_n(\mathbb{Z})$ si $m>n$. / My thesis lies at the intersection of \textit{geometric group theory} and \textit{measured group theory}. A major question in geometric group theory is to study the quasi-isometry (QI) class and the measure equivalence (ME) class of a group, respectively. $L^p$-measure equivalence is an equivalence relation which is defined by adding some geometric constraints with measure equivalence. Besides, quasi-isometry is a geometric condition. It is a natural question if two groups are QI and ME, whether they are $L^p$-ME for some $p>0$. In my first paper, together with R. Tessera, we answer this question negatively for $p\geq 1$, showing that the canonical central extension of a surface group of higher genus is not $L^1$-ME to the direct product of this surface group with $\mathbb{Z}$ (while they are both quasi-isometric and measure equivalent). In my second paper, I observed a general link between the geometry of expanders arising as a sequence of finite quotients (box space) of a finitely generated group, and the measured theoretic properties of the group. More precisely, I proved that if two box spaces' are quasi-isometric, then the corresponding groups must be `uniformly measure equivalent', a notion that combines both quasi-isometry and measure equivalence. I also prove a version of this result for coarse embedding, allowing to distinguish many classes of expanders. For instance, I show that the expanders associated to $SL(m,\mathbb{Z})$ do not coarsely embed inside the expanders associated to $SL_n(\mathbb{Z}$ if $m>n$.

São estudados alguns aspectos das álgebras alternativas, como o bar-radical de uma álgebra bárica alternativa e as identidades de grau 4 e 5 nas álgebras de Cayley-Dickson. Neste estudo fazemos uso da decomposição de Peirce e de diversas propriedades importantes das álgebras alternativas. Concluímos mostrando que as únicas identidades de grau 4 são as triviais e as de grau 5 são conseqüência de outras duas identidades conhecidas / We studied some aspects of alternative algebras, in special the bar radical of an alternative baric algebra and identities of degree 4 and 5 of Cayley-Dickson algebras. We made significant use of the Peirce decomposition and several properties of the alternative algebras, in order to show that the only identities of degree four are the trivial ones, and the identities of degree five are consequences of other two known identities.

Dizertační práce se zabývá konstrukcí obecného řešení slabě zpožděných systémů lineárních diskrétních rovnic v ${\mathbb R}^3$ tvaru \begin{equation*} x(k+1)=Ax(k)+Bx(k-m), \end{equation*} kde $m>0$ je kladné celé číslo, $x\colon \bZ_{-m}^{\infty}\to\bR^3$, $\bZ_{-m}^{\infty} := \{-m, -m+1, \dots, \infty\}$, $k\in\bZ_0^{\infty}$, $A=(a_{ij})$ a $B=(b_{ij})$ jsou konstantní $3\times 3$ matice. Charakteristické rovnice těchto systémů jsou identické s charakteristickými rovnicemi systému, který neobsahuje zpožděné členy. Jsou získána kriteria garantující, že daný systém je slabě zpožděný a následně jsou tato kritéria specifikována pro všechny možné případy Jordanova tvaru matice $A$. Systém je vyřešen pomocí metody, která ho transformuje na systém vyšší dimenze, ale bez zpoždění \begin{equation*} y(k+1)=\mathcal{A}y(k), \end{equation*} kde ${\mathrm{dim}}\ y = 3(m+1)$. Pomocí metod lineární algebry je možné najít Jordanovy formy matice $\mathcal{A}$ v závislosti na vlastních číslech matic $A$ and $B$. Tudíž lze nalézt obecné řešení nového systému a v důsledku toho pak odvodit obecné řešení počátečního systému.

Réalisé avec le support financier du Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG) et du Fonds de Recherche du Québec – Nature et technologies (FRQNT). / Ce mémoire étudie le jeu de policiers-voleur et contient trois articles, chacun portant sur une classe de graphes spécifique. Dans le premier chapitre, la notation et les définitions de base de la théorie de graphe qui nous serons utiles sont introduites. Bien que chaque article comporte une introduction citant les concepts et résultats pertinents, le premier chapitre de ce mémoire contient aussi une introduction générale au jeu de policiers-voleur et présente certains des résultats majeurs sur ce jeu. Le deuxième chapitre contient l’article écrit avec Seyyed Aliasghar Hosseini et Peter Bradshaw portant sur le jeu de policiers-voleurs sur les graphes de Cayley abéliens. Nous améliorons la borne supérieure sur le cop number de ces graphes en raffinant les méthodes utilisées précédemment par Hamidoune, Frankl et Bradshaw. Le troisième chapitre présente l’article concernant le cop number des graphes 2K2-libres. Plus précisément, il est prouvé que 2 policiers peuvent toujours capturer le voleur sur ces graphes, prouvant ainsi la conjecture de Sivaraman et Testa. Finalement, le quatrième chapitre est l’article écrit avec Samuel Yvon et porte sur les graphes qui ont cop number 4. Nous montrons que tous ces graphes ont au moins 19 sommets. En d’autres mots, 3 policiers peuvent toujours capturer le voleur sur tout graphe avec au plus 18 sommets, ce qui répond par la négative à une question de Andreae formulée en 1986. Un pan important de la preuve est faite par ordinateur; ce mémoire contient donc une annexe comprenant le code utilisé. / This thesis studies the game of cops and robbers and consists of three articles, each considering a specific class of graphs. In the first chapter, notation and basic definitions of graph theory are introduced. Al- though each article has an introduction citing the relevant concepts and results, the first chapter of this thesis also contains a general introduction to the game of cops and robbers and presents some of its major results. The second chapter contains the paper written with Seyyed Aliasghar Hosseini and Peter Bradshaw on the game of cops and robbers on abelian Cayley graphs. We improve the upper bound on the cop number of these graphs by refining the methods used previously by Hamidoune, Frankl and Bradshaw. The third chapter presents the paper concerning the cop number of 2K2-free graphs. More precisely, it is proved that 2 cops can always catch the robber on these graphs, proving a conjecture of Sivaraman and Testa. Finally, the fourth chapter is the paper written with Samuel Yvon which deals with graphs of cop number 4. We show that such graphs have at least 19 vertices. In other words, 3 cops can always catch the robber on any graph with at most 18 vertices, which answers in the negative a question by Andreae from 1986. An important part of the proof is by computer; this thesis thus has an appendix containing the code used.