Content area
Abstract
We present a series of results on the theme of using computational complexity to analyze combinatorial objects with algebraic significance.
Chapter 1 concerns the cogrowth sequence of nilpotent groups. We prove that congruences of 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 ≤ 1086 which create a universal Turing machine.
In Chapter 2 we present negative results to versions of questions posed by Sergey Fomin on 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 tight bounds 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.
