This dissertation is a contribution to two classical areas of graph theory, partitioning the vertex set of a graph into disjoint cycles, and packing trees into graphs. In addition to the original results which appear in two papers, we provide a historical background of each topic and a unifying perspective. Chapter 1 contains historical background going back to Euler, Hamilton, and Cayley who can be considered some of the fathers of these topics. Chapter 2 includes two surveys that show the development of both topics. These surveys contain preliminary results needed in the foregoing. Chapter 3 contains our contribution to the area of disjoint cycles. It is motivated by the following conjecture of El-Zahar. If G is a graph of order n ＝ n1 ＋ n2 ＋ &middot；&middot；&middot； ＋ nk with n2 &ge； 3 1 &le； i &le； k) and the minimum degree of G is at least n1/2＋ n2/2＋&dot；&dot；&dot；＋ nk/2 , then G contains k independent cycles of lengths n1, n2, …, nk, respectively. Several previous results toward the resolution of this conjecture have been attained by Dirac, Corradi and Hajnal, and Wang. Our contribution settles the case where n 1 ＝ n2 ＝ &middot；&middot；&middot； ＝ ns ＝3 1 &le； s &le； k) and ns＋1 ＝ ns ＋2 ＝ &middot；&middot；&middot； ＝ nk ＝ 5. Chapter 4 contains our contribution to the tree packing problem which is motivated in part by the observation that trees with large maximum degree are the major obstacle for achieving the packing. Continuing previous works of Bollabas, Wang, and Sauer and Spencer we prove that two trees T1 and T2 of order n, with Delta ＝ max {Delta T1), Delta T2)}, can be packed into a graph with restrained maximum degree. In particular, we show there is a packing a such that Delta T1 &cup； sigmaT2)) &le； Delta ＋ 2.

In this dissertation we investigate two main topics: minor-minimally 3-connected matroids and characteristic polynomials. Chapter 1 provides a survey of basic concepts from matroid theory that will be referenced in later chapters. The remainder of this dissertation includes the main results, their proofs, as well as motivation of these results. A 3-connected matroid M is minor-minimally 3-connected if, for every e &isin； EM), either M\e or M/e is not 3-connected. In Chapter 2, we review several theorems concerning minor-minimally 3-connected matroids. We also consider a conjecture of Wagner, which is the motivation of our research in this area. We provide a counterexample to Wagners conjecture in this chapter. In Chapter 3 we introduce and prove our main result concerning minor-minimally 3-connected binary matroids. This is a chain-type theorem that offers a characterization of minor-minimally 3-connected binary matroids. As a consequence, one can generate all minor-minimally 3-connected binary matroids starting from MK4 ), the graphic matroid of the complete graph with four vertices, the Fano matroid F7, and its dual. The characteristic polynomial of a rank r matroid M with ground set E is defined as cM,x＝ X&sube；E-1 Xxr-r X. The characteristic polynomial PG x) of a graphic matroid MG) is related to the chromatic polynomial of G by the equation PGx＝xw Gc MG,x where oG) is the number of components of G. In Chapter 4, we present existing results concerning these polynomials, and we prove a broken-circuit theorem for matroids. In Chapter 5, we give new upper and lower bounds for the coefficients of the characteristic polynomial of simple binary matroids. New bounds for the coefficients of the flow polynomials of graphs can be obtained as a direct consequence.

Independence Polynomials have been introduced several times, independently and with various names [6, 8, 9], beginning in the early 1980s. Applications have been found in Molecular Chemistry and Statistical Physics. The purposes of this dissertation include the derivation of tight upper and lower bounds for the coefficients of the independence polynomial of a k-tree: n-ks-1 s &le；fsT kn&le； n-k s where Tkn is a k-tree with n vertices and fs is the coefficient of xs in the independence polynomial of Tkn . All instances of equality at the upper and lower bounds are determined. This result generalizes a theorem of Wingard [21] corresponding to k ＝ 1. A second focus of this dissertation is the exact determination of the independence polynomials in several classes of k-trees, including k, n)-paths, k, n)-stars, and k, n)-spirals, and in some graphs which are closely related to k-trees. These include k, n)-cycles and k, n)-wheels. A third focus is the determination of the independence polynomial in a certain class of well-covered graphs. These graphs are described by a construction in Chapter 4 and their independence polynomials are computed using a very general theorem. In cases where the polynomial can be determined in closed form and its coefficients determined separately, the independence polynomial is used to generate some new combinatorial identities. Finally, the independence structure of the line graph of a 2 x n lattice is considered. While the exact determination of the polynomial remains an open question, the fibonacci number of this graph, that is, the sum of the coefficients of its polynomial, is determined precisely for all n. At the end of this dissertation, some further related research problems are proposed.

