The aim of this work is to investigate some algebraic and combinatorial aspects of group factorizations. The main contribution of this dissertation is a set of new results regarding factorization of groups, with emphasis on the nonabelian case. We introduce a novel technique for factorization of groups, the so-called free mappings, a powerful tool for factorization of a wide class of abelian and non-abelian groups. By applying a certain group action on the blocks of a factorization, a number of combinatorial and computational problems were noted and studied. In particular, we analyze the case of the group Aut(Zn) acting on blocks of factorization of Zn. We present new theoretical facts that reveal the numerical structure of the stabilizer of a set in Zn, under the action of Aut(Zn). New algorithms for finding the stabilizer of a set and checking whether two sets belong to the same orbit are proposed. / by Vladimir Bozovic. / Thesis (Ph.D.)--Florida Atlantic University, 2008. / Includes bibliography. / Electronic reproduction. Boca Raton, FL : 2008 Mode of access: World Wide Web.

Thesis. 1977. Ph.D.--Massachusetts Institute of Technology. Dept. of Mathematics. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND SCIENCE. / Vita. / Bibliography : leaves 104-110. / Ph.D.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1979. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND SCIENCE. / Vita. / Bibliography: leaves 74-75. / Ph.D.

We will explore progenitors extensively throughout this project. The progenitor, developed by Robert T Curtis, is a special type of infinite group formed by a semi-direct product of a free group m*n and a transitive permutation group of degree n. Since progenitors are infinite, we add necessary relations to produce finite homomorphic images. Curtis found that any non-abelian simple group is a homomorphic image of a progenitor of the form 2*n: N. In particular, we will investigate progenitors that generate two of the Mathieu sporadic groups, M11 and M11, as well as some classical groups. We will prove their existences a variety of different ways, including the process of double coset enumeration, Iwasawa's Lemma, and linear fractional mappings. We will also investigate the various techniques of finding finite images and their corresponding isomorphism types.

The k-core of a graph is its maximal subgraph with minimum degree at least k. The study of k-cores in random graphs was initiated by Bollobás in 1984 in connection to k-connected subgraphs of random graphs. Subsequently, k-cores and their properties have been extensively investigated in random graphs and hypergraphs, with the determination of the threshold for the emergence of a giant k-core, due to Pittel, Spencer and Wormald, as one of the most prominent results. In this thesis, we obtain an asymptotic formula for the number of 2-connected graphs, as well as 2-edge-connected graphs, with given number of vertices and edges in the sparse range by exploiting properties of random 2-cores. Our results essentially cover the whole range for which asymptotic formulae were not described before. This is joint work with G. Kemkes and N. Wormald. By defining and analysing a core-type structure for uniform hypergraphs, we obtain an asymptotic formula for the number of connected 3-uniform hypergraphs with given number of vertices and edges in a sparse range. This is joint work with N. Wormald. We also examine robustness aspects of k-cores of random graphs. More specifically, we investigate the effect that the deletion of a random edge has in the k-core as follows: we delete a random edge from the k-core, obtain the k-core of the resulting graph, and compare its order with the original k-core. For this investigation we obtain results for the giant k-core for Erdős-Rényi random graphs as well as for random graphs with minimum degree at least k and given number of vertices and edges.

A map is an embedding of the vertices and edges of a graph into a compact 2-manifold such that the remainder of the surface has components homeomorphic to open disks. With the goal of proving the Four Colour Theorem, Tutte began the field of map enumeration in the 1960's. His methods included developing the edge deletion decomposition, developing and solving a recurrence and functional equation based on this decomposition, and developing the medial bijection between two equinumerous infinite families of maps. Beginning in the 1980's Jackson, Goulden and Visentin applied algebraic methods in enumeration of non-planar and non-orientable maps, to obtain results of interest for mathematical physics and algebraic geometry, and the Quadrangulation Conjecture and the Map-Jack Conjecture. A special case of the former is solved by Tutte's medial bijection. The latter uses Jack symmetric functions which are a topic of active research. In the 1960's Walsh and Lehman introduced a method of encoding orientable maps. We develop a similar method, based on depth first search and extended to non-orientable maps. With this, we develop a bijection that extends Tutte's medial bijection and partially solves the Quadrangulation Conjecture. Walsh extended Tutte's recurrence for planar maps to a recurrence for all orientable maps. We further extend the recurrence to include non-orientable maps, and express it as a partial differential equation satisfied by the generating series. By appropriately interpolating the differential equation and applying the depth first search method, we construct a parameter that empirically fulfils the conditions of the Map-Jack Conjecture, and we prove some of its predicted properties. Arques and Beraud recently obtained a continued fraction form of a specialisation of the generating series for maps. We apply the depth search method with an ordinary differential equation, to construct a bijection whose existence is implied by the continued fraction.

