L’utilisation de l’algèbre pour résoudre des problèmes de graphes a conduit au développement de trois branches : théorie spectrale des graphes, géométrie et combinatoire des groupes et études des invariants de graphes. La notion de graphe d’expansions (invariant de graphes) est relativement récente, elle a été développée afin d’étudier la robustesse des réseaux de télécommunication. Il s’avère que la construction de familles infinies de graphes expanseurs est un problème difficile. Cette thèse traite principalement de la construction de nouvelles familles de tels graphes. Les graphes expanseurs possèdent des nombreuses applications en informatique, notamment dans la construction de certains algorithmes, en théorie de la complexité, sur les marches aléatoires (random walk), etc. En informatique théorique, ils sont utilisés pour construire des familles de codes correcteurs d’erreur. Comme nous l’avons déjà vu les familles d’expanseurs sont difficiles à construire. La plupart des constructions s'appuient sur des techniques algébriques complexes, principalement en utilisant des graphes de Cayley et des produit Zig-Zag. Dans cette thèse, nous présentons une nouvelle méthode de construction de familles infinies d’expanseurs en utilisant les G-graphes. Ceux-ci sont en quelque sorte une généralisation des graphes de Cayley. Plusieurs nouvelles familles infinies d’expanseurs sont construites, notamment la première famille d’expanseurs irréguliers. / Applying algebraic and combinatorics techniques to solve graph problems leads to the birthof algebraic and combinatorial graph theory. This thesis deals mainly with a crossroads questbetween the two theories, that is, the problem of constructing infinite families of expandergraphs.From a combinatorial point of view, expander graphs are sparse graphs that have strongconnectivity properties. Expanders constructions have found extensive applications in bothpure and applied mathematics. Although expanders exist in great abundance, yet their explicitconstructions, which are very desirable for applications, are in general a hard task. Mostconstructions use deep algebraic and combinatorial approaches. Following the huge amountof research published in this direction, mainly through Cayley graphs and the Zig-Zagproduct, we choose to investigate this problem from a new perspective; namely by usingG-graphs theory and spectral hypergraph theory as well as some other techniques. G-graphsare like Cayley graphs defined from groups, but they correspond to an alternative construction.The reason that stands behind our choice is first a notable identifiable link between thesetwo classes of graphs that we prove. This relation is employed significantly to get many newresults. Another reason is the general form of G-graphs, that gives us the intuition that theymust have in many cases such as the relatively high connectivity property.The adopted methodology in this thesis leads to the identification of various approaches forconstructing an infinite family of expander graphs. The effectiveness of our techniques isillustrated by presenting new infinite expander families of Cayley and G-graphs on certaingroups. Also, since expanders stand in no single stem of graph theory, this brings us toinvestigate several closely related threads from a new angle. For instance, we obtain newresults concerning the computation of spectra of certain Cayley and G-graphs, and theconstruction of several new infinite classes of integral and Hamiltonian Cayley graphs.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

As an alternative to print media, digital media make us newly aware of the materiality of experimental poetic texts and require us to account for their media-specific differences. Although already several theoretical models have been put forward to define these differences, so far few poems have been analyzed in terms of their media-specific textual materiality. This thesis seeks to fill this gap in the applied media-specific analysis of experimental poetry. It combines traditional close reading with a media-specific approach in order to investigate the relationship between the physical characteristics and signifying strategies of four experimental poetic texts in various digital and non-digital media. It critically interrogates the specific use of the given medium in each poem, and illustrates that their respective textual materiality cannot be specified in advance based on general assumptions concerning the medium in question. A digital poem is not inherently more innovative than a non-digital poem. Rather, a poem is perceived as innovative if it resists conventional reading strategies by establishing a particularly complex, dynamic, and effectively anomalous sense of textual materiality, which necessarily only emerges from the direct interplay among text, object, and reader.

Les systèmes de preuves formelles ont connu ces dernières années des évolutions importantes. Des travaux récents, comme la preuve formelle du théorème des quatre couleurs ou celle du théorème des nombres premiers, ont montré que ces systèmes ont atteint un niveau de maturité leur permettant de s'attaquer à des problèmes mathématiques non triviaux. Malgré cela, l'utilisation des systèmes de preuves formelles en mathématique reste très limitée. Un des arguments qui est avancé pour expliquer cette situation est le manque de bibliothèques de preuves formelles. Cette thèse s'intéresse au développement de composants mathématiques pour la théorie des groupes finis. Elle entre dans le cadre du travail de formalisation du théorème de Feit-Thompson sur la classification des groupes finis. L'objectif principal dans ce travail est d'appliquer les techniques de génie logiciel pour faciliter la réutilisation et l'organisation des développements mathématiques formelles de grande échelle, comme la formalisation du théorème de Feit-Thompson. Cette thèse présente une première formalisation du théorème de Cayley-Hamilton sur les polynômes et les matrices. Elle présente aussi des développements sur la théorie des représentations des groupes finis qui est une composante nécessaire à la formalisation de la preuve du théorème de Feit-Thompson. En particulier, elle présente une formalisation de la théorie des modules sur un corps ou sur une algèbre ainsi qu'une formalisation du théorème de Maschke. Ces développements ont été faits dans le système Coq et avec l'extension SSReflect.