Let G be a connected and simply connected semisimple algebraic group over an algebraically closed field of positive prime characteristic. Let L(lambda) and Delta(lambda) be the simple and induced finite dimensional rational G-modules with p-singular dominant highest weight lambda. In this thesis, the concept of Weyl filtration dimension of a finite dimensional rational G-module is studied for some highest weight modules with p-singular highest weights inside the p 2-alcove when G is of type B 2. In Chapter 4, intertwining morphisms, a diagonal G-module morphism and tilting modules are used to compute the Weyl filtration dimension of L(lambda) with lambda p-singular and inside the p2 -alcove. It is shown that the Weyl filtration dimension of L(lambda) coincides with the Weyl filtration dimension of Delta(lambda) for almost all (all but one of the 6 facet types) p-singular weights inside the p2-alcove. In Chapter 5 we study some submodule structures of Weyl (and there translations), Vogan, and tilting modules with both p-regular and p-singular highest weights. Most results are for the p2-alcove only although some concepts used are alcove independent.

Let R be a complete rank-1 valuation ring of mixed characteristic (0,p), and let K be its field of fractions. A g-dimensional truncated Barsotti-Tate group G of level n over R is said to have a level-n canonical subgroup if there is a K-subgroup of G &otimes；R K with geometric structure ( Z/pnZ)g consisting of points “closest to zero”. We give a nontrivial condition on the Hasse invariant of G that guarantees the existence of the canonical subgroup, which is analogous to a result of Katz and Lubin for elliptic curves.

Since their introduction by Konheim and Weiss, parking functions have evolved into objects of surprising combinatorial complexity for their simple definitions. First, we introduce these structures, give a brief history of their development and give a few basic theorems about their structure. Then we examine the internal structures of parking functions, focusing on the distribution of descents and inversions in parking functions. We develop a generalization to the Catalan numbers in order to count subsets of the parking functions. Later, we introduce a generalization to parking functions in the form of k-blocked parking functions, and examine their internal structure. Finally, we expand on the extension to the Catalan numbers, exhibiting examples to explore its internal structure. These results continue the exploration of the deep structures of parking functions and their relationship to other combinatorial objects.

Most public key cryptosystems used in practice are based on integer factorization or discrete logarithms in finite fields or elliptic curves). However, these systems suffer from two potential drawbacks. First, they must use large keys to maintain security, resulting in decreased efficiency. Second, if large enough quantum computers can be built, Shors algorithm will render them completely insecure. Multivariate public key cryptosystems MPKC) are one possible alternative. MPKC makes use of the fact that solving multivariate polynomial systems over a finite field is an NP-complete problem, for which it is not known whether there is a polynomial algorithm on quantum computers. The main goal of this work is to show how to use new mathematical structures, specifically polynomial identities from algebraic geometry, to construct new multivariate public key cryptosystems. We begin with a basic overview of MPKC and present several significant cryptosystems that have been proposed. We also examine in detail some of the most powerful attacks against MPKCs. We propose a new framework for constructing multivariate public key cryptosystems and consider several strategies for constructing polynomial identities that can be utilized by the framework. In particular, we have discovered several new families of polynomial identities. Finally, we propose our new cryptosystem and give parameters for which it is secure against known attacks on MPKCs.

Multilayer composite structures are used in a wide variety of applications, from sporting goods to aerospace engineering and in robotic arms and floor joists. A common design for a multilayer composite structure consists of n ＝ 2m ＋ 1 layers, in which m＋1 stiff layers are bound together by m shear-deformable layers. It has been known for 50 years that the shear motion in the compliant layers is responsible for most of the damping of flexural vibrations. We consider multilayer beam and plate models in which linear viscous shear damping is included in the shear-deformable layers. We formulate the equations of motion for such a structure as a partial differential equation (PDE) semigroup problem, and we use the theory of PDE semigroups to prove stability results for damped multilayer beams and plates. In particular, we show that the semigroups associated multilayer beam and plate models of Mead and Markus are both analytic and exponentially stable, and we show that the semigroup associated with the multilayer beam of Rao and Nakra is exponentially stable under certain conditions. In addition, we consider two optimal damping problems for the multilayer Mead-Markus beam: (i) choosing damping parameters in the shear-deformable layers to achieve the optimal angle of analyticity, and (ii) choosing damping parameters in the shear-deformable layers to achieve the optimal energy decay rate.

