No description available.

No description available.

Informally, a rooted map is a topologically pointed embedding of a graph in a surface. This thesis examines two problems in the enumerative theory of rooted maps. The b-Conjecture, due to Goulden and Jackson, predicts that structural similarities between the generating series for rooted orientable maps with respect to vertex-degree sequence, face-degree sequence, and number of edges, and the corresponding generating series for rooted locally orientable maps, can be explained by a unified enumerative theory. Both series specialize M(x,y,z;b), a series defined algebraically in terms of Jack symmetric functions, and the unified theory should be based on the existence of an appropriate integer valued invariant of rooted maps with respect to which M(x,y,z;b) is the generating series for locally orientable maps. The conjectured invariant should take the value zero when evaluated on orientable maps, and should take positive values when evaluated on non-orientable maps, but since it must also depend on rooting, it cannot be directly related to genus. A new family of candidate invariants, η, is described recursively in terms of root-edge deletion. Both the generating series for rooted maps with respect to η and an appropriate specialization of M satisfy the same differential equation with a unique solution. This shows that η gives the appropriate enumerative theory when vertex degrees are ignored, which is precisely the setting required by Goulden, Harer, and Jackson for an application to algebraic geometry. A functional equation satisfied by M and the existence of a bijection between rooted maps on the torus and a restricted set of rooted maps on the Klein bottle show that η has additional structural properties that are required of the conjectured invariant. The q-Conjecture, due to Jackson and Visentin, posits a natural combinatorial explanation, for a functional relationship between a generating series for rooted orientable maps and the corresponding generating series for 4-regular rooted orientable maps. The explanation should take the form of a bijection, ϕ, between appropriately decorated rooted orientable maps and 4-regular rooted orientable maps, and its restriction to undecorated maps is expected to be related to the medial construction. Previous attempts to identify ϕ have suffered from the fact that the existing derivations of the functional relationship involve inherently non-combinatorial steps, but the techniques used to analyze η suggest the possibility of a new derivation of the relationship that may be more suitable to combinatorial analysis. An examination of automorphisms that must be induced by ϕ gives evidence for a refinement of the functional relationship, and this leads to a more combinatorially refined conjecture. The refined conjecture is then reformulated algebraically so that its predictions can be tested numerically.

Informally, a rooted map is a topologically pointed embedding of a graph in a surface. This thesis examines two problems in the enumerative theory of rooted maps. The b-Conjecture, due to Goulden and Jackson, predicts that structural similarities between the generating series for rooted orientable maps with respect to vertex-degree sequence, face-degree sequence, and number of edges, and the corresponding generating series for rooted locally orientable maps, can be explained by a unified enumerative theory. Both series specialize M(x,y,z;b), a series defined algebraically in terms of Jack symmetric functions, and the unified theory should be based on the existence of an appropriate integer valued invariant of rooted maps with respect to which M(x,y,z;b) is the generating series for locally orientable maps. The conjectured invariant should take the value zero when evaluated on orientable maps, and should take positive values when evaluated on non-orientable maps, but since it must also depend on rooting, it cannot be directly related to genus. A new family of candidate invariants, η, is described recursively in terms of root-edge deletion. Both the generating series for rooted maps with respect to η and an appropriate specialization of M satisfy the same differential equation with a unique solution. This shows that η gives the appropriate enumerative theory when vertex degrees are ignored, which is precisely the setting required by Goulden, Harer, and Jackson for an application to algebraic geometry. A functional equation satisfied by M and the existence of a bijection between rooted maps on the torus and a restricted set of rooted maps on the Klein bottle show that η has additional structural properties that are required of the conjectured invariant. The q-Conjecture, due to Jackson and Visentin, posits a natural combinatorial explanation, for a functional relationship between a generating series for rooted orientable maps and the corresponding generating series for 4-regular rooted orientable maps. The explanation should take the form of a bijection, ϕ, between appropriately decorated rooted orientable maps and 4-regular rooted orientable maps, and its restriction to undecorated maps is expected to be related to the medial construction. Previous attempts to identify ϕ have suffered from the fact that the existing derivations of the functional relationship involve inherently non-combinatorial steps, but the techniques used to analyze η suggest the possibility of a new derivation of the relationship that may be more suitable to combinatorial analysis. An examination of automorphisms that must be induced by ϕ gives evidence for a refinement of the functional relationship, and this leads to a more combinatorially refined conjecture. The refined conjecture is then reformulated algebraically so that its predictions can be tested numerically.

