This dissertation investigates the difficulty of counting two classes of combinatorial objects, linear extensions of posets and contingency tables. For linear extensions of posets, we prove a number of hardness results. We show that computing the parity of the number of linear extensions of dimension two is parity-P-complete. We extend this result to show that counting linear extensions of dimension two posets is #P-complete, answering a question posed by M�hring and by Felsner and Wernisch. We also show that counting linear extensions of height two posets is #P-complete, resolving a conjecture of Brightwell and Winkler. We extend this result to show that incidence posets are #P-complete.

For the results about posets of dimension two we employed a computer search to construct families of permutations that behave as logic gates in a certain setting. The results about height two posets and incidence posets rely instead on gadgets that were constructed by hand.

For contingency tables, we work from the opposite direction, proving results about the feasibility of approximately counting and sampling tables. We give a new algorithm for approximating the number of contingency tables with fixed margins, which we call the SHM algorithm. We prove that the SHM algorithm is a fully polynomial random approximation scheme (FPRAS) for the number of tables for certain families of sparse margins. We then use this result to establish a polynomial mixing time for the Diaconis-Gangolli chain with sparse margins.

Using our SHM algorithm and techniques in discrete probability, we present experimental and theoretical evidence in support of answers to a number of questions Barvinok posed about the distribution of individual entries in contingency tables. In particular, we show that for a certain set of margins considered by Barvinok, and under certain assumptions about weak independence of entries, the distribution of the corner table entry exhibits a phase transition in mean and distribution.

When does a topological polyhedral complex (embedded in R^d) admit a geometric realization (a rectilinear embedding in R^d)? What are the constraints on the possible realizations? Two classic results concerning such questions are Fary's theorem, which states that every planar graph can be drawn in the plane such that each edge is a straight line segment, and Tutte's theorem, which provides necessary and sufficient conditions for embedding a planar graph such that all faces are convex. The present work is motivated largely by the question of whether these types of results generalize to higher dimensions.

We begin by constructing an irrational polytopal complex consisting of 1278 convex 3-polytopes in R³. The methods of this construction may also be used to produce small topological complexes with no geometric realization, as well as geometric complexes which encode arbitrary point and line configurations. This allows us to prove universality theorems for 3-dimensional polytopal complexes and arrangements. We also investigate geometric realizations of plane triangulations, and describe an explicit algorithm that embeds a plane triangulation with n vertices in a 4n³ x 8n⁵ integer grid, in such a way that at each step of the algorithm, the resulting region of the plane is convex. This embedding, by nature of its sequential convexity, may be lifted vertically to a 3-polytope. This process gives a new proof of Steinitz's Theorem for triangulations, and provides a new upper bound on the size of the integer grid necessary to embed the vertices of simplicial 3-polytopes. For certain classes of triangulations, this grid size is subexponential.

Diptera has more species with an aquatic stage than any other insect group, yet their evolutionary history and its association with other traits, like blood feeding and marine dwelling, remain unknown. A comprehensive phylogeny of Diptera (flies) has recently been proposed, allowing for studies of adaptations across this diverse group. Ancestral state reconstruction analyses suggest marine dwelling is not an ancestral trait in the most recent common ancestor to Diptera. In addition, several families (e.g. Culicidae and Canacidae) of flies have independently adapted to saltwater found in the marine environment. For example, Canacidae (beach flies) is a cosmopolitan family that includes species that are found in intertidal ecosystems where their larvae feed on algae. The genus Procanace, in particular, offers the opportunity to study biogeography and the adaptation to novel freshwater environments. In this dissertation, a phylogeny of Procanace and relatives is reconstructed, based on multiple mitochondrial and nuclear DNA sequences from 15 species representing 5 genera. The reconstructed phylogeny supports the monophyly of the Procanace genus, which confirms previous taxonomic studies. In addition, the reconstructed phylogeny suggests that canacids colonized Hawai’i twice, once by an ancestor of Procanace and again by an ancestor of Canaceoides. Speciation patterns within the genus Procanace follow the progression rule and demonstrate a single switch from saltwater to freshwater habitats in the Hawaiian Islands. Although understudied, these flies may yield insights into freshwater invasions and pathways behind osmoregulatory systems. This dissertation also examines the evolution of aquatic life histories and their associations with blood-feeding across Diptera. The most recent common ancestor of Diptera is likely to have had an aquatic (but not marine) life history. When examing aquatic life history in relation to blood-feeding, we found that blood-feeding behaviors often occur in fly lineages that also have aquatic life histories, but not significantly more often. This pattern suggests that, in some cases, adaptations to larval aquatic life history were a precursor for flies expanding their diets to take blood meals. This work builds on our understanding of the ecological and evolutionary history of aquatic Diptera and its associations with blood-feeding.

In eukaryotes, both mitochondrial and nuclear genes encode subunits of electron transport system (ETS) enzymes that must favorably interact (mitonuclear interactions) to produce metabolic energy. Therefore, mitochondrial and nuclear genes coevolve within populations such that hybrids bred from populations in different geographic locations may result in mitonuclear incompatibilities, leading to hybrid breakdown in numerous phenotypic traits. Current hybrid studies of intertidal copepods reveal the effects of mitonuclear interactions in the breakdown of developmental times, ATP production, and survival; however, the linkages amongst numerous phenotypic traits are still largely unknown. To determine the extent of breakdown of phenotypic traits and their linkages to one another, we recorded developmental times and monitored longevity after categorizing copepods into fast-developing and slow-developing groups. Contrary to previous studies, we found that mitonuclear incompatibilities did not greatly affect the developmental times in hybrids. Additionally, individuals from the slow-developing groups for each of the crosses showed higher survivorship to day 89 than the fast-developing group; i.e., there was an apparent tradeoff between early life stage developmental rates and longevity where fast-developing individuals displayed shorter lifespans compared to slow-developing individuals. Future studies should examine the effects of different rates of development on longevity and potentially when the tradeoff starts between fast early life stage development and a shorter lifespan. Other potential future directions include measuring different life history traits alongside longevity such as lifetime egg production in females.