Given two graphs G and H sharing the same vertex set, the edge-intersection spectrum of G and H is the set of possible sizes of the intersection of the edge sets of both graphs. For example, the spectrum of two copies of the cycle C5 is {0, 2, 3, 5}, and the spectrum of two copies of the star K1,r is {1, r}. The intersection spectrum was initially studied for designs by Lindner and Fu and others and was originally extended to graphs by Eric Mendelsohn. Several examples are studied, both when G and H are isomorphic and when they are not isomorphic. It will also be shown any set S of positive integers is the edge-intersection spectrum of some pair of connected graphs. The other two chapters cover the area of conflict-tolerance graph representations. These representations consist of rules for measuring the rank and tolerance of each vertex, and for determining if two vertices are in conflict, by combining and comparing the ranks and tolerances of the vertices. The edge set of the graph is then the pairs of vertices which are in conflict. In the odd-intersection interval model, each vertex is represented by a subpath of a host path P, and two vertices are in conflict if and only if their corresponding subpaths intersect in an odd number of nodes. This model is not universal； in particular, the complete 4-partite graph K3,3,3,3 is a minimal forbidden subgraph. The parity of the subpaths affects the representation； graphs in which the subpaths are of a fixed odd order are strongly chordal in fact, these are precisely the unit interval graphs), and graphs in which the subpaths are all of even order are bipartite. The converse of the latter statement is not true, as it will be shown that the number of bipartite graphs is asymptotically larger than the number of possible representations. A cross-comparison graph model is one in which each vertex v is assigned a rank rv and a tolerance tv, and two vertices u and v are in conflict if rv &ge； tu and ru &ge； t v. Jamison showed that the cross-comparison model is universal, using n-dimensional vectors and coordinatewise comparison to represent a graph on n vertices. The inefficiency of a vector representation is the smallest number of dimensions d for which we can represent a graph G using d-dimensional vectors. The set of all graphs which can be represented using one-dimensional vectors efficient cross-comparison graphs) is precisely the set of graphs which are the complement of a threshold tolerance graph known as co-TT graphs ； these were defined by Monma, Reed, and Trotter in [31]). The efficient cross-comparison graphs are characterized as those graphs which are chordal, and contain no strongly asteroidal triple – a set of three vertices, such that there is a path between any two of these vertices which contains no neighbor of the third, and which does not contain two consecutive vertices adjacent to every neighbor of the third. In addition, a graph with a d-dimensional vector representation is the intersection of d efficient graphs. The inefficiency of G is bounded below by its chordality, and above by its boxicity； both of these bounds are tight. In addition, the graph Kn2) has chordality and boxicity and thus inefficiency) equal to n, and this is known to be the upper bound for boxicity, which shows that the efficiency of a graph is at most half its order, and that this bound is tight.

Recently, Olver and Pohjanpelto have successfully extended the theory of equivariant moving frames to infinite-dimensional Lie pseudo-groups. Based on its finite-dimensional counterpart, this new theory promises to be a source of interesting new results and applications. In this thesis, we look at two applications of this new theory. By combining the powerful theories of Lie groupoids and variational bicomplexes, Olver and Pohjanpelto have developed a practical algorithm for determining the Maurer–Cartan structure equations of Lie pseudo-groups. The structure equations obtained with this new theory are compared with those derived by Cartan. It is shown that for transitive Lie pseudo-groups the two structure theories are isomorphic while for intransitive Lie pseudogroups the two sets of structure equations do not agree. To make the two structure theory isomorphic we argue that Cartans structure equations need to be slightly modified. The effect of this modification on Cartans definition of essential invariants is analyzed. In 1965, Singer and Sternberg gave an infinitesimal interpretation of Cartans structure equations for transitive Lie pseudo-groups. This interpretation is extended to intransitive Lie pseudo-groups and the result is used to state a symmetry-based linearization theorem for systems of nonlinear partial differential equations which does not require the integration of the infinitesimal determining equations of the symmetry group. The theory of equivariant moving frames is a powerful tool for determining a generating set of the differential invariant algebra of Lie pseudo-groups. After reviewing this theory, the method is illustrated with three applications. In the first two applications, generating sets of differential invariant algebra for the symmetry groups of the Infeld–Rowlands equation and the Davey–Stewartson equations are determined. Then we show that for two and three dimensional Riemannian manifolds the sectional curvatures generate the differential invariant algebra of the pseudo-group of locally invertible changes of variables.