We develop algebraic methods to solve join-cut equations, which are partial differential equations that arise in the study of permutation factorizations. Using these techniques, we give a detailed study of the recently introduced monotone Hurwitz numbers, which count factorizations of a given permutation into a fixed number of transpositions, subject to some technical conditions known as transitivity and monotonicity. Part of the interest in monotone Hurwitz numbers comes from the fact that they have been identified as the coefficients in a certain asymptotic expansion related to the Harish-Chandra-Itzykson-Zuber integral, which comes from the theory of random matrices and has applications in mathematical physics. The connection between random matrices and permutation factorizations goes through representation theory, with symmetric functions in the Jucys-Murphy elements playing a key role. As the name implies, monotone Hurwitz numbers are related to the more classical Hurwitz numbers, which count permutation factorizations regardless of monotonicity, and for which there is a significant body of work. Our results for monotone Hurwitz numbers are inspired by similar results for Hurwitz numbers; we obtain a genus expansion for the related generating functions, which yields explicit formulas and a polynomiality result for monotone Hurwitz numbers. A significant difference between the two cases is that our methods are purely algebraic, whereas the theory of Hurwitz numbers relies on some fairly deep results in algebraic geometry. Despite our methods being algebraic, it seems that there should be a connection between monotone Hurwitz numbers and geometry, although this is currently missing. We give some evidence for this connection by identifying some of the coefficients in the monotone Hurwitz genus expansion with coefficients in the classical Hurwitz genus expansion known to be Hodge integrals over the moduli space of curves.

NP-Hardness is a well-known theory to identify the hardness of computational problems. It is believed that NP-Hard problems are unlikely to admit polynomial-time algorithms. However since many NP-Hard problems are of practical significance, different approaches are proposed to solve them: Approximation algorithms, randomized algorithms and heuristic algorithms. None of the approaches meet the practical needs. Recently parameterized computation and complexity has attracted a lot of attention and been a fruitful branch of the study of efficient algorithms. By taking advantage of the moderate value of parameters in many practical instances, we can design efficient algorithms for the NP-Hard problems in practice. In this dissertation, we discuss a new approach to design efficient parameterized algorithms, kernelization. The motivation is that instances of small size are easier to solve. Roughly speaking, kernelization is a preprocess on the input instances and is able to significantly reduce their sizes. We present a 2k kernel for the cluster editing problem, which improves the previous best kernel of size 4k; We also present a linear kernel of size 7k 2d for the d-cluster editing problem, which is the first linear kernel for the problem. The kernelization algorithm is simple and easy to implement. We propose a quadratic kernel for the pseudo-achromatic number problem. This implies that the problem is tractable in term of parameterized complexity. We also study the general problem, the vertex grouping problem and prove it is intractable in term of parameterized complexity. In practice, many problems seek a set of good solutions instead of a good solution. Motivated by this, we present the framework to study enumerability in term of parameterized complexity. We study three popular techniques for the design of parameterized algorithms, and show that combining with effective enumeration techniques, they could be transferred to design efficient enumeration algorithms.

We develop algebraic methods to solve join-cut equations, which are partial differential equations that arise in the study of permutation factorizations. Using these techniques, we give a detailed study of the recently introduced monotone Hurwitz numbers, which count factorizations of a given permutation into a fixed number of transpositions, subject to some technical conditions known as transitivity and monotonicity. Part of the interest in monotone Hurwitz numbers comes from the fact that they have been identified as the coefficients in a certain asymptotic expansion related to the Harish-Chandra-Itzykson-Zuber integral, which comes from the theory of random matrices and has applications in mathematical physics. The connection between random matrices and permutation factorizations goes through representation theory, with symmetric functions in the Jucys-Murphy elements playing a key role. As the name implies, monotone Hurwitz numbers are related to the more classical Hurwitz numbers, which count permutation factorizations regardless of monotonicity, and for which there is a significant body of work. Our results for monotone Hurwitz numbers are inspired by similar results for Hurwitz numbers; we obtain a genus expansion for the related generating functions, which yields explicit formulas and a polynomiality result for monotone Hurwitz numbers. A significant difference between the two cases is that our methods are purely algebraic, whereas the theory of Hurwitz numbers relies on some fairly deep results in algebraic geometry. Despite our methods being algebraic, it seems that there should be a connection between monotone Hurwitz numbers and geometry, although this is currently missing. We give some evidence for this connection by identifying some of the coefficients in the monotone Hurwitz genus expansion with coefficients in the classical Hurwitz genus expansion known to be Hodge integrals over the moduli space of curves.

Thesis (M.S.)--Virginia Polytechnic Institute and State University, 1991. / Vita. Abstract. Includes bibliographical references (leaves 75-77). Also available via the Internet.

Thesis (Ph. D.)--Oregon State University, 1995. / Typescript (photocopy). Includes bibliographical references (leaves 52-54). Also available on the World Wide Web.

Graphlet enumeration is a basic task in graph analysis with many applications. Thus it is important to be able to perform this task within a reasonable amount of time. However, this objective is challenging when the input graph is very large, with millions of nodes and edges. Known solutions are limited in terms of scalability. Distributed computing is often proposed as a solution to improve scalability. How- ever, it has to be done carefully to reduce the overhead cost and to really benefit from the distributed solution. We study the enumeration of four-node graphlets in undirected graphs using a distributed platform. We propose an efficient distributed solution which significantly surpasses the existing solutions. With this method we are able to process larger graphs that have never been processed before and enumerate quadrillions of graphlets using a modest cluster of machines. We convincingly show the scalability of our solution through experimental results. / Graduate