For any filter F defined on the unit disc D, F* is the filter generated by ∈-neighbourhoods of the sets of F, using hyperbolic distance. Any complex homomorphism I of β, the algebra of bounded analytic functions on D, is given by I(g) = lim g(F*) for some maximal closed filter F. The homomorphisms can be classified according to the direction of approach to the boundary of the corresponding filters. For those which are obtained by oricycle or non-tangential approach, the *-filters are in 1-1 correspondence with the homomorphisms; and into these subsets, one can analytically embed discs. On the Silov boundary of β, the above correspondence fails to be 1-1, and smaller filters are considered. / Thesis / Doctor of Philosophy (PhD)

The purpose of this thesis was to present the technique of double coset enumeration and apply it to construct finite homomorphic images of infinite semidirect products. Several important homomorphic images include the classical groups, the Projective Special Linear group and the Derived Chevalley group were constructed.

Soit Σ une surface compacte connexe orientée avec une seule composante du bord. Notons par M le groupe d'homéotopie de Σ. En considérant l'action de M sur le groupe fondamental de Σ, il est possible de définir différentes filtrations de M ainsi que des homomorphismes sur chaque terme de ces filtrations. Le but de cette thèse est double. En premier lieu, nous étudions deux filtrations de M : la " filtration de Johnson-Levine " introduite par Levine et la " filtration de Johnson alternative " introduite recemment par Habiro et Massuyeau. Les définitions de ces deux filtrations prennent en compte un corps en anses bordé par la surface. Nous nous référons à ces filtrations comme " filtrations de type Johnson " et les homomorphismes correspondants sont appelés " homomorphismes de type Johnson " par leur analogie avec la filtration de Johnson originale et les homomorphismes de Johnson usuels. Nous donnons une comparaison de la filtration de Johnson avec la filtration de Johnson-Levine au niveau du monoïde des cobordismes d'homologie de Σ. Nous donnons également une comparaison entre la filtration de Johnson alternative, la filtration Johnson-Levine et la filtration de Johnson au niveau du groupe d'homéotopie. Deuxièmement, nous étudions la relation entre les " homomorphismes de type Johnson" et l'extension fonctorielle de l'invariant perturbatif universel des variétés de dimension trois (l'invariant de Le-Murakami-Ohtsuki ou invariant LMO). Cette extension fonctorielle s'appelle le foncteur LMO et il prend ses valeurs dans une catégorie de diagrammes. Nous démontrons que les "homomorphismes de type Johnson " peuvent être lus dans la réduction arborée du foncteur LMO. En particulier, cela fournit une nouvelle grille de lecture de la réduction arborée du foncteur LMO. / Let Σ be a compact oriented surface with one boundary component and let M denote the mapping class group of Σ. By considering the action of M on the fundamental group of Σ it is possible to define different filtrations of M together with some homomorphisms on each term of the filtrations. The aim of this thesis is twofold. First, we study two filtrations of M : the « Johnson-Levine filtration » introduced by Levine and « the alternative Johsnon filtration » introduced recently by Habiro and Massuyeau. The definition of both filtrations involve a handlebody bounded by Σ. We refer to these filtrations as ≪ Johnson-type filtrations » and the corresponding homomorphisms have referred to as « Johnson-type homomorphisms » by their analogy with the original Johnson filtration and the usual Johnson homomorphisms. We provide a comparison of the Johnson filtration with the Johnson-Levine filtration at the level of the monoid of homology cobordisms of Σ. We also provide a comparison of the alternative Johnson filtration with the Johnson-Levine filtration and the Johnson filtration at the level of the mapping class group. Secondly, we study the relationship between the « Johnson-type homomorphisms » and the functorial extension of the universal perturbative invariant of 3-manifolds (the Le-Murakami-Ohtsuki invariant or LMO invariant). This functorial extension is calling the LMO functor and it takes values in a category of diagrams. We prove that the « Johnson-type homomorphisms » is in the tree reduction of the LMO functor. In particular, this provides a new reading grid of the tree reduction of the LMO functor.

A homomorphism from a graph G to a graph H is a function from V (G) to V (H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this thesis we study the complexity of various problems related to graph homomorphisms.

In this thesis we examine the computational complexity of certain digraph homomorphism problems. A homomorphism between digraphs, denoted by $f: G \to H$, is a mapping from the vertices of $G$ to the vertices of $H$ such that the arcs of $G$ are preserved. The problem of deciding whether a homomorphism to a fixed digraph $H$ exists is known as the $H$-colouring problem. We prove a generalization of a theorem due to Bang-Jensen, Hell and MacGillivray. Their theorem shows that for every semi-complete digraph $H$, $H$-colouring exhibits a dichotomy: $H$-colouring is either polynomial time solvable or it is NP-complete. We show that the class of local tournaments also exhibit a dichotomy. The NP-completeness results are found using direct NP-completeness reductions, indicator and vertex (and arc) sub-indicator constructions. The polynomial cases are handled by appealing to a result of Gutjhar, Woeginger and Welzl: the \underbar{$X$}-graft extension. We also provide a new proof of their result that follows directly from the consistency check. An unexpected result is the existence of unicyclic local tournaments with NP-complete homomorphism problems. During the last decade a new approach to studying the complexity of digraph homomorphism problems has emerged. This approach focuses attention on so-called polymorphisms as a measure of the complexity of a digraph homomorphism problem. For a digraph $H$, a polymorphism of arity $k$ is a homomorphism $f: H^k \to H$. Certain special polymorphisms are conjectured to be the key to understanding $H$-colouring problems. These polymorphisms are known as weak near unanimity functions (WNUFs). A WNUF of arity $k$ is a polymorphism $f: H^k \to H$ such that $f$ is idempotent an $f(y,x,x,\ldots,x)=f(x,y,x,\ldots,x)=f(x,x,y,\ldots,x) = \cdots = f(x,x,x,\ldots,y)$. We prove that a large class of polynomial time $H$-colouring problems all have a $\WNUF$. Furthermore we also prove some non-existence results for $\WNUF$s on certain digraphs. In proving these results, we develop a vertex (and arc) sub-indicator construction as well as an indicator construction in analogy with the ones developed by Hell and Ne{\v{s}}et{\v{r}}il. This is then used to show that all tournaments with at least two cycles do not admit a $\WNUF_k$ for $k>1$. This furnishes a new proof (in the case of tournaments) of the result by Bang-Jensen, Hell and MacGillivray referred to at the start. These results lend some support to the conjecture that $\WNUF$s are the ``right'' functions for measuring the complexity of $H$-colouring problems. We also study a related notion, namely that of an injective homomorphism. A homomorphism $f: G \to H$ is injective if the restriction of $f$ to the in-neighbours of every vertex in $G$ is an injective mapping. In order to classify the complexity of these problems we develop an indicator construction that is suited to injective homomorphism problems. For this type of digraph homomorphism problem we consider two cases: reflexive and irreflexive targets. In the case of reflexive targets we are able to classify all injective homomorphism problems as either belonging to the class of polynomial time solvable problems or as being NP-complete. Irreflexive targets pose more of a problem. The problem lies with targets of maximum in-degree equal to two. Targets with maximum in-degree one are polynomial, while targets with in-degree at least three are NP-complete. There is a transformation from (ordinary) graph homomorphism problems to injective, in-degree two, homomorphism problems (a reverse transformation also exists). This transformation provides some explanation as to the difficulty of the in-degree two case. We nonetheless classify all injective homomorphisms to irreflexive tournaments as either being a problem in P or a problem in the class of NP-complete problems. We also discuss some upper bounds on the injective oriented irreflexive (reflexive) chromatic number.

Quantum information brings together theories of physics and computer science. This synthesis challenges the basic intuitions of both fields. In this thesis, we show that adopting a unified and general language for process theories advances foundations and practical applications of quantum information. Our first set of results analyze quantum algorithms with a process theoretic structure. We contribute new constructions of the Fourier transform and Pontryagin duality in dagger symmetric monoidal categories. We then use this setting to study generalized unitary oracles and give a new quantum blackbox algorithm for the identification of group homomorphisms, solving the GROUPHOMID problem. In the remaining section, we construct a novel model of quantum blackbox algorithms in non-deterministic classical computation. Our second set of results concerns quantum foundations. We complete work begun by Coecke et al., definitively connecting the Mermin non-locality of a process theory with a simple algebraic condition on that theory's phase groups. This result allows us to offer new experimental tests for Mermin non-locality and new protocols for quantum secret sharing. In our final chapter, we exploit the shared process theoretic structure of quantum information and distributional compositional linguistics. We propose a quantum algorithm adapted from Weibe et al. to classify sentences by meaning. The clarity of the process theoretic setting allows us to recover a speedup that is lost in the naive application of the algorithm. The main mathematical tools used in this thesis are group theory (esp. Fourier theory on finite groups), monoidal category theory, and categorical algebra.

Let <i>R</i> be a commutative ring, <i>I</i> be an ideal in <i>R</i> and let <i>M</i> be a <i>R/ I</i> -module. In this thesis we construct a <i>R/ I</i> -projective resolution of <i>M</i> using given <i>R</i>-projective resolutions of <i>M</i> and <i>I</i>. As immediate consequences of our construction we give descriptions of the canonical maps Ext_R/I<i>(M,N)</i> -> Ext_R<i>(M,N)</i> and Tor^R_N<i>(M, N)</i> -> Tor^R/I_n<i>(M, N)</i> for a <i>R/I</i> module <i>N</i> and we give a new proof of a theorem of Gulliksen [6] which states that if <i>I</i> is generated by a regular sequence of length r then ∐∞_n=o Tor^R/I_n <i>(M, N)</i> is a graded module over the polynomial ring </i>R/ I</i> [X₁. .. X_r] with deg X_i = -2, 1 ≤ i ≤ r. If <i>I</i> is generated by a regular element and if the <i>R</i>-projective dimension of <i>M</i> is finite, we show that <i>M</i> has a <i>R/ I</i>-projective resolution which is eventually periodic of period two. This generalizes a result of Eisenbud [3]. In the case when <i>R</i> = (<i>R</i>, m) is a Noetherian local ring and <i>M</i> is a finitely generated <i>R/ I</i> -module, we discuss the minimality of the constructed resolution. If it is minimal we call (<i>M, I</i>) a Golod pair over <i>R</i>. We give a direct proof of a theorem of Levin [10] which states thdt if (<i>M,I</i>) is a Golod pair over <i>R</i> then (Ωⁿ_R/IR/I(M),I) is a Golod pair over <i>R</i> where Ωⁿ_R/IR/I(M) is the nth syzygy of the constructed <i>R/ I</i> -projective resolution of <i>M</i>. We show that the converse of the last theorem is not true and if (Ω¹_R/IR/I(M),I) is a Golod pair over <i>R</i> then we give a necessary and sufficient condition for (<i>M, I</i>) to be a Golod pair over <i>R</i>. Finally we prove that if (<i>M, I</i>) is a Golod pair over <i>R</i> and if a ∈ <i>I</i> - m<i>I</i> is a regular element in </i>R</i> then (<i>M</i>, (a)) and (1/(a), (a)) are Golod pairs over <i>R</i> and (<i>M,I</i>/(a)) is a Golod pair over <i>R</i>/(a). As a corrolary of this result we show that if the natural map π : <i>R</i> → <i>R/1</i> is a Golod homomorphism ( this means (<i>R</i>/m, <i>I</i>) is a Golod pair over <i>R</i> ,Levin [8]), then the natural maps π₁ : <i>R</i> → <i>R</i>/(a) and π₂ : <i>R</i>/(a) → <i>R/1</i> are Golod homomorphisms. / Ph. D.

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes. / An oriented graph is a directed graph with no cycle of length at most two. A homomorphism of an oriented graph to another oriented graph is an arc preserving vertex mapping. To push a vertex is to switch the direction of the arcs incident to it. An orientable graph is an equivalence class of oriented graph with respect to the push operation. An orientable graph [−→G] admits a homomorphism to an orientable graph [−→H] if an element of [−→G] admits a homomorphism to an element of [−→H]. A signified graph (G, Σ) is a graph whose edges are assigned either a positive sign or a negative sign, while Σ denotes the set of edges with negative signs assigned to them. A homomorphism of a signified graph to another signified graph is a vertex mapping such that the image of a positive edge is a positive edge and the image of a negative edge is a negative edge. A signed graph [G, Σ] admits a homomorphism to a signed graph [H, Λ] if an element of [G, Σ] admits a homomorphism to an element of [H, Λ]. The oriented chromatic number of an oriented graph −→G is the minimum order of an oriented graph −→H such that −→G admits a homomorphism to −→H. A set R of vertices of an oriented graph −→G is an oriented relative clique if no two vertices of R can have the same image under any homomorphism. The oriented relative clique number of an oriented graph −→G is the maximum order of an oriented relative clique of −→G. An oriented clique or an oclique is an oriented graph whose oriented chromatic number is equal to its order. The oriented absolute clique number of an oriented graph −→G is the maximum order of an oclique contained in −→G as a subgraph. The chromatic number, the relative chromatic number and the absolute chromatic number for orientable graphs, signified graphs and signed graphs are defined similarly. In this thesis we study the chromatic number, the relative clique number and the absolute clique number of the above mentioned four types of graphs. We specifically study these three parameters for the family of outerplanar graphs, of outerplanar graphs with given girth, of planar graphs and of planar graphs with given girth. We also try to investigate the relation between the four types of graphs and prove some results regarding that. In this thesis, we provide tight bounds for the absolute clique number of these families in all these four settings. We provide improved bounds for relative clique numbers for the same. For some of the cases we manage to provide improved bounds for the chromatic number as well. One of the most difficult results that we prove here is that the oriented absolute clique number of the family of planar graphs is at most 15. This result settles a conjecture made by Klostermeyer and MacGillivray in 2003. Using the same technique we manage to prove similar results for orientable planar graphs and signified planar graphs. We also prove that the signed chromatic number of triangle-free planar graphs is at most 25 using the discharging method. This also implies that the signified chromatic number of trianglefree planar graphs is at most 50 improving the previous upper bound. We also study the 2-dipath and oriented L(p, q)-labeling (labeling with a condition for distance one and two) for several families of planar graphs. It was not known if the categorical product of orientable graphs and of signed graphs exists. We prove both the existence and also provide formulas to construct them. Finally, we propose some conjectures and mention some future directions of works to conclude the thesis.

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes.

Homomorfismos de grafos são funções do conjunto de vértices de um grafo no conjunto de vértices de outro grafo que preservam adjacências. O estudo de homomorfismos de grafos é bastante abrangente, existindo muitas linhas de pesquisa sobre esse tópico. Nesta dissertação, apresentaremos resultados sobre homomorfismos de grafos relacionados a pseudo-aleatoriedade, convergência de seqüência de grafos e matrizes de conexão de invariantes de grafos. Esta linha tem se mostrado muito rica, não apenas pelos seus resultados, como também pelas técnicas utilizadas nas demonstrações. Em especial, destacamos a diversidade das ferramentas matemáticas que são usadas, que incluem resultados clássicos de álgebra, probabilidade e análise. / Graph homomorphisms are functions from the vertex set of a graph to the vertex set of another graph that preserve adjacencies. The study of graph homomorphisms is very broad, and there are several lines of research about this topic. In this dissertation, we present results about graph homomorphisms related to convergence of graph sequences and connection matrices of graph parameters. This line of research has been proved to be very rich, not only for its results, but also for the proof techniques. In particular, we highlight the diversity of mathematical tools used, including classical results from Algebra, Probability and Analysis.