Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 15 of 15 for “"Cayley graph"”.
-
Automata on Cayley Graphs
… to realize very general kinds of inputs. Any graph with the above two properties of a tape must, in fact, be the Cayley graph of a suitable group. Recent investigations by various authors have begun to shed some light on what promises to be intimate connections between the geometry of a Cayley …
-
Universality of Cutoff for Random Walks on Random Cayley Graphs
Consider the random Cayley graph of a finite group G with respect to k generators chosen uniformly at random. This draws a Cayley graph uniformly amongst all degree-k Cayley graphs of G. A conjecture of Aldous and Diaconis (1985) from the '80s asserts, for k ≫ log |G|, the following: • the random …
-
Some applications of noncommutative groups and semigroups to information security
… and compute bounds on the girth of the Cayley graph of the subgroup of SL<sub>2</sub>(F<sub>p</sub>) for specific generators <em>A</em>, <em>B</em>. We demonstrate that even without optimization, these hashes have comparable performance to hashes in the SHA family.</p>
-
Cayley maps for certain cyclic groups with odd generators
… work for both oral and written presentation; A Cayley graph provides us with a discrete model for a finite group with specified generating set. It is desirable to represent such structures in their simplest form and also so that certain symmetries are emphasized. By simplest form, we mean to …
-
Artin Groups of Extra-Large Type Are Biautomatic
… Using these techniques we examine paths in the Cayley graph of the Artin group. For any Artin group G, with semigroup generators ${\cal A}$, we define a language $L(G) \subset {\cal A}\sp*$. The language L(G) is a set of canonical forms for the Artin group. In the case G is an Artin group of …
-
Average Cayley genus for Cayley maps with dihedral groups
… and let Delta be a generating set for Gamma. A Cayley map associated with Gamma and Delta is an oriented 2-cell embedding of the Cayley graph GDelta (Gamma) such that the rotation of arcs emanating from each vertex is determined by a unique cyclic permutation of generators and their inverses. A …
-
Detecting topological properties of boundaries of hyperbolic groups
… approximated by spheres of large radius in the Cayley graph of the group. The technical results contained in this thesis are effective versions of this statement: we see that the presence of a particular topological feature in the boundary of a hyperbolic group is determined by the geometry of …
-
Solving Algorithmic Problems in Finitely Presented Groups via Machine Learning
… that are of interest to non-commutative cryptography.</p> <p>As a prototypical example, we utilize supervised learning methods to construct classifiers that can solve the conjugacy decision problem, i.e., determine whether or not a pair of elements from a specified group are conjugate. The …
-
Random Sorting Networks, the Directed Landscape, and Random Polynomials
… is a shortest path from 12···n to n···21 in the Cayley graph of the symmetric group Sn generated by adjacent transpositions. We prove that in a uniform random n-element sorting network σn, all particle trajectories are close to sine curves with high probability. We also find the weak limit of the …
-
Group-invariant random processes
… point process on Rd and examine what types of graphs can be defined on the points of the process in such a way that the point process and the graph have an equivariant distribution. We show that 1-ended trees and Zn can be achieved for invariant point processes in Rd that satisfy some …
-
Lines in Hales-Jewett cubes and other combinatorial results
… a generating set for the group, but in fact the Cayley graph of G with respect to these elements is highly connected, in the sense that it is an expander graph. Our proof of the Alon-Roichman Theorem gives an improvement to the known bounds. In Chapter 3, we study properties of random graphs …
-
Single and joint iterative decoding for higher order modulation schemes
… (LDPC) codes, iterative decoding on Tanner graphs, and their application on joint iterative receivers based on the turbo principle, previously proposed. The construction of random LDPC codes that fulfil certain desirable characteristics, such as large girth, specific p and -y values, and …
-
Results in Extremal Graph Theory, Ramsey Theory and Additive Combinatorics
… 2, we consider a central problem in Extremal Graph Theory. The extremal number (or Turán number) ex(n,H) of a graph H is the maximum number of edges in an H-free graph on n vertices. It is a major area of research to better understand the extremal number of bipartite graphs. In this chapter we …