UCLA

We present a series of results on the theme of using computational complexity to analyzecombinatorial objects with algebraic significance.

Chapter 1 concerns the cogrowth sequence of nilpotent groups. We prove that congruencesof such sequences are undecidable in general. We then show that related problems in analytic combinatorics are uncomputable as well. This is done by constructing matrices of size ≤ 10^86 which create a universal Turing machine.

In Chapter 2 we present negative results to versions of questions posed by Sergey Fominon quiver mutation equivalence. We do this by embedding versions of classic computationally difficult problems into quivers. Finally, we give a quick characterization of mutation classes of quivers with two mutable vertices as a contrast.

Chapters 3 and 4 are centered around the use of involutions to count posets. We give tightbounds for the number of posets of height 2 with an odd number of linear extensions, shedding new light on a conjecture of Chan and Pak. Then, we give a combinatorial interpretation (and corresponding positivity result) of area generating functions of partitions evaluated at −1.