The genus of partitions and c-trees: Boolean decompositions and the graphs, Pruefer codes and perfect matchings of genus 0 c-trees

This thesis studies the genus of set partitions and three aspects of c-trees constrained by genus: the graphs formed by trees of a particular genus, their Prüfer codes, and their perfect matchings. A c-tree is a tree drawn on n points arranged sequentially on a circle such that the edges of the tree lie inside the circle.; The lattice of genus 0 set partitions was shown by Kreweras to be self-dual and by Simion and Ullman to be decomposable into symmetrically embedded boolean sublattices. We provide an alternate description, the adjacent block decomposition, for the Simion-Ullman decomposition that relates it to a genus 0 c-tree that only joins adjacent points. We show that the operation of face/edge duality is an order-reversing isomorphism between the adjacent block decomposition and another decomposition, the star decomposition, that is related to a c-tree in which all edges are incident to a single vertex. After considering these two special cases, we show that in general any genus 0 tree corresponds to the maximal boolean lattice of a boolean decomposition.; Next we similarly decompose the genus 1 set partition poset. A corollary gives an identity similar to Touchard's. We also use the decomposition to count the number of connected genus 1 set partitions. We find that they have the same number of elements as a type of lattice path that we call jump paths (because the path can jump any size step rightward or upward except vertically).; Next we define the genus of a c-tree, and construct a graph $Tin$ of genus i c-trees on n points. In $T0n$, a certain configuration of two trees that are especially far apart establishes a lower bound for the diameter d, and we find that ; We characterize the center of $T0n$ as trees that (1) have a subchain joining consecutive points with leaves extending from the subchain; (2) have an edge in common with every other tree; (3) have no long nonpendant edges; or (4) have all leaves on adjacent points.; We prove that the graph of all quadrangulations of an n-gon is a subgraph of $T0n$. The quadrangulation graph is one of a family of graphs constructed from divisions of an n-gon into r-gons. The diameter of the triangulation graph was found by Sleator, Tarjan, and Thurston to be 2n − 10 for large n by volume estimates in hyperbolic geometry.; We prove that $T1n$ is connected.; We enumerate the initial values of the Prüfer codes of genus 0 c-trees and the number of c-trees that are perfectly matched.