Decreasing fossil fuel reserves and environmental concerns necessitate a shift toward biofuels. However, the chemistry of many biomass to fuel conversion pathways remains to be thoroughly studied. The future of biorefineries thus depends on developing new pathways while optimizing existing ones. Here, potential chemicals are added to create a superstructure, then an algorithm is run to enumerate every feasible reaction stoichiometry through a mixed integer linear program (MILP). An optimal chemical reaction pathway, taking into account thermodynamic, safety, and economic constraints is then found through reaction network flux analysis (RNFA). The RNFA is first formulated as a linear programming problem (LP) and later recast as an MILP in order to solve multiple alternate optima through integer cuts. A graphical method is also developed in order to show a shortcut method based on thermodynamics as opposed to the reaction stoichiometry enumeration and RNFA methods. A hypothetical case study, based on the conversion of woody biomass to liquid fuels, is presented at the end of the work along with a more detailed look at the glucose and xylose to 2-mthyltetrahydrofuran (MTHF) biofuel production pathway.

A DNA microarray is a very good tool to study the gene expression level in different situations. Mining association rules in DNA microarray datasets can help us know how genes affect each other, and what genes are usually co-expressed. Mining closed large itemsets can be useful for reducing the size of the mining result from the DNA microarray datasets, where a closed itemset is an itemset that there is no superset whose support value is the same as the support value of this itemset. Since the number of genes stored in columns is much larger than the number of samples stored in rows in a DNA microarray dataset, traditional mining methods which use column enumeration face a great challenge, where the column enumeration means that enumerating itemsets from the combinations of items stored in columns. Therefore, several row enumeration methods, e.g., RERII, have been proposed to solve this problem, where row enumeration means that enumerating itemsets from the combinations of items stored in rows. Although the RERII method saves more memory space and has better performance than the other row enumeration methods, it needs complex intersection operations at each node of the row enumeration tree to generate the closed itemsets. In this thesis, we propose a new method, UMiner, which is based on the union operations to mine the closed large itemsets in the DNA microarray datasets. Our approach is a row enumeration method. First, we add all tuples in the transposed table to a prefix tree, where a transposed table records the information about where an item appears in the original table. Next, we traverse this prefix tree to create a row-node table which records the information about a node and the related range of its child nodes in the prefix tree created from the transposed table. Then we generate the closed itemset by using the union operations on the itemsets in the item groups stored in the row-node table. Since we do not use the intersection operations to generate the closed itemset for each enumeration node, we can reduce the time complexity that is needed at each node of the row enumeration tree. Moreover, we develop four pruning techniques to reduce the number of candidate closed itemsets in the row enumeration tree. By replacing the complex intersection operations with the union operations and designing four pruning techniques to reduce the number of branches in the row enumeration tree, our method can find closed large itemsets very efficiently. In our performance study, we use three real datasets which are the clinical data on breast cancer, lung cancer, and AML-ALL. From the experiment results, we show that our UMiner method is always faster than the RERII method in all support values, no matter what the average length of the closed large itemsets is. Moreover, in our simulation result, we also show that the processing time of our method increases much more slowly than that of the RERII method as the average number of items in the rows of a dataset increases.

The k-core of a graph is its maximal subgraph with minimum degree at least k. The study of k-cores in random graphs was initiated by Bollobás in 1984 in connection to k-connected subgraphs of random graphs. Subsequently, k-cores and their properties have been extensively investigated in random graphs and hypergraphs, with the determination of the threshold for the emergence of a giant k-core, due to Pittel, Spencer and Wormald, as one of the most prominent results. In this thesis, we obtain an asymptotic formula for the number of 2-connected graphs, as well as 2-edge-connected graphs, with given number of vertices and edges in the sparse range by exploiting properties of random 2-cores. Our results essentially cover the whole range for which asymptotic formulae were not described before. This is joint work with G. Kemkes and N. Wormald. By defining and analysing a core-type structure for uniform hypergraphs, we obtain an asymptotic formula for the number of connected 3-uniform hypergraphs with given number of vertices and edges in a sparse range. This is joint work with N. Wormald. We also examine robustness aspects of k-cores of random graphs. More specifically, we investigate the effect that the deletion of a random edge has in the k-core as follows: we delete a random edge from the k-core, obtain the k-core of the resulting graph, and compare its order with the original k-core. For this investigation we obtain results for the giant k-core for Erdős-Rényi random graphs as well as for random graphs with minimum degree at least k and given number of vertices and edges.

This thesis details a method of enumerating bases of hyperplane arrangements up to symmetries. I consider here automorphisms, geometric symmetries which leave the set of all points contained in the arrangement setwise invariant. The algorithm for basis enumeration described in this thesis is a backtracking search over the adjacency graph implied on the bases by minimum-ratio simplex pivots, pruning at bases symmetric to those already seen. This work extends Bremner, Sikiri c, and Sch urmann's method for basis enumeration of polyhedra up to symmetries, including a new pivoting rule for nding adjacent bases in arrangements, a method of computing automorphisms of arrangements which extends the method of Bremner et al. for computing automorphisms of polyhedra, and some associated changes to optimizations used in the previous work. I include results of tests on ACEnet clusters showing an order of magnitude speedup from the use of C++ in my implementation, an up to 3x speedup with a 6-core parallel variant of the algorithm, and positive results from other optimizations.