This paper discusses the direct product cancellation of digraphs. We define the exact conditions on G such that GxK=HxK implies G=H. We focus first on simple equations such as GxK_2=HxK_2 where K_2 denotes a single arc and then extend this to the more general situation, GxK = HxK. Our results are achieved by using a “factorial” operation on graphs, which is in some sense analogous to the factorial of an integer.

viii, 125 p. A print copy of this thesis is available through the UO Libraries. Search the library catalog for the location and call number. / Finite p -groups are studied using bilinear methods which lead to using nonassociative rings. There are three main results, two which apply only to p -groups and the third which applies to all groups. First, for finite p -groups P of class 2 and exponent p the following are invariants of fully refined central decompositions of P : the number of members in the decomposition, the multiset of orders of the members, and the multiset of orders of their centers. Unlike for direct product decompositions, Aut P is not always transitive on the set of fully refined central decompositions, and the number of orbits can in fact be any positive integer. The proofs use the standard semi-simple and radical structure of Jordan algebras. These algebras also produce useful criteria for a p -group to be centrally indecomposable. In the second result, an algorithm is given to find a fully refined central decomposition of a finite p -group of class 2. The number of algebraic operations used by the algorithm is bounded by a polynomial in the log of the size of the group. The algorithm uses a Las Vegas probabilistic algorithm to compute the structure of a finite ring and the Las Vegas MeatAxe is also used. However, when p is small, the probabilistic methods can be replaced by deterministic polynomial-time algorithms. The final result is a polynomial time algorithm which, given a group of permutations, matrices, or a polycyclic presentation; returns a Remak decomposition of the group: a fully refined direct decomposition. The method uses group varieties to reduce to the case of p -groups of class 2. Bilinear and ring theory methods are employed there to complete the process. / Adviser: William M. Kantor

A semigroup is simply a set with an associative binary operation; computational semigroup theory is the branch of mathematics concerned with developing techniques for computing with semigroups, as well as investigating semigroups with the help of computers. This thesis explores both sides of computational semigroup theory, across several topics, especially in the finite case. The central focus of this thesis is computing and describing maximal subsemigroups of finite semigroups. A maximal subsemigroup of a semigroup is a proper subsemigroup that is contained in no other proper subsemigroup. We present novel and useful algorithms for computing the maximal subsemigroups of an arbitrary finite semigroup, building on the paper of Graham, Graham, and Rhodes from 1968. In certain cases, the algorithms reduce to computing maximal subgroups of finite groups, and analysing graphs that capture information about the regular I-classes of a semigroup. We use the framework underpinning these algorithms to describe the maximal subsemigroups of many families of finite transformation and diagram monoids. This reproduces and greatly extends a large amount of existing work in the literature, and allows us to easily see the common features between these maximal subsemigroups. This thesis is also concerned with direct products of semigroups, and with a special class of semigroups known as Rees 0-matrix semigroups. We extend known results concerning the generating sets of direct products of semigroups; in doing so, we propose techniques for computing relatively small generating sets for certain kinds of direct products. Additionally, we characterise several features of Rees 0-matrix semigroups in terms of their underlying semigroups and matrices, such as their Green's relations and generating sets, and whether they are inverse. In doing so, we suggest new methods for computing Rees 0-matrix semigroups.