Motivated by primality and integer factorization, this thesis introduces generalizations of standard binary multiplication to commutative n-ary operations based upon geometric construction and representation. This class of operations are constructed to preserve commutativity and identity so that binary multiplication is included as a special case, in order to preserve relationships with ordinary multiplicative number theory. This leads to a study of their expression in terms of elementary symmetric polynomials, and connections are made to results from the theory of polyadic (n-ary) groups. Higher order operations yield wider factorization and representation possibilities which correspond to reductions in the set of primes as well as tiered notions of primality. This comes at the expense of familiar algebraic properties such as associativity, and unique factorization. Criteria for primality and a naive testing algorithm are given for the ternary arithmetic, drawing heavily upon modular arithmetic. Finally, connections with the theory of partitions of integers and quadratic forms are discussed in relation to questions about cardinality of primes.

This paper develops a data structure based on preimage sets of functions on a finite set. This structure, called the sigma matrix, is shown to be particularly well-suited for exploring the structural characteristics of recursive functions relevant to investigations of complexity. The matrix is easy to compute by hand, defined for any finite function, reflects intrinsic properties of its generating function, and the map taking functions to sigma matrices admits a simple polynomial-time algorithm . Finally, we develop a flexible measure of preimage complexity using the aforementioned matrix. This measure naturally partitions all functions on a finite set by characteristics inherent in each function's preimage structure.

This dissertation is divided into four chapters. In Chapter 2 the equivariant homology groups of upper order ideals in the partition lattice are computed. The homology groups of these filters are written in terms of border strip Specht modules as well as in terms of links in an associated complex in the lattice of compositions. The classification is used to reproduce topological calculations of many well-studied subcomplexes of the partition lattice, including the d-divisible partition lattice and the Frobenius complex. In Chapter 3 the box polynomial B_{m,n}(x) is defined in terms of all integer partitions that fit in an m by n box. The real roots of the box polynomial are completely characterized, and an asymptotically tight bound on the norms of the complex roots is also given. An equivalent definition of the box polynomial is given via applications of the finite difference operator Delta to the monomial x^{m+n}. The box polynomials are also used to find identities counting set partitions with all even or odd blocks, respectively. Chapter 4 extends results from Chapter 3 to give combinatorial proofs for the ordinary generating function for set partitions with all even or all odd block sizes, respectively. This is achieved by looking at a multivariable generating function analog of the Stirling numbers of the second kind using restricted growth words. Chapter 5 introduces a colored variant of the ordered partition lattice, denoted Q_n^{\alpha}, as well an associated complex known as the alpha-colored permutahedron, whose face poset is Q_n^\alpha. Connections between the Eulerian polynomials and Stirling numbers of the second kind are developed via the fibers of a map from Q_n^{\alpha} to the symmetric group on n-elements

In a 2011 paper by Beeler and Hoilman, the game of peg solitaire is generalized to arbitrary boards. These boards are treated as graphs in the combinatorial sense. An open problem from that paper is to determine the minimum number of edges necessary for a graph with a fixed number of vertices to be solvable. This thesis provides new bounds on this number. It also provides necessary and sufficient conditions for two families of graphs to be solvable, along with criticality results, and the maximum number of pegs that can be left in each of the two graph families.

A set S of vertices in a graph G=(V,E) is a dominating set if every vertex in V\S is adjacent to at least one vertex in S, and the minimum cardinality of a dominating set of G is the domination number of G. A vertex v in a dominating set S is said to be very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is very cost effective if every vertex in S is very cost effective. The minimum cardinality of a very cost effective dominating set of G is the very cost effective domination number of G. We first give necessary conditions for a graph to have equal domination and very cost effective domination numbers. Then we determine an upper bound on the very cost effective domination number for trees in terms of their domination number, and characterize the trees which attain this bound. lastly, we show that no such bound exists for graphs in general, even when restricted to bipartite graphs.

In this paper, we consider decompositions of the complete graph on v vertices into 4-cycles with a pendant edge. In part, we will consider decompositions which admit automorphisms consisting of: (1) a single cycle of length v, (2) f fixed points and a cycle of length v − f, or (3) two disjoint cycles. The purpose of this thesis is to give necessary and sufficient conditions for the existence of cyclic, f-cyclic, and bicyclic Q-decompositions of Kv.

There are four orientations of cycles on four vertices. Necessary and sufficient conditions are given for covering complete directed digraphs Dv, packing and covering complete bipartite digraphs, Dm,n, and packing and covering the complete digraph on v vertices with hole of size w, D(v,w), with three of the orientations of a 4-cycle, including C4, X, and Y.

The alphabet overlap graph is a modification of the well known de Bruijn graph. De Bruijn graphs have been highly studied and hence many properties of these graphs have been determined. However, very little is known about alphabet overlap graphs. In this work we determine the chromatic number for a special case of these graphs. We define the alphabet overlap graph by G = AO(a, k, t, where a, k and t are positive integers such that 0 ≤ t ≤ k. The vertex set of G is the set of all k-letter sequences over an alphabet of size a. Also there is an edge between vertices u, v if and only if the last t letters in u match the first t letters in v or the first t letters in u match the last t letters in v. We consider the chromatic number for the AO(a, k, t graphs when k > 2, t = k - 1 and a = 2.

For a graph G=(V,E) and a set of vertices S, a vertex v in S is said to be very cost effective if it is adjacent to more vertices in V -S than in S. A bipartition pi={S, V- S} is called very cost effective if both S and V- S are very cost effective sets. Not all graphs have a very cost effective bipartition, for example, the complete graphs of odd order do not. We consider several families of graphs G, including Cartesian products and cacti graphs, to determine whether G has a very cost effective bipartition.

The Apprentices' Tower of Hanoi is introduced in this thesis. Several bounds are found in regards to optimal algorithms which solve the puzzle. Graph theoretic properties of the associated state graphs are explored. A brief summary of other Tower of Hanoi variants is also presented.