On considère R une relation d'équivalence borélienne standard de type I I1 sur un espace de probabilités (X, µ). On étudie une certaine propriété d'homogénéité pour un graphage fixé de la relation R : on suppose que les feuilles du graphage sont toutes isomorphes à un certain graphe transitif (connexe, infini, localement fini) Γ. Que peut-on dire sur la relation ? Dans ce cas, en considérant une action "à la Mackey", on montre qu'il existe (Z ,η) un revêtement standard probabilisé de (X, µ), une action libre (qui préserve η) sur Z du groupe G (localement compact, à base dénombrable d'ouverts) des automorphismes du graphe et un isomorphisme stable des groupoïdes mesurés associés. On fait le lien entre les propriétés du groupe G et celles de la relation de départ ; en particulier la propriété (T), (H) et la moyennabilité "passent" du graphe à la relation et réciproquement. On déduit aussi de la construction quelques couplages d'équivalence mesurée (ou plus généralement des "randembeddings") entre certains sous-groupes des automorphismes de Γ et tout groupe qui contient orbitalement la relation R. Dans un deuxième chapitre, on aborde le cas particulier de la propriété (T) relative pour les paires de groupes (ΓxZ^2, Z^2), où Γ est un sous-groupe non moyennable de SL(2,Z). Cette propriété a d'abord été prouvée par Marc Burger, puis "re-démontrée" plus "visuellement" quelques années plus tard dans le cas de SL(2,Z)xZ^2 par Y. Shalom, en utilisant des découpages du plan. On reprend cette technique dans le cas général du théorème de Burger afin d'obtenir par un algorithme des constantes de Kazhdan explicites pour toute paire (ΓxZ^2, Z^2).

In this thesis, we investigate examples of random walks on free products of cyclic groups. Free products are groups that contain words constructed by concatenation with possible simplifications[20]. Mairesse in [17] proved that the harmonic measure on the boundary of these random walks has a Markovian Multiplicative structure (this is a class of Markov measures which requires fewer parameters than the usual Markov measures for its description ), and also showed how in the case of the harmonic measure these parameters can be found from Traffic Equations. Then Mairesse and Math ́eus in [20] continued investigation of these random walks and the associated Traffic Equations. They introduced the Stationary Traffic Equations for the situation when the measure is shift-invariant in addition to being μ-invariant. In this thesis, we review these developments as well as explicitly describe several concrete examples of random walks on free products, some of which are new.

The Cayley-Hamilton Theorem is an important result in the study of linear transformations over finite dimensional vector spaces. In this thesis, we show that the Cayley-Hamilton Theorem can be extended to self-adjoint trace-class operators and to closed self-adjoint operators with trace-class resolvent over a separable Hilbert space. Applications of these results include calculating operators resolvents and finding the inverse of a frame operator.

<p>Denote by $k_t(G)$ the number of cliques of order $t$ in a graph $G$ having $n$ vertices. Let $k_t(n) = \min\{k_t(G)+k_t(\overline{G}) \}$ where $\overline{G}$ denotes the complement of $G$. Let $c_t(n) = {k_t(n)}/{\tbinom{n}{t}}$ and $c_t$ be the limit of $c_t(n)$ for $n$ going to infinity. A 1962 conjecture of Erd\H{o}s stating that $c_t = 2^{1-\tbinom{t}{2}}$ was disproved by Thomason in 1989 for all $t\geq 4$. Tighter counterexamples have been constructed by Jagger, {\v S}{\v t}ov{\' \i}{\v c}ek and Thomason in 1996, by Thomason for $t\leq 6$ in 1997, and by Franek for $t=6$ in 2002. Further tightenings $t=6,7$ and $8$ was recently obtained by Deza, Franek, and Liu.</p> <p>We investigate the computational framework used by Deza, Franek, and Liu. In particular, we present the benefits and limitations of different parallel computer memory architectures and parallel programming models. We propose a functional decomposition approach which is implemented in C++ with POSIX thread (Pthread) libraries for multi-threading. Computational benchmarking on the parallelized framework and a performance analysis including a comparison with the original computational framework are presented.</p> / Master of Science (MSc)

Dans cette thèse, nous étudions quelques problèmes géométriques liés aux domaines bornés symétriques réels. Ces espaces sont des espaces D=G/K riemanniens symétriques non compacts, obtenus à partir de domaines bornés hermitiens symétriques. Lorsque le domaine D=G/K est de type Cr ou Dr, G opère transitivement sur chaque composante connexe de l'ensemble [sigma] des tripotents maximaux du système triple de Jordan réel positif T0D. Dans le cas complexe, cet ensemble est connexe et est appelé frontière de Shilov du domaine. Dans le cas réel, [sigma] n'est en général pas connexe. Nous fixons donc une composante connexe S de [sigma]. Alors l'action de G sur S x S possède un nombre fini d'orbites et nous donnons un système explicite de représentants. Si le domaine est de type Cs ou D2s, alors parmi ces orbites, il y a celle des couples d'éléments transverses. Sous ces hypothèses, nous pouvons alors définir l'ensemble des triplets d'éléments de S transverses deux à deux, sur lequel G opère. Là encore, nous déterminons les orbites de cette action. Enfin, nous nous intéressons à un problème analytique concernant un système de Hua. Nous montrons que pour toute fonction continue [phi] sur S, la transformée de poisson f=P[sigma phi]:=[intégrale]SP(.,u)[sigma phi](u)du est solution du système de Hua Hf(x)=(2n-/r)2[sigma]([sigma]-1)f(x)Id, où P(.,.) est le noyau de Poisson sur D x S et où n- désigne la dimension de V-. / In this thesis, we are interested in geometric problems related with \emph{real bounded symmetric domains}. These spaces are Riemannian symmetric spaces $\mathcal{D}=G/K$ of noncompact type, constructed from \emph{hermitian bounded symmetric domains}. When $\mathcal{D}=G/K$ is of type $C_r$ or $D_r$, we prove that $G$ acts transitively on each connected component of the set $\Sigma$ of \emph{maximal tripotents} in the \emph{compact Jordan triple system} $T_0\mathcal{D}$. In the hermitian case, this set is connected and is called \emph{the Shilov boundary}. In the real case, $\Sigma$ is not necessarily connected, thus we choose a connected component $\mathcal{S}$ of $\Sigma$. Then the action of $G$ in $\mathcal{S}\times\mathcal{S}$ as a finite number of orbits for wich we give representative elements. If $\mathcal{D}$ is of type $C_s$ or $D_{2s}$, then the set of couples of transversal elements of $\mathcal{S}$ is a $G$-orbit in $\mathcal{S}\times\mathcal{S}$. Under these assumptions, $G$ acts on the set of transversal triples in $\mathcal{S}\times\mathcal{S}\times\mathcal{S}$ and we determine the orbits for this action. Finally, we are interested in Hua differential systems. We prove that for any continuous function $\varphi$ on $\mathcal{S}$, the Poisson transform $f=\mathcal{P}_\sigma\varphi:=\int_\mathcal{S}\mathcal{P}(\cdot,u)^\sigma\varphi(u)du$ is a solution of the Hua system $\mathcal{H}f(x)=(\frac{2n^-}{r})^2\sigma(\sigma-1)f(x)\textnormal{Id}$, where $\mathcal{P}(\cdot,\cdot)$ is the Poisson kernel on $\mathcal{D}\times\mathcal{S}$ and $n^-$ is the dimension of $V^-$.

Cette thèse se place dans le cadre du vaste domaine s'intitulant géométrie non commutative, domaine dont l'étude est motivée par l'opinion courante des mathématiciens et physiciens selon laquelle les méthodes de la géométrie non commutative peuvent être utiles pour décrire certains processus dynamiques à l'échelle de Planck. Aussi l'objectif principal de cette thèse est de généraliser quelques modèles dynamiques définis sur l'espace de Minkowski sur son q-analogue. Des tentatives d'introduire des modèles dynamiques qui seraient covariants par rapport à l'action de groupes quantiques ont été entrepris juste après la création de la théorie sur les groupes quantiques par Drinfeld. Les modèles les plus intéressants sont ceux qui sont liés au q-analogue de l'espace de Minkowski. C'est P. Kulish qui définit cette algèbre comme étant un cas particulier d'une algèbre appelée modified Reflection Equation Algebra (mREA) elle-même liée à un opérateur appelé symétrie de Hecke. Nous définissons donc certains modèles dynamiques qui sont des déformations de modèles classiques, l'espace des phases de nos modèles déformés n'est autre alors que notre espace de q-Minkowski. Nous recherchons par la suite des intégrales de mouvement de ces dynamiques, ce qui nous amène à définir des analogues de l'énergie et du vecteur de Runge-Lenz. Nous généralisons pour terminer les équations aux dérivées partielles de la théorie des champs et en particulier l'opérateur de Maxwell.