No description available.

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.

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.

We study the Erdős- Sòs conjecture that states that ever graph of average degree greater than k-1 contains every tree of order k+1. While the conjecture was studied for some graphs, it still remains open and of interest after more than 40 years. We study the conjecture for graphs with no K2,s where, s ≥ 2 and k > 12(s-1). We use the fact that as G contains no K2,s, any two distinct vertices in G have at most s-1 neighbors in common in proving the results. We have answered in the affirmative that the Erdős- Sòs conjecture is true for graphs defined above, thus adding to the list of graphs for which the conjecture is true. We also study the Cayley Isomorphism Problem that states that for which finite groups H is it true that any two Cayley graphs of H are isomorphic if and only if they are isomorphic by a group automorphism of H ? (H is a CI-group with respect to graphs.) Determining whether or not a group is a CI-group with respect to graphs has received considerable attention over the last 40 or so years. In particular, we study the problem for (pq,r)-metacirculant color digraphs where p < q < r and pq/| α|. We use the fact that Γ is a CI-color digraph of H if and only if given a permutation γ ∈ SH such that γ-1HLγ ≤ Aut(Γ), HL and γ-1HLγ are conjugate in Aut(Γ). We consider the Cayley isomorphism problem for a nonabelian group of order pqr, where p, q, r are distinct primes such that pq/(r- 1). We show that the results are true, not only for Cayley graphs but for some related classes of non Cayley vertex transitive graphs, thus solving the problem for that case.

<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 quatre problèmes de théorie des graphes. En particulier,Nous étudions le problème du cycle hamiltonien dans les line graphes, et aussi nous prouvons l’existence de cycles hamiltoniens dans certains sous graphes couvrants d’un line graphe. Notre résultat principal est: Si L(G) est hamiltonien, alors SL(G) est hamiltonien. Grâce à ce résultat nous proposons une conjecture équivalente à des conjectures célèbres. Et nous obtenons deux résultats sur les cycles hamiltoniens disjoints dans les line graphes.Nous considérons alors la bipancyclicité résistante aux pannes des graphes de Cayley engendrés par transposition d’arbres. Nous prouvons que de tels graphes de Cayley excepté le “star graph” ont une bipancyclicité (n − 3)-arête résistante aux pannes.Ensuite nous introduisons la coloration des arcs d’un digraphe sommet distinguant. Nous étudions la relation entre cette notion et la coloration d’arêtes sommet distinguant dans les graphes non orientés. Nous obtenons quelques résultats sur le nombre arc chromatique des graphes orientés (semi-)sommet-distinguant et proposons une conjecture sur ce paramètre. Pour vérifier cette conjecture nous étudions la coloration des arcs d’un digraphe sommet distinguant des graphes orientés réguliers.Finalement nous introduisons la coloration acyclique des arcs d’un graphe orienté. Nous calculons le nombre chromatique acyclique des arcs de quelques familles de graphes orientés et proposons une conjecture sur ce paramètre. Nous considérons les graphes orientés de grande maille et utilisons le Lemme Local de Lovász; d’autre part nous considérons les graphes orientés réguliers aléatoires. Nous prouvons que ces deux classes de graphes vérifient la conjecture. / In this thesis, we study four problems in graph theory, the Hamiltonian cycle problem in line graphs, the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees, the vertex-distinguishing arc colorings in digraph- s and the acyclic arc coloring in digraphs. The first two problems are the classic problem on the cycles in graphs. And the other two arc coloring problems are related to the modern graph theory, in which we use some probabilistic methods. In particular,We first study the Hamiltonian cycle problem in line graphs and find the Hamiltonian cycles in some spanning subgraphs of line graphs SL(G). We prove that: if L(G) is Hamiltonian, then SL(G) is Hamiltonian. Due to this, we propose a conjecture, which is equivalent to some well-known conjectures. And we get two results about the edge-disjoint Hamiltonian cycles in line graphs.Then, we consider the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees. And we prove that the Cayley graph generated by transposition tree is (n − 3)-edge-fault-tolerant bipancyclic if it is not a star graph.Later, we introduce the vertex-distinguishing arc coloring in digraphs. We study the relationship between the vertex-distinguishing edge coloring in undirected graphs and the vertex-distinguishing arc coloring in digraphs. And we get some results on the (semi-) vertex-distinguishing arc chromatic number for digraphs and also propose a conjecture about it. To verify the conjecture we study the vertex-distinguishing arc coloring for regular digraphs.Finally, we introduce the acyclic arc coloring in digraphs. We calculate the acyclic arc chromatic number for some digraph families and propose a conjecture on the acyclic arc chromatic number. Then we consider the digraphs with high girth by using the Lovász Local Lemma and we also consider the random regular digraphs. And the results of the digraphs with high girth and the random regular digraphs verify the conjecture.

Dans la premier partie de cette thèse, nous étudions la structure des sous-groupes approximatifs dans les groupes metabéliens (groupes résolubles de classe de résolubilité 2) et montrons que si A est un tel sous-groupe K approximatif, il est K^⁰(r) contrôlée (au sens du Tao) par un groupe nilpotent où $ r désigne le rang de $ G=Fit (G) et Fit (G) $ est le sous-groupe de fitting de G. La deuxième partie est consacrée à l'étude de la croissance des ensembles dans GLn(Fq) où Fq est un corps fini. Nous montrons une borne sur le diamètre (par rapport à n'importe quel système des générateurs) pour tous sous-groupes simples finis de ce groupe. Si G est un groupe fini simple de type Lie de rang n, et son corps de base est de taille borné, le diamètre du graphe du Cayley Gamma (G;S) serait borné par exp (O (n (log n) ^ 3)) . Si la taille du corps fini Fq n'est pas borné, notre méthode donne une borne de q ^ {O (n ( log nq) ^ 3) pour le diamètre.Dans la troisième partie nous nous sommes intéressés à la croissance des ensembles dans les boucles de Moufang commutatifs. Ceux-ci sont les boucles commutatifs respectant les identités de Moufang mais sans être (nécessairement) associatifs. Nous montrons que, si les tailles des ensembles des associateurs sont bornées alors la croissance des sous-structures approximatifs dans ces boucles est similaire à celle des groupes ordinaires. De cette façon dans le cadre des boucles de moufang commutatifs finiment engendré on a un théorème de structure pour ses sous-boucles approximatifs.Mots-clefs -sous-groupes approximatifs, groupes résolubles, diamètres des groupes, boucles de moufang commutatifs. / In the first part of this thesis, we study the structure of approximate subgroups inside metabelian groups (solvable groups of derived length 2) and show that if A is such a K-approximate subgroup, then it is K^(O(r)) controlled (in the sense of Tao) by a nilpotent group where r denotes the rank of G=Fit(G) and Fit(G) is the fitting subgroup of G.The second part is devoted to the study of growth of sets inside GLn(Fq) , where we show a bound on the diameter (with respect to any set of generators) for all finite simple subgroups of this group. What we have is - if G is a finite simple group of Lie type with rank n, and its base field has bounded size, then the diameter of the Cayley graph C(G; S) would be bounded by exp(O(n(logn)^3)). If the size of the base field Fq is not bounded then our method gives a bound of q^(O(n(log nq)3)) for the diameter.In the third part we are interested in the growth of sets inside commutative Moufang loops which are commutative loops respecting the moufang identities but without (necessarily)being associative. For them we show that if the sizes of the associator sets are bounded then the growth of approximate substructures inside these loops is similar to those in ordinary groups. In this way for the subclass of finitely generated commutative moufang loops we have a classification theorem of its approximate subloops.

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$.