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.