To see the other types of publications on this topic, follow the link: Automorphisme des graphes.
Dissertations / Theses on the topic 'Automorphisme des graphes'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 43 dissertations / theses for your research on the topic 'Automorphisme des graphes.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Carboni, Lucrezia. "Graphes pour l’exploration des réseaux de neurones artificiels et de la connectivité cérébrale humaine." Electronic Thesis or Diss., Université Grenoble Alpes, 2023. http://www.theses.fr/2023GRALM060.
Full textAbstract:
L'objectif principal de cette thèse est d'explorer la connectivité cérébrale et celle des réseaux de neurones artificiels d'un point de vue de leur connectivité. Un modèle par graphes pour l'analyse de la connectivité structurelle et fonctionnelle a été largement étudié dans le contexte du cerveau humain mais, un tel cadre d'analyse manque encore pour l'analyse des systèmes artificiels. Avec l'objectif d'intégrer l'analyse de la connectivité dans les système artificiels, cette recherche se concentre sur deux axes principaux. Dans le premier axe, l'objectif principal est de déterminer une caractérisation de la signature saine de la connectivité fonctionnelle de repos du cerveau humain. Pour atteindre cet objectif, une nouvelle méthode est proposée, intégrant des statistiques de graphe traditionnelles et des outils de réduction de réseau, pour déterminer des modèles de connectivité sains. Ainsi, nous construisons une comparaison en paires de graphes et un classifieur pour identifier les états pathologiques et identifier les régions cérébrales perturbées par une pathologie. De plus, la généralisation et la robustesse de la méthode proposée ont été étudiées sur plusieurs bases de données et variations de la qualité des données. Le deuxième axe de recherche explore les avantages de l'intégration des études de la connectivité inspirée du cerveau aux réseaux de neurones artificiels (ANNs) dans la perspective du développement de systèmes artificiels plus robustes. Un problème majeur de robustesse dans les modèles d'ANN est représenté par l'oubli catastrophique qui apparaît lorsque le réseau oublie dramatiquement les tâches précédemment apprises lors de l'adaptation à de nouvelles tâches. Notre travail démontre que la modélisation par graphes offre un cadre simple et élégant pour étudier les ANNs, comparer différentes stratégies d'apprentissage et détecter des comportements nuisibles tels que l'oubli catastrophique. De plus, nous soulignons le potentiel d'une adaptation à de nouvelles tâches en contrôlant les graphes afin d'atténuer efficacement l'oubli catastrophique et jetant ainsi les bases de futures recherches et explorations dans ce domaineThe main objective of this thesis is to explore brain and artificial neural network connectivity from agraph-based perspective. While structural and functional connectivity analysis has been extensivelystudied in the context of the human brain, there is a lack of a similar analysis framework in artificialsystems.To address this gap, this research focuses on two main axes.In the first axis, the main objective is to determine a healthy signature characterization of the humanbrain resting state functional connectivity. To achieve this objective, a novel framework is proposed,integrating traditional graph statistics and network reduction tools, to determine healthy connectivitypatterns. Hence, we build a graph pair-wise comparison and a classifier to identify pathological statesand rank associated perturbed brain regions. Additionally, the generalization and robustness of theproposed framework were investigated across multiple datasets and variations in data quality.The second research axis explores the benefits of brain-inspired connectivity exploration of artificialneural networks (ANNs) in the future perspective of more robust artificial systems development. Amajor robustness issue in ANN models is represented by catastrophic forgetting when the networkdramatically forgets previously learned tasks when adapting to new ones. Our work demonstrates thatgraph modeling offers a simple and elegant framework for investigating ANNs, comparing differentlearning strategies, and detecting deleterious behaviors such as catastrophic forgetting.Moreover, we explore the potential of leveraging graph-based insights to effectively mitigatecatastrophic forgetting, laying a foundation for future research and explorations in this area
2
Aurand, Eric William. "Infinite Planar Graphs." Thesis, University of North Texas, 2000. https://digital.library.unt.edu/ark:/67531/metadc2545/.
Full textAbstract:
How many equivalence classes of geodesic rays does a graph contain? How many bounded automorphisms does a planar graph have? Neimayer and Watkins studied these two questions and answered them for a certain class of graphs.
Using the concept of excess of a vertex, the class of graphs that Neimayer and Watkins studied are extended to include graphs with positive excess at each vertex. The results of this paper show that there are an uncountable number of geodesic fibers for graphs in this extended class and that for any graph in this extended class the only bounded automorphism is the identity automorphism.
3
Derakhshan, Parisa. "Automorphisms generating disjoint Hamilton cycles in star graphs." Thesis, Loughborough University, 2015. https://dspace.lboro.ac.uk/2134/16779.
Full textAbstract:
In the first part of the thesis we define an automorphism φn for each star graph Stn of degree n-1, which yields permutations of labels for the edges of Stn taken from the set of integers {1,..., [n/2c]}. By decomposing these permutations into permutation cycles, we are able to identify edge-disjoint Hamilton cycles that are automorphic images of a known two-labelled Hamilton cycle H1 2(n) in Stn. The search for edge-disjoint Hamilton cycles in star graphs is important for the design of interconnection network topologies in computer science. All our results improve on the known bounds for numbers of any kind of edge-disjoint Hamilton cycles in star graphs.
4
Schmidt, Simon [Verfasser]. "Quantum automorphism groups of finite graphs / Simon Schmidt." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2020. http://d-nb.info/1216104816/34.
Full text
5
Crinion, Tim. "Chamber graphs of some geometries related to the Petersen graph." Thesis, University of Manchester, 2013. https://www.research.manchester.ac.uk/portal/en/theses/chamber-graphs-of-some-geometries-related-to-the-petersen-graph(f481f0af-7c39-4728-8928-571495d1217a).html.
Full textAbstract:
In this thesis we study the chamber graphs of the geometries ΓpA2nΓ1q, Γp3A7q, ΓpL2p11qq and ΓpL2p25qq which are related to the Petersen graph [4, 13]. In Chapter 2 we look at the chamber graph of ΓpA2nΓ1q and see what minimal paths between chambers look like. Chapter 3 finds and proves the diameter of these chamber graphs and we see what two chambers might look like if they are as far apart as possible. We discover the full automorphism group of the chamber graph. Chapters 4, 5 and 6 focus on the chamber graphs of ΓpL2p11qq,ΓpL2p25qq and Γp3A7q respectively. We ask questions such as what two chambers look like if they are as far apart as possible, and we find the automorphism groups of the chamber graphs.
6
Möller, Rögnvaldur G. "Groups acting on graphs." Thesis, University of Oxford, 1991. http://ora.ox.ac.uk/objects/uuid:2dacfc67-56c4-4541-b52e-10199a13dcc2.
Full textAbstract:
In the first part of this thesis we investigate the automorphism groups of regular trees. In the second part we look at the action of the automorphism group of a locally finite graph on the ends of the graph. The two part are not directly related but trees play a fundamental role in both parts. Let Tn be the regular tree of valency n. Put G := Aut(Tn) and let G0 be the subgroup of G that is generated by the stabilisers of points. The main results of the first part are : Theorem 4.1 Suppose 3 ≤ n < N0 and α ϵ Tn. Then Gα (the stabiliser of α in G) contains 22N0 subgroups of index less than 22N0. Theorem 4.2 Suppose 3 ≤ n < N0 and H ≤ G with G : H |< 2N0. Then H = G or H = G0 or H fixes a point or H stabilises an edge. Theorem 4.3 Let n = N0 and H ≤ G with | G : H |< 2N0. Then H = G or H = G0 or there is a finite subtree ϕ of Tn such that G(ϕ) ≤ H ≤ G{ϕ}. These are proved by finding a concrete description of the stabilisers of points in G, using wreath products, and also by making use of methods and results of Dixon, Neumann and Thomas [Bull. Lond. Math. Soc. 18, 580-586]. It is also shown how one is able to get short proofs of three earlier results about the automorphism groups of regular trees by using the methods used to prove these theorems. In their book Groups acting on graphs, Warren Dicks and M. J. Dunwoody [Cambridge University Press, 1989] developed a powerful technique to construct trees from graphs. An end of a graph is an equivalence class of half-lines in the graph, with two half-lines, L1 and L2, being equivalent if and only if we can find the third half-line that contains infinitely many vertices of both L1 and L2. In the second part we point out how one can, by using this technique, reduce questions about ends of graphs to questions about trees. This allows us both to prove several new results and also to give simple proofs of some known results concerning fixed points of group actions on the ends of a locally finite graph (see Chapter 10). An example of a new result is the classification of locally finite graphs with infinitely many ends, whose automorphism group acts transitively on the set of ends (Theorem 11.1).
7
Hahn, Gena. "Sur des graphes finis et infinis." Paris 11, 1986. http://www.theses.fr/1986PA112166.
Full textAbstract:
Ce travail porte sur l'étude des relations entre la microstructure et paramètres d'élaboration des rubans de l'alliage binaire Al-8% Fe. Les paramètres étudiés sont entre autres : - pression d'éjection et vitesse du substrat, -nature et rugosité du substrat,- température d'éjection. La microstructure des rubans élaborés en jet libre est classée en trois familles : structure de solidification micro-cellulaire, dendritique et équiaxe contenant des précipités. Nous montrons qu'il est possible d'éviter la formation de la structure dendritique grossière correspondant aux conditions de refroidissement les plus lentes : toutefois, les caractéristiques morphologiques des rubans ainsi qu'un bon contact thermique entre celui-ci et le substrat sont à rechercher. Nous en déduisons que la mouillabilité de l'alliage liquide sur le substrat est le critère le plus important et l'influence des paramètres d'élaboration est discuté en termes de distance de collage des rubans sur le substrat. L'élaboration de rubans en jet confiné est également étudiée et leur microstructure est comparée à celle de leurs homologues élaborés en jet libreThis work describes the dependence of microstructural features on rapid solidification processing for the melt spun Al-8% Fe alloy. The inspected parameters are: - ejection pressure and substrate velocity, - nature and rugosity of susbtrate, - ejection temperature. The resultant microstructures of the chill block melt spun ribbons is classified into three families: micro-cellular and dendritic structures, and equiaxed grains containing precipitates. It is possible to avoid the occurrence of the coarse dendritic structure corresponding to the slowest cooling conditions however, uniformity of the ribbon morphologic characteristics and good thermal contact between the ribbon and the weel have to be insured. So, improvement of wetting is the major point. The influence of process parameters on wetting is discussed and particular attention is paid to the sticking distance between the ribbon and the substrate. The planar flow casting method has been developed and microstructural results are compared to those given by the C. B. M. S. Technique
8
Bougard, Nicolas. "Regular graphs and convex polyhedra with prescribed numbers of orbits." Doctoral thesis, Universite Libre de Bruxelles, 2007. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210688.
Full textAbstract:
Etant donné trois entiers k, s et a, nous prouvons dans le premier chapitre qu'il existe un graphe k-régulier fini (resp. un graphe k-régulier connexe fini) dont le groupe d'automorphismes a exactement s orbites sur l'ensemble des sommets et a orbites sur l'ensemble des arêtes si et seulement si(s,a)=(1,0) si k=0,
(s,a)=(1,1) si k=1,
s=a>0 si k=2,
0< s <= 2a <= 2ks si k>2.
(resp.
(s,a)=(1,0) si k=0,
(s,a)=(1,1) si k=1 ou 2,
s-1<=a<=(k-1)s+1 et s,a>0 si k>2.)
Nous étudions les polyèdres convexes de R³ dans le second chapitre. Pour tout polyèdre convexe P, nous notons Isom(P) l'ensemble des isométries de R³ laissant P invariant. Si G est un sous-groupe de Isom(P), le f_G-vecteur de P est le triple d'entiers (s,a,f) tel que G ait exactement s orbites sur l'ensemble sommets de P, a orbites sur l'ensemble des arêtes de P et f orbites sur l'ensemble des faces de P. Remarquons que (s,a,f) est le f_{id}-vecteur (appelé f-vecteur dans la littérature) d'un polyèdre si ce dernier possède exactement s sommets, a arêtes et f faces. Nous généralisons un théorème de Steinitz décrivant tous les f-vecteurs possibles. Pour tout groupe fini G d'isométries de R³, nous déterminons l'ensemble des triples (s,a,f) pour lesquels il existe un polyèdre convexe ayant (s,a,f) comme f_G-vecteur. Ces résultats nous permettent de caractériser les triples (s,a,f) pour lesquels il existe un polyèdre convexe tel que Isom(P) a s orbites sur l'ensemble des sommets, a orbites sur l'ensemble des arêtes et f orbites sur l'ensemble des faces.
La structure d'incidence I(P) associée à un polyèdre P consiste en la donnée de l'ensemble des sommets de P, l'ensemble des arêtes de P, l'ensemble des faces de P et de l'inclusion entre ces différents éléments (la notion de distance ne se trouve pas dans I(P)). Nous déterminons également l'ensemble des triples d'entiers (s,a,f) pour lesquels il existe une structure d'incidence I(P) associée à un polyèdre P dont le groupe d'automorphismes a exactement s orbites de sommets, a orbites d'arêtes et f orbites de sommets.
Doctorat en sciences, Spécialisation mathématiques
info:eu-repo/semantics/nonPublished
9
Adatorwovor, Dayana. "H - Removable Sequences of Graphs." OpenSIUC, 2014. https://opensiuc.lib.siu.edu/dissertations/791.
Full textAbstract:
H-removable sequences, for arbitrary H, under &Lambda^* construction are presented here. In the first part we investigate Neighborhood Distinct (ND) graphs and ask some natural questions concerning disconnected H and H complement. In the second part, we introduce property * and investigate graphs that satisfy property *. Consequently we find $H$-removable sequences for all graphs H with up to 6 vertices except for G60. G60 is the only graph with up to 6 vertices for which neither it nor its complement satisfies property *. The last part of our work focuses on good and bad copies of arbitrary graphs $H$ and how to interchange from one to the other. The number of ways to count all possible copies of H in H_{pn} ^ &Lambda^* is also presented via examples.
10
Allie, Imran. "Meta-Cayley Graphs on Dihedral Groups." University of the Western Cape, 2017. http://hdl.handle.net/11394/5440.
Full textAbstract:
>Magister Scientiae - MScThe pursuit of graphs which are vertex-transitive and non-Cayley on groups has been ongoing for some time. There has long been evidence to suggest that such graphs are a very rarety in occurrence. Much success has been had in this regard with various approaches being used. The aim of this thesis is to find such a class of graphs. We will take an algebraic approach. We will define Cayley graphs on loops, these loops necessarily not being groups. Specifically, we will define meta-Cayley graphs, which are vertex-transitive by construction. The loops in question are defined as the semi-direct product of groups, one of the groups being Z₂ consistently, the other being in the class of dihedral groups. In order to prove non-Cayleyness on groups, we will need to fully determine the automorphism groups of these graphs. Determining the automorphism groups is at the crux of the matter. Once these groups are determined, we may then apply Sabidussi's theorem. The theorem states that a graph is Cayley on groups if and only if its automorphism group contains a subgroup which acts regularly on its vertex set.
Chemicals Industries Education and Training Authority (CHIETA)
11
Piggott, Adam. "The topology of finite graphs, recognition and the growth of free-group automorphisms." Thesis, University of Oxford, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.409180.
Full text
12
Vodah, Sunday. "On the primarity of some block intersection graphs." University of the Western Cape, 2018. http://hdl.handle.net/11394/6735.
Full textAbstract:
Philosophiae Doctor - PhDA tactical con guration consists of a nite set V of points, a nite set B of blocks and an incidence relation between them, so that all blocks are incident with the same number k points, and all points are incident with the same number r of blocks (See [14] for example ). If v := jV j and b := jBj; then v; k; b; r are known as the parameters of the con guration. Counting incident point-block pairs, one sees that vr = bk: In this thesis, we generalize tactical con gurations on Steiner triple systems obtained from projective geometry. Our objects are subgeometries as blocks. These subgeometries are collected into systems and we study them as designs and graphs. Considered recursively is a further tactical con guration on some of the designs obtained and in what follows, we obtain similar structures as the Steiner triple systems from projective geometry. We also study these subgeometries as factorizations and examine the automorphism group of the new structures. These tactical con gurations at rst sight do not form interesting structures. However, as will be shown, they o er some level of intriguing symmetries. It will be shown that they inherit the automorphism group of the parent geometry.
13
McPhee, Jillian Dawn. "Endomorphisms of Fraïssé limits and automorphism groups of algebraically closed relational structures." Thesis, University of St Andrews, 2012. http://hdl.handle.net/10023/3358.
Full textAbstract:
Let Ω be the Fraïssé limit of a class of relational structures. We seek to answer the following semigroup theoretic question about Ω. What are the group H-classes, i.e. the maximal subgroups, of End(Ω)? Fraïssé limits for which we answer this question include the random graph R, the random directed graph D, the random tournament T, the random bipartite graph B, Henson's graphs G[subscript n] (for n greater or equal to 3) and the total order Q. The maximal subgroups of End(Ω) are closely connected to the automorphism groups of the relational structures induced by the images of idempotents from End(Ω). It has been shown that the relational structure induced by the image of an idempotent from End(Ω) is algebraically closed. Accordingly, we investigate which groups can be realised as the automorphism group of an algebraically closed relational structure in order to determine the maximal subgroups of End(Ω) in each case. In particular, we show that if Γ is a countable graph and Ω = R,D,B, then there exist 2[superscript aleph-naught] maximal subgroups of End(Ω) which are isomorphic to Aut(Γ). Additionally, we provide a complete description of the subsets of Q which are the image of an idempotent from End(Q). We call these subsets retracts of Q and show that if Ω is a total order and f is an embedding of Ω into Q such that im f is a retract of Q, then there exist 2[superscript aleph-naught] maximal subgroups of End(Q) isomorphic to Aut(Ω). We also show that any countable maximal subgroup of End(Q) must be isomorphic to Zⁿ for some natural number n. As a consequence of the methods developed, we are also able to show that when Ω = R,D,B,Q there exist 2[superscript aleph-naught] regular D-classes of End(Ω) and when Ω = R,D,B there exist 2[superscript aleph-naught] J-classes of End(Ω). Additionally we show that if Ω = R,D then all regular D-classes contain 2[superscript aleph-naught] group H-classes. On the other hand, we show that when Ω = B,Q there exist regular D-classes which contain countably many group H-classes.
14
Kumwenda, Khumbo. "Codes, graphs and designs related to iterated line graphs of complete graphs." Thesis, University of the Western Cape, 2011. http://etd.uwc.ac.za/index.php?module=etd&action=viewtitle&id=gen8Srv25Nme4_1742_1320645699.
Full textAbstract:
In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1, 2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+1(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn, and neighbourhood designs of their line graphs, L1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of L1(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs ôn that are embeddable into the strong product L1(Kn) â K2, of triangular graphs and K2, a class which at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, ôn also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of ôn and Hn and determine their parameters.
15
Wagner, Andrew. "On the Existence of a Second Hamilton Cycle in Hamiltonian Graphs With Symmetry." Thèse, Université d'Ottawa / University of Ottawa, 2013. http://hdl.handle.net/10393/30290.
Full textAbstract:
In 1975, Sheehan conjectured that every simple 4-regular hamiltonian graph has a second Hamilton cycle. If Sheehan's Conjecture holds, then the result can be extended to all simple d-regular hamiltonian graphs with d at least 3.
First, we survey some previous results which verify the existence of a second Hamilton cycle if d is large enough. We will then demonstrate some techniques for finding a second Hamilton cycle that will be used throughout this paper. Finally, we use these techniques and show that for certain 4-regular Hamiltonian graphs whose automorphism group is large enough, a second Hamilton cycle exists.
16
Gibbins, Aliska L. "Automorphism Groups of Buildings Constructed Via Covering Spaces." The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1373976456.
Full text
17
Ye, Kaidi. "Automorphismes géométriques des groupes libres : croissance polynomiale et algorithmes." Thesis, Aix-Marseille, 2016. http://www.theses.fr/2016AIXM4713/document.
Full textAbstract:
Un automorphisme (extérieur) $phi $ d'un groupe libre $F_n$ de rang fini $ngeq 2$ est dit géométrique s'il est induit par un homéomorphisme d'une surface. La question à laquelle nous intéressons est la suivante: Quels sont les automorphismes de $F_n$ qui sont géométriques?Nous donnons une réponse algorithmique pour la classe des automorphismes à croissance polynomiale (en s'autorisant à remplacer un automorphisme par une puissance).Pour cela, nous sommes amenés à étudier les automorphismes de graphes de groupes. En particulier, nous introduisons deux transformations élémentaires d'automorphismes de graphes de groupes: les quotients et les éclatements.Pour le cas particulier où l'automorphisme est un twist de Dehn partiel, on obtient un critère pour décider quand un tel twist de Dehn partiel est un véritable twist de Dehn.En appliquant le critère à plusieurs reprises sur un twist de Dehn cumulé, nous montrons que soit on peut ＂déplier＂ ce twist de Dehn cumulé jusqu'à obtenir un twist de Dehn ordinaire, soit que $phi$ est à croissance au moins quadratique (et par conséquent, n'est pas géométrique).Cela montre, au passage, que tout automorphisme du groupe libre à croissance linéaire admet une puissance qui est un twist de Dehn. Ce fait est connu des experts, et souvent utilisé, bien qu'il n'en existait pas de preuve formelle dans la littérature (à la connaissance de l'auteur).Pour conclure, on applique l'algorithme de Cohen-Lustig pour le transformer en twist de Dehn efficace, puis on applique l'algorithme Whitehead et des théorèmes classiques de Nielsen-Baer et Zieschang pour construire un modèle géométrique ou pour montrer qu'il n'est pas géométriqueAn automorphism $phi$ of a free group $F_n$ of finite rank $n geq 2$ is said to be geometric it is induced by a homeomorphism on a surface.In this thesis we concern ourselves with answering the question:Which precisely are the outer automorphisms of $F_n$ that are geometric?to which we give an algorithmical decision for the case of polynomially growing outer automorphisms, up to raising to certain positive power.In order to realize this algorithm, we establish the technique of quotient and blow-up automorphisms of graph-of-groups, which when apply for the special case of partial Dehn twist enables us to develop a criterion to decide whether the induced outer automorphism is an actual Dehn twist.Applying the criterion repeatedly on the special topological representative deriving from relative train track map, we are now able to either “unfold” this iterated relative Dehn twist representative level by level until eventually obtain an ordinary Dehn twist representative or show that $hat{phi}$ has at least quadratic growth hence is not geometric.As a side result, we also proved that every linearly growing automorphism of free group has a positive power which is a Dehn twist automorphism. This is a fact that has been taken for granted by many experts, although has no formal proof to be found in the literature.In the case of Dehn twist automorphisms, we then use the known algorithm to make the given Dehn twist representative efficient and apply the Whitehead algorithm as well as the classical theorems by Nielsen, Baers, Zieschangs and others to construct its geometric model or to show that it is not geometric
18
MacKinnon, Benjamin B. "The Automorphism Group of the Halved Cube." VCU Scholars Compass, 2016. http://scholarscompass.vcu.edu/etd/4609.
Full textAbstract:
An n-dimensional halved cube is a graph whose vertices are the binary strings of length n, where two vertices are adjacent if and only if they differ in exactly two positions. It can be regarded as the graph whose vertex set is one partite set of the n-dimensional hypercube, with an edge joining vertices at hamming distance two. In this thesis we compute the automorphism groups of the halved cubes by embedding them in R n and realizing the automorphism group as a subgroup of GLn(R). As an application we show that a halved cube is a circulant graph if and only if its dimension of is at most four.
19
Mumba, Nephtale Bvalamanja. "Codes, graphs and designs from maximal subgroups of alternating groups." University of the Western Cape, 2018. http://hdl.handle.net/11394/6165.
Full textAbstract:
Philosophiae Doctor - PhD (Mathematics)The main theme of this thesis is the construction of linear codes from adjacency matrices or sub-matrices of adjacency matrices of regular graphs. We first examine the binary codes from the row span of biadjacency matrices and their transposes for some classes of bipartite graphs. In this case we consider a sub-matrix of an adjacency matrix of a graph as the generator of the code. We then shift our attention to uniform subset graphs by exploring the automorphism groups of graph covers and some classes of uniform subset graphs. In the sequel, we explore equal codes from adjacency matrices of non-isomorphic uniform subset graphs and finally consider codes generated by an adjacency matrix formed by adding adjacency matrices of two classes of uniform subset graphs.
20
Vodah, Sunday. "Automorphism groups of some designs of steiner triple systems and the atomorphism groups of their block intersection graphs." University of the Western Cape, 2014. http://hdl.handle.net/11394/4527.
Full textAbstract:
>Magister Scientiae - MScA Steiner triple system of order v is a collection of subsets of size three from a set of v-elements such that every pair of the elements of the set is contained in exactly one 3-subset. In this study, we discuss some known Steiner triple systems and their automorphism groups. We also construct block intersection graphs of the Steiner triple systems of our consideration and compare their automorphism groups to the automorphism groups of the Steiner triple systems.
21
Maggiolo, Stefano. "On the automorphism group of certain algebraic varieties." Doctoral thesis, SISSA, 2012. http://hdl.handle.net/20.500.11767/4690.
Full textAbstract:
We study the automorphism groups of two families of varieties. The first is the family of stable curves of low genus. To every such curve, we can associate a combinatorial object, a stable graph, which encode many properties of the curve. Combining the automorphisms of the graph with the known results on the automorphisms of smooth curves, we obtain precise descriptions of the automorphism groups for stable curves with low genera. The second is the family of numerical Godeaux surfaces. We compute in details the automorphism groups of numerical Godeaux surfaces with certain invariants; that is, corresponding to points in some specific connected components of the moduli space; we also give some estimates on the order of the automorphism groups of the other numerical Godeaux surfaces and some characterization on their structures.
22
Muthivhi, Thifhelimbilu Ronald. "Codes Related to and Derived from Hamming Graphs." University of the Western Cape, 2013. http://hdl.handle.net/11394/4091.
Full textAbstract:
Masters of ScienceCodes Related to and Derived from Hamming Graphs T.R Muthivhi M.Sc thesis, Department of Mathematics, University of Western Cape For integers n; k 1; and k n; the graph k n has vertices the 2n vectors of Fn2 and adjacency de ned by two vectors being adjacent if they di er in k coordinate positions. In particular, 1 n is the classical n-cube, usually denoted by H1(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 rst 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 H1(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.
23
Tener, Greg. "ATTACKS ON DIFFICULT INSTANCES OF GRAPH ISOMORPHISM: SEQUENTIAL AND PARALLEL ALGORITHMS." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2631.
Full textAbstract:
The graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best of the existing algorithms perform well in practice; so well that it is challenging to find hard instances for them. The most efficient algorithms, for determining if a pair of graphs are isomorphic, are based on the individualization-refinement paradigm, pioneered by Brendan McKay in 1981 with his algorithm nauty. Nauty and various improved descendants of nauty, such as bliss and saucy, solve the graph isomorphism problem by determining a canonical representative for each of the graphs. The graphs are isomorphic if and only if their canonical representatives are identical. These algorithms also detect the symmetries in a graph which are used to speed up the search for the canonical representative--an approach that performs well in practice. Yet, several families of graphs have been shown to exist which are hard for nauty-like algorithms. This dissertation investigates why these graph families pose difficulty for individualization-refinement algorithms and proposes several techniques for circumventing these limitations. The first technique we propose addresses a fundamental problem pointed out by Miyazaki in 1993. He constructed a family of colored graphs which require exponential time for nauty (and nauty's improved descendants). We analyze Miyazaki's construction to determine the source of difficulty and identify a solution. We modify the base individualization-refinement algorithm by exploiting the symmetries discovered in a graph to guide the search for its canonical representative. This is accomplished with the help of a novel data structure called a guide tree. As a consequence, colored Miyazaki graphs are processed in polynomial time--thus obviating the only known exponential upper-bound on individualization-refinement algorithms (which has stood for the last 16 years). The preceding technique can only help if a graph has enough symmetry to exploit. It cannot be used for another family of hard graphs that have a high degree of regularity, but possess few actual symmetries. To handle these instances, we introduce an adaptive refinement method which utilizes the guide-tree data structure of the preceding technique to use a stronger vertex-invariant, but only when needed. We show that adaptive refinement is very effective, and it can result in dramatic speedups. We then present a third technique ideally suited for large graphs with a preponderance of sparse symmetries. A method was devised by Darga et al. for dealing with these large and highly symmetric graphs, which can reduce runtime by an order of magnitude. We explain the method and show how to incorporate it into our algorithm. Finally, we develop and implement a parallel algorithm for detecting the symmetries in, and finding a canonical representative of a graph. Our novel parallel algorithm divides the search for the symmetries and canonical representative among each processor, allowing for a high degree of scalability. The parallel algorithm is benchmarked on the hardest problem instances, and shown to be effective in subdividing the search space.Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science PhD
24
Smith, Heather Christina. "Zero Divisors among Digraphs." VCU Scholars Compass, 2010. http://scholarscompass.vcu.edu/etd/2120.
Full textAbstract:
This thesis generalizes to digraphs certain recent results about graphs. There are special digraphs C such that AxC is isomorphic to BxC for some pair of distinct digraphs A and B. Lovasz named these digraphs C zero-divisors and completely characterized their structure. Knowing that all directed cycles are zero-divisors, we focus on the following problem: Given any directed cycle D and any digraph A, enumerate all digraphs B such that AxD is isomorphic to BxD. From our result for cycles, we generalize to an arbitrary zero-divisor C, developing upper and lower bounds for the collection of digraphs B satisfying AxC isomorphic to BxC.
25
Vasey, Daniel. "Alternating groups as completions of the Goldschmidt G3-amalgam." Thesis, University of Manchester, 2014. https://www.research.manchester.ac.uk/portal/en/theses/alternating-groups-as-completions-of-the-goldschmidt-g3amalgam(e8819961-7d8d-4c51-93f8-ab74afdf8011).html.
Full textAbstract:
Suppose a group G can be generated by two subgroups, P1 and P2, both isomorphic to S4 which have intersection isomorphic to D8- the dihedral group of order 8. Then G is known as a faithful completion of the Goldschmidt G3-amalgam. In this thesis we consider the alternating groups as faithful completions of the Goldschmidt G3-amalgam.
26
Manjunath, Madhusudan Verfasser], and Kurt [Akademischer Betreuer] [Mehlhorn. "A Riemann-Roch theory for sublattices of the root lattice An, graph automorphisms and counting cycles in graphs / Madhusudan Manjunath. Betreuer: Kurt Mehlhorn." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2012. http://d-nb.info/1052292607/34.
Full text
27
Chassaniol, Arthur. "Contributions à l'étude des groupes quantiques de permutations." Thesis, Clermont-Ferrand 2, 2016. http://www.theses.fr/2016CLF22709/document.
Full textAbstract:
Dans cette thèse nous étudions le groupe quantique d’automorphismes des graphes finis, introduit par Banica et Bichon. Dans un premier temps nous montrerons un théorème de structure du groupe quantique d’automorphismes du produit lexicographique de deux graphes finis réguliers, qui généralise un résultat classique de Sabidussi. Ce théorème donne une condition nécessaire et suffisante pour que ce groupe quantique s’exprime comme le produit en couronne libre des groupes quantiques d’automorphismes de ces deux graphes. Dans un deuxième temps, nous expliciterons certaines améliorations de résultats de Banica, Bichon et Chenevier permettant d’obtenir des critères de non symétrie quantique sur les graphes, à l’aide des outils développés par les auteurs susmentionnés.Enfin, pour poursuivre ces recherches, nous développerons une autre méthode utilisant la dualité de Tannaka-Krein et inspirée de l’étude des groupes quantiques compacts orthogonaux par Banica et Speicher. Celle-ci nous permettra, à l’aide d’une étude orbitale approfondie des graphes sommets-transitifs, d’énoncer une condition suffisante pour qu’un graphe ait des symétries quantiques ; condition qui a vocation à être aussi nécessaire mais ceci reste une conjecture à ce stadeIn this thesis we study the quantum automorphism group of finite graphs, introduces by Banica and Bichon. First we will prove a theorem about the structure of the quantum automorphism group of the lexicographic product of two finite regular graphs. It is a quantum generalization of a classical result of Sabidussi. This theorem gives a necessary and sufficient condition for this quantum group to be discribe as the free wreath product of the quantum automorphism groups of these two graphs. Then, we will give some improvement of Banica, Bichon and Chenevier results, to obtain a quantum non-symmetry criteria on graphs, using tools developped by the above authors. Finally, to continue this research, we will describe another method using Tannaka-Krein duality and inspired by the study of orthogonal compact groups by Banica and Speicher. This will enable us, with a thorough orbital study of vertex-transitive graphs, to state a sufficient condition for a graph to have quantum symmetries ; condition which is intended to be also necessary but this remains conjecture at this point
28
Sousa, Paulo Regis Menezes. "AplicaÃÃes de criptografia quÃntica de chave pÃblica em assinaturas de mensagens." Universidade Federal do CearÃ, 2013. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=13047.
Full textAbstract:
CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel SuperiorAs assinaturas digitais sÃo de fundamental importÃncia para as comunicaÃÃes eletrÃnicas no mundo todo por garantirem a integridade e autenticidade da informaÃÃo. Com os avanÃos da ciÃncia nas Ãreas da mecÃnica quÃntica e a introduÃÃo destes novos conceitos nas telecomunicaÃÃes, a seguranÃa da informaÃÃo tambÃm precisou evoluir e cada vez mais se tem buscado novos sistemas de seguranÃa que forneÃam maior integridade e autenticidade que os sistemas clÃssicos. Dessa forma o objetivo deste trabalho à utilizar as propriedades do problema QSCDff , para a criaÃÃo de um protocolo de assinatura quÃntica de mensagens. O problema QSCD ff possui propriedades matemÃticas e computacionais para garantir a integridade e autenticidade das assinaturas geradas. O protocolo proposto faz uso de chaves descritas na forma de estados quÃnticos construÃdos a partir de permutaÃÃes de um grupo simÃtrico e de uma funÃÃo de hash para a compressÃo da mensagem original. Como entrada o protocolo recebe a mensagem clÃssica e uma chave privada. Para a geraÃÃo do estado quÃntico da assinatura utiliza-se uma permutaÃÃo como chave privada e o hash da mensagem. Gerar tal assinatura sem ter uma chave privada consiste em resolver um problema de encontrar automorfismos nÃo triviais de grafos. A validaÃÃo deste estado à feita atravÃs da aplicaÃÃo do algoritmo quÃntico de busca de Grover. Por fim à mostrado que a probabilidade de falsificaÃÃo da assinatura à negligenciÃvel dado o nÃmero de cÃpias do estado da assinatura.
29
Dirino, Kariny de Andrade. "Um estudo sobre álgebras associadas a alguns grafos orientados em níveis." Universidade Federal de Goiás, 2017. http://repositorio.bc.ufg.br/tede/handle/tede/7784.
Full textAbstract:
Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2017-09-22T11:27:19Z
No. of bitstreams: 2
Dissertação - Kariny de Andrade Dirino - 2017.pdf: 1986993 bytes, checksum: fd843aaf3aee361fd3b4dd512828d8f0 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-09-22T11:27:47Z (GMT) No. of bitstreams: 2 Dissertação - Kariny de Andrade Dirino - 2017.pdf: 1986993 bytes, checksum: fd843aaf3aee361fd3b4dd512828d8f0 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Made available in DSpace on 2017-09-22T11:27:47Z (GMT). No. of bitstreams: 2 Dissertação - Kariny de Andrade Dirino - 2017.pdf: 1986993 bytes, checksum: fd843aaf3aee361fd3b4dd512828d8f0 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-08-28
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
Considering a layered directed graphs we may associate it to an algebra, denoted as , whose generators are the edges of the graph and the relations are defined through: every ways with the same initial vertex and the same final vertex determine different fractorizations for the same polynomial with coefficients in a non-commutative ring. We present a study about these algebras and their main properties, presenting some classes of examples and having as central focus the Hasse graph of the partially ordered set of k -faces of Petersen graph, . We discuss the results on basis for algebras of type we calculate their Hilbert series and the automorphisms group of these algebras, we determine the subgraphs induced by the set of vertices fixed by each and we calculate the graded trace generating functions, in order to introduce problems related to koszulity.
Dado um grafo orientado em níveis podemos associar a ele uma álgebra, denotada por cujos geradores são as arestas do grafo e as relações são definidas mediante: todos os caminhos com o mesmo vértice inicial e mesmo vértice final determinam fatorações distintas para o mesmo polinômio com coeficientes em um anel não comutativo. Exibimos um estudo sobre essas álgebras e suas principais propriedades, apresentando algumas classes de exemplos e tendo como foco central o grafo de Hasse do conjunto parcialmente ordenado das k-faces do grafo de Petersen, . Abordamos resultados sobre bases para álgebras do tipo , calculamos as suas séries de Hilbert e o grupo dos automorfismos dessas álgebras, determinamos os subgrafos induzidos pelo conjunto dos vértices fixados por cada e calculamos as funções geradoras do traço graduado, a fim de introduzirmos problemas relacionados à koszulidade.
30
Bobga, Benkam Benedict. "Bicyclic Mixed Triple Systems." Digital Commons @ East Tennessee State University, 2005. https://dc.etsu.edu/etd/1043.
Full textAbstract:
In the study of triple systems, one question faced is that of finding for what order a decomposition exists. We state and prove a necessary and sufficient condition for the existence of a bicyclic mixed triple system based on the three possible partial orientations of the 3-cycle with twice as many arcs as edges. We also explore the existence of rotational and reverse mixed triple systems. Our principal proof technique applied is the difference method. Finally, this work contains a result on packing of complete mixed graphs on v vertices, Mv, with isomorphic copies of two of the mixed triples and a possible leave structure.
31
Talpo, Humberto Luiz. "Reflexões e numero de cobertura de arvores homogeneas e grupos de automorfismos de arvores semi-homogeneas." [s.n.], 2006. http://repositorio.unicamp.br/jspui/handle/REPOSIP/305924.
Full textAbstract:
Orientadores: Marcelo Firer, Luiz Antonio Barrera San MartinTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
Made available in DSpace on 2018-08-05T23:33:46Z (GMT). No. of bitstreams: 1 Talpo_HumbertoLuiz_D.pdf: 1408389 bytes, checksum: b11f884cbf1e05f81138a8e91a5980dc (MD5) Previous issue date: 2006
Resumo: Seja G uma árvore homogênea e Aut(G) seu grupo de automorfismos. Um automorfismo f Î Aut(G) é par se d(f(x),x) º0 mod 2 para todo vértice x Î G, onde d(.,.) é a função distância definida pelo comprimento do menor caminho ligando os vértices. O conjunto Aut+(G) de todos os automorfismos pares é um subgrupo de índice 2 em Aut(G). Definimos uma geodésica g Ì G como um subgrafo isomorfo a Z (onde Z é visto como um grafo que possui arestas unindo inteiros consecutivos). Uma reflexão em uma geodésica g é um automorfismo involutivo f (f² =1) tal que f(x) = x se, e somente se, x Î G. Denotamos por R o conjunto de todas as reflexões em geodésicas. Neste trabalho (Capítulo 2) provamos que, dada uma árvore homogênea de grau par G, o número de cobertura de Aut+(G) pelas reflexões em geodésicas é 11, no seguinte sentido: dado f Î Aut+(G) existem f1, f2,... fk com k £ 11, tais que f(x) = fk °fk-1°...°f1(x) para todo vértice x em G. Além disso, considerando árvores homogêneas, sabemos que o grupo de automorfismos é completo e o subgrupo de automorfismos pares é simples. Flexibilizamos a condição de homogeneidade e conseguimos demonstrar (Capítulo 3) para o caso de árvores semi-homogêneas, que o grupo de automorfismos é simples e completo
Abstract: Let G be a homogeneous tree and Aut(G) its group of automorphism. An automorphism Î Aut(G) is said to be even if d(f(x),x) º0 mod 2 for every vertex x Î G of , where d(.,.) is the canonical distance function defined by the minimum length of paths connecting the vertices. The set Aut+(G) of all even automorphism is a subgroup of index 2 in Aut(G). We define a geodesic g Ì G as a subtree isomorphic to the standard tree of the integers Z, that is, a homogeneous subtree of degree 2. A reflection in a geodesic g is an involutive automorphism f (f² =1) such that f(x) = x if x Î G. We denote by R the set of all reflections in geodesics. In this work (Chapter 2) we prove that, for every even degree tree G, the covering number of Aut+(G) by reflections in geodesics is 11, in the sense that give f Î Aut+(G) there are f1, f2,... fk with k £ 11, such that f(x) = fk °fk-1°...°f1(x) for every vertex x in G.Moreover, if we consider homogeneous trees we know that automorphisms group is complete and the even automorphisms subgroup is simple. We vary the homogeneous condition and we prove that (Chapter 3) for the semi-homogeneous trees, the automorphisms group is simple and complete
Doutorado
Doutor em Matemática
32
Tran, Quan Duc. "Tricyclic Steiner Triple Systems with 1-Rotational Subsystems." Digital Commons @ East Tennessee State University, 2007. https://dc.etsu.edu/etd/2102.
Full textAbstract:
A Steiner triple system of order v, denoted STS(v), is said to be tricyclic if it admits an automorphism whose disjoint cyclic decomposition consists of three cycles. In this thesis we give necessary and sufficient conditions for the existence of a tricyclic STS(v) when one of the cycles is of length one. In this case, the STS(v) will contain a subsystem which admits an automorphism consisting of a fixed point and a single cycle. The subsystem is said to be 1-rotational.
33
Wade, Richard D. "Symmetries of free and right-angled Artin groups." Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:b856e2b5-3689-472b-95c1-71b5748affc9.
Full textAbstract:
The objects of study in this thesis are automorphism groups of free and right-angled Artin groups. Right-angled Artin groups are defined by a presentation where the only relations are commutators of the generating elements. When there are no relations the right-angled-Artin group is a free group and if we take all possible relations we have a free abelian group. We show that if no finite index subgroup of a group $G$ contains a normal subgroup that maps onto $mathbb{Z}$, then every homomorphism from $G$ to the outer automorphism group of a free group has finite image. The above criterion is satisfied by SL$_m(mathbb{Z})$ for $m geq 3$ and, more generally, all irreducible lattices in higher-rank, semisimple Lie groups with finite centre. Given a right-angled Artin group $A_Gamma$ we find an integer $n$, which may be easily read off from the presentation of $A_G$, such that if $m geq 3$ then SL$_m(mathbb{Z})$ is a subgroup of the outer automorphism group of $A_Gamma$ if and only if $m leq n$. More generally, we find criteria to prevent a group from having a homomorphism to the outer automorphism group of $A_Gamma$ with infinite image, and apply this to a large number of irreducible lattices as above. We study the subgroup $IA(A_Gamma)$ of $Aut(A_Gamma)$ that acts trivially on the abelianisation of $A_Gamma$. We show that $IA(A_Gamma)$ is residually torsion-free nilpotent and describe its abelianisation. This is complemented by a survey of previous results concerning the lower central series of $A_Gamma$. One of the commonly used generating sets of $Aut(F_n)$ is the set of Whitehead automorphisms. We describe a geometric method for decomposing an element of $Aut(F_n)$ as a product of Whitehead automorphisms via Stallings' folds. We finish with a brief discussion of the action of $Out(F_n)$ on Culler and Vogtmann's Outer Space. In particular we describe translation lengths of elements with regards to the `non-symmetric Lipschitz metric' on Outer Space.
34
Barboza, Marcelo Bezerra. "Sobre uma classe de álgebras associadas a duas famílias de grafos orientados." Universidade Federal de Goiás, 2015. http://repositorio.bc.ufg.br/tede/handle/tede/4541.
Full textAbstract:
Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-05-19T11:39:34Z
No. of bitstreams: 2
Dissertação - Marcelo Bezerra Barboza - 2015.pdf: 1031294 bytes, checksum: 1a2c64373fbcf29d38e433509a38f1ab (MD5)
license_rdf: 19874 bytes, checksum: 38cb62ef53e6f513db2fb7e337df6485 (MD5)Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-05-19T11:45:05Z (GMT) No. of bitstreams: 2 Dissertação - Marcelo Bezerra Barboza - 2015.pdf: 1031294 bytes, checksum: 1a2c64373fbcf29d38e433509a38f1ab (MD5) license_rdf: 19874 bytes, checksum: 38cb62ef53e6f513db2fb7e337df6485 (MD5)
Made available in DSpace on 2015-05-19T11:45:05Z (GMT). No. of bitstreams: 2 Dissertação - Marcelo Bezerra Barboza - 2015.pdf: 1031294 bytes, checksum: 1a2c64373fbcf29d38e433509a38f1ab (MD5) license_rdf: 19874 bytes, checksum: 38cb62ef53e6f513db2fb7e337df6485 (MD5) Previous issue date: 2015-03-02
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
Given a directed layered graph , we present the algebra A() as a quotient of the free associative or tensor algebra (with unit, over an arbitrarily fixed field of scalars), freely generated by the set of edges in . We calculate the Hilbert series associated with the grading on A() coming from degree in the tensor algebra. We also calculate the group of automorphisms of A() that preserve the (ascending) filtration associated with the grading mentioned above. Despite the fact the main results within this notes remain true for a relatively large class of directed graphs, we stay close to the ones Dn and Ln, n 3, that is, those consisting, respectively, on the Hasse diagram of the partially ordered sets of faces in a regular polygon containing n edges and the power set of {1, . . . , n}. The work teaching us all of the above is [1], by Colleen Duffy.
Dado um grafo orientado em níveis, apresentamos a álgebra A() como um quociente da álgebra associativa livre ou tensorial (com unidade, sobre um corpo de escalares arbitrariamente fixado), livremente gerada pelo conjunto de arestas em . Calculamos a série de Hilbert associada à graduação em A() proveniente do grau na álgebra tensorial. Também calculamos o grupo dos automorfismos de A() que preservam a filtração (crescente) associada à graduação acima mencionada. Apesar de os resultados principais permanecerem verdadeiros para uma classe relativamente ampla de grafos orientados, permanecemos próximos a Dn e Ln, n 3, isto é, aqueles que consistem, respectivamente, no diagrama de Hasse dos conjuntos parcialmente ordenados das faces de um polígono regular de n lados e no conjunto das partes de {1, . . . , n}. O trabalho do qual aprendemos todo o acima é [1], por Collen Duffy.
35
Artemenko, Igor. "On Weak Limits and Unimodular Measures." Thèse, Université d'Ottawa / University of Ottawa, 2014. http://hdl.handle.net/10393/30417.
Full textAbstract:
In this thesis, the main objects of study are probability measures on the isomorphism classes of countable, connected rooted graphs. An important class of such measures is formed by unimodular measures, which satisfy a certain equation, sometimes referred to as the intrinsic mass transport principle. The so-called law of a finite graph is an example of a unimodular measure. We say that a measure is sustained by a countable graph if the set of rooted connected components of the graph has full measure. We demonstrate several new results involving sustained unimodular measures, and provide thorough arguments for known ones. In particular, we give a criterion for unimodularity on connected graphs, deduce that connected graphs sustain at most one unimodular measure, and prove that unimodular measures sustained by disconnected graphs are convex combinations. Furthermore, we discuss weak limits of laws of finite graphs, and construct counterexamples to seemingly reasonable conjectures.
36
Le, Boudec Adrien. "Géométrie des groupes localement compacts. Arbres. Action !" Thesis, Paris 11, 2015. http://www.theses.fr/2015PA112036.
Full textAbstract:
Dans le Chapitre 1 nous étudions les groupes localement compacts lacunaires hyperboliques. Nous caractérisons les groupes ayant un cône asymptotique qui est un arbre réel et dont l'action naturelle est focale. Nous étudions également la structure des groupes lacunaires hyperboliques, et montrons que dans le cas unimodulaire les sous-groupes ne satisfont pas de loi. Nous appliquons au Chapitre 2 les résultats précédents pour résoudre le problème de l'existence de points de coupure dans un cône asymptotique dans le cas des groupes de Lie connexes. Dans le Chapitre 3 nous montrons que le groupe de Neretin est compactement présenté et donnons une borne supérieure sur sa fonction de Dehn. Nous étudions également les propriétés métriques du groupe de Neretin, et prouvons que certains sous-groupes remarquables sont quasi-isométriquement plongés. Nous étudions dans le Chapitre 4 une famille de groupes agissant sur un arbre, et dont l'action locale est prescrite par un groupe de permutations. Nous montrons entre autres que ces groupes ont la propriété (PW), et exhibons des groupes simples au sein de cette famille. Dans le Chapitre 5 nous introduisons l'éventail des relations d'un groupe de type fini, qui est l'ensemble des longueurs des relations non engendrées par des relations plus courtes. Nous établissons un lien entre la simple connexité d'un cône asymptotique et l'éventail des relations du groupe, et donnons une grande classe de groupes dont l'éventail des relations est aussi grand que possibleIn Chapter 1 we investigate the class of locally compact lacunary hyperbolic groups. We characterize locally compact groups having one asymptotic cone that is a real tree and whose natural isometric action is focal. We also study the structure of lacunary hyperbolic groups, and prove that in the unimodular case subgroups cannot satisfy a law. We apply the previous results in Chapter 2 to solve the problem of the existence of cut-points in asymptotic cones for connected Lie groups. In Chapter 3 we prove that Neretin's group is compactly presented and give an upper bound on its Dehn function. We also study metric properties of Neretin's group, and prove that some remarkable subgroups are quasi-isometrically embedded. In Chapter 4 we study a family of groups acting on a tree, and whose local action is prescribed by some permutation group. We prove among other things that these groups have property (PW), and exhibit some simple groups in this family. In Chapter 5 we introduce the relation range of a finitely generated group, which is the set of lengths of relations that are not generated by relations of smaller length. We establish a link between simple connectedness of asymptotic cones and the relation range of the group, and give a large class of groups having a relation range as large as possible
37
Haubold, Niko. "Compressed Decision Problems in Groups." Doctoral thesis, Universitätsbibliothek Leipzig, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-85413.
Full textAbstract:
Wir beschäftigen uns mit Problemen der algorithmischen Gruppentheorie und untersuchen dabei die Komplexität von komprimierten Versionen des Wortproblems und des Konjugationsproblems für endlich erzeugte Gruppen.
Das Wortproblem fragt für eine feste, endlich erzeugte Gruppe ob ein gegebenes Wort über der Erzeugermenge das neutrale Element der Gruppe repräsentiert. Wir betrachten das gegebene Wort jedoch in einer komprimierten Form, als Straight-line Program (SLP) und untersuchen die Komplexität dieses Problems, das wir \'komprimiertes Wortproblem\' nennen. SLPs sind kontextfreie Grammatiken, die genau einen String erzeugen. Die Eingabegröße ist dabei stets die Größe des gegebenen SLPs. Eine Hauptmotivation ist dabei, dass für eine feste endlich erzeugte Gruppe das Wortproblem ihrer Automorphismengruppe durch eine Turingmaschine in Polynomialzeit auf das komprimierte Wortproblem der Gruppe selbst reduzierbar ist.
Wir untersuchen das komprimierte Wortproblem für die verbreiteten Gruppenerweiterungen HNN-Erweiterungen (amalgamierte Produkte und Graphprodukte) und können zeigen, dass sich Instanzen des komprimierten Wortproblems von einer Turingmaschine in Polynomialzeit auf Instanzen des komprimierten Wortproblems der Basisgruppe (respektive Basisgruppen und Knotengruppen) reduzieren lassen. Weiterhin zeigen wir, dass das komprimierte Wortproblem für endlich erzeugte nilpotente Gruppen von einer Turingmaschine in Polynomialzeit entscheidbar ist.
Wir betrachten außerdem eine komprimierte Variante des Konjugationsproblems. Das unkomprimierte Konjugationsproblem fragt für zwei gegebene Wörter über den Erzeugern einer festen endlich erzeugten Gruppe, ob sie in dieser Gruppe konjugiert sind. Beim komprimierten Konjugationsproblem besteht die Eingabe aus zwei SLPs und es wird gefragt, ob die beiden Wörter die von den SLPs erzeugt werden in der Gruppe konjugierte Elemente präsentieren. Wir konnten zeigen, dass sich das komprimierte Konjugationsproblem für Graphgruppen in Polynomialzeit entscheiden lässt.
Weiterhin haben wir das Wortproblem der äußeren Automorphismengruppen von Graphprodukten endlich erzeugter Gruppen untersucht. Durch den engen Zusammenhang des komprimierten Konjugationsproblems einer Gruppe mit dem Wortproblem der äußeren Automorphismengruppe konnten wir zeigen, dass sich das Wortproblem der äußeren Automorphismengruppe eines Graphprodukts von endlich erzeugten Gruppen durch eine Turingmaschine in Polynomialzeit auf Instanzen von simultanen komprimierten Konjugationsproblemen der Knotengruppen und Instanzen von komprimierten Wortproblemen der Knotengruppen reduzieren lässt.
Als Anwendung gelten obige Resultate auch für right-angled Coxetergruppen und Graphgruppen, da beide spezielle Graphprodukte sind. So folgt beispielsweise, dass das komprimierte Wortproblem einer right-angled Coxetergruppe in Polynomialzeit entscheidbar ist.
38
Gagnon, Jérôme. "Les graphes asymétriques minimaux de longueur induite 3." Thèse, 2006. http://hdl.handle.net/1866/17293.
Full text
39
Fournier, J. "Automorphismes et isomorphismes des graphes de Cayley." Thèse, 2004. http://hdl.handle.net/1866/17274.
Full text
40
Gray, Jonathan Nathan. "On the homology of automorphism groups of free groups." 2011. http://trace.tennessee.edu/utk_graddiss/974.
Full textAbstract:
Following the work of Conant and Vogtmann on determining the homology of the group of outer automorphisms of a free group, a new nontrivial class in the rational homology of Outer space is established for the free group of rank eight. The methods started in [8] are heavily exploited and used to create a new graph complex called the space of good chord diagrams. This complex carries with it significant computational advantages in determining possible nontrivial homology classes.Next, we create a basepointed version of the Lie operad and explore some of it proper- ties. In particular, we prove a Kontsevich-type theorem that relates the Lie homology of a particular space to the cohomology of the group of automorphisms of the free group.
41
Shrivastava, Abhishek Kumar. "Listing Unique Fractional Factorial Designs." 2009. http://hdl.handle.net/1969.1/ETD-TAMU-2009-12-7345.
Full textAbstract:
Fractional factorial designs are a popular choice in designing experiments for
studying the effects of multiple factors simultaneously. The first step in planning an
experiment is the selection of an appropriate fractional factorial design. An appro-
priate design is one that has the statistical properties of interest of the experimenter
and has a small number of runs. This requires that a catalog of candidate designs
be available (or be possible to generate) for searching for the "good" design. In the
attempt to generate the catalog of candidate designs, the problem of design isomor-
phism must be addressed. Two designs are isomorphic to each other if one can be
obtained from the other by some relabeling of factor labels, level labels of each factor
and reordering of runs. Clearly, two isomorphic designs are statistically equivalent.
Design catalogs should therefore contain only designs unique up to isomorphism.
There are two computational challenges in generating such catalogs. Firstly,
testing two designs for isomorphism is computationally hard due to the large number
of possible relabelings, and, secondly, the number of designs increases very rapidly
with the number of factors and run-size, making it impractical to compare all designs
for isomorphism. In this dissertation we present a new approach for tackling both
these challenging problems. We propose graph models for representing designs and
use this relationship to develop efficient algorithms. We provide a new efficient iso-
morphism check by modeling the fractional factorial design isomorphism problem as
graph isomorphism problem. For generating the design catalogs efficiently we extend a result in graph isomorphism literature to improve the existing sequential design
catalog generation algorithm.
The potential of the proposed methods is reflected in the results. For 2-level
regular fractional factorial designs, we could generate complete design catalogs of run
sizes up to 4096 runs, while the largest designs generated in literature are 512 run
designs. Moreover, compared to the next best algorithms, the computation times
for our algorithm are 98% lesser in most cases. Further, the generic nature of the
algorithms makes them widely applicable to a large class of designs. We give details of
graph models and prove the results for two classes of designs, namely, 2-level regular
fractional factorial designs and 2-level regular fractional factorial split-plot designs,
and provide discussions for extensions, with graph models, for more general classes
of designs.
42
Zeman, Peter. "Algebraické, strukturální a výpočetní vlastnosti geometrických reprezentací grafů." Master's thesis, 2016. http://www.nusl.cz/ntk/nusl-352783.
Full textAbstract:
Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
43
Haubold, Niko. "Compressed Decision Problems in Groups." Doctoral thesis, 2011. https://ul.qucosa.de/id/qucosa%3A11370.
Full textAbstract:
Wir beschäftigen uns mit Problemen der algorithmischen Gruppentheorie und untersuchen dabei die Komplexität von komprimierten Versionen des Wortproblems und des Konjugationsproblems für endlich erzeugte Gruppen.
Das Wortproblem fragt für eine feste, endlich erzeugte Gruppe ob ein gegebenes Wort über der Erzeugermenge das neutrale Element der Gruppe repräsentiert. Wir betrachten das gegebene Wort jedoch in einer komprimierten Form, als Straight-line Program (SLP) und untersuchen die Komplexität dieses Problems, das wir \''komprimiertes Wortproblem\'' nennen. SLPs sind kontextfreie Grammatiken, die genau einen String erzeugen. Die Eingabegröße ist dabei stets die Größe des gegebenen SLPs. Eine Hauptmotivation ist dabei, dass für eine feste endlich erzeugte Gruppe das Wortproblem ihrer Automorphismengruppe durch eine Turingmaschine in Polynomialzeit auf das komprimierte Wortproblem der Gruppe selbst reduzierbar ist.
Wir untersuchen das komprimierte Wortproblem für die verbreiteten Gruppenerweiterungen HNN-Erweiterungen (amalgamierte Produkte und Graphprodukte) und können zeigen, dass sich Instanzen des komprimierten Wortproblems von einer Turingmaschine in Polynomialzeit auf Instanzen des komprimierten Wortproblems der Basisgruppe (respektive Basisgruppen und Knotengruppen) reduzieren lassen. Weiterhin zeigen wir, dass das komprimierte Wortproblem für endlich erzeugte nilpotente Gruppen von einer Turingmaschine in Polynomialzeit entscheidbar ist.
Wir betrachten außerdem eine komprimierte Variante des Konjugationsproblems. Das unkomprimierte Konjugationsproblem fragt für zwei gegebene Wörter über den Erzeugern einer festen endlich erzeugten Gruppe, ob sie in dieser Gruppe konjugiert sind. Beim komprimierten Konjugationsproblem besteht die Eingabe aus zwei SLPs und es wird gefragt, ob die beiden Wörter die von den SLPs erzeugt werden in der Gruppe konjugierte Elemente präsentieren. Wir konnten zeigen, dass sich das komprimierte Konjugationsproblem für Graphgruppen in Polynomialzeit entscheiden lässt.
Weiterhin haben wir das Wortproblem der äußeren Automorphismengruppen von Graphprodukten endlich erzeugter Gruppen untersucht. Durch den engen Zusammenhang des komprimierten Konjugationsproblems einer Gruppe mit dem Wortproblem der äußeren Automorphismengruppe konnten wir zeigen, dass sich das Wortproblem der äußeren Automorphismengruppe eines Graphprodukts von endlich erzeugten Gruppen durch eine Turingmaschine in Polynomialzeit auf Instanzen von simultanen komprimierten Konjugationsproblemen der Knotengruppen und Instanzen von komprimierten Wortproblemen der Knotengruppen reduzieren lässt.
Als Anwendung gelten obige Resultate auch für right-angled Coxetergruppen und Graphgruppen, da beide spezielle Graphprodukte sind. So folgt beispielsweise, dass das komprimierte Wortproblem einer right-angled Coxetergruppe in Polynomialzeit entscheidbar ist.