UCLA

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.