most recent 30 from http://mathoverflow.net 2013-05-19T09:11:23Z http://mathoverflow.net/feeds/question/26599 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/26599/complexity-of-counting-homomorphisms Eric Rowell 2010-05-31T16:17:07Z 2010-06-01T17:35:48Z

<p>This is a question I have thought about and asked a number of people, but have never got an answer beyond "It should be true that..."</p> <p>Given a finitely generated group $G$ (eg. a link group $G_L:=\pi_1(S^3-L)$ for a link $L$) and a finite group $H$ we want to count homomorphisms from $G$ to $H$. For link groups as above, this is an invariant of $L$. </p> <p>My question: (for which $H$) is there a polynomial-time algorithm (in the number of generators and relations for $G$) for computing $N(G,H):=|Hom(G,H)|$ (particularly for $G_L$)?</p> <p>Some things I know: 1) If $L$ is a knot and $H$ is nilpotent then $N(G_L,H)$ is constant (<a href="https://www.ams.org/journals/proc/2000-128-05/S0002-9939-99-05287-9/home.html" rel="nofollow">M. Eisermann</a>) 2) <a href="http://doi:10.1016/j.jalgebra.2005.01.009" rel="nofollow">D. Matei; A. I. Suciu,</a> have an algorithm for solvable $H$, but the complexity is not clear. 3) The abelianization of $G_L$ is just $Z^c$, $c$ the number of components, so for $H$ abelian it is easy.</p> <p>A wild conjecture is that it should always be "FPRASable" i.e. there exists a fully polynomial randomized approximation scheme for the computation.</p>

http://mathoverflow.net/questions/26599/complexity-of-counting-homomorphisms/26742#26742 Agol 2010-06-01T17:11:25Z 2010-06-01T17:35:48Z

<p>For $G$ a knot group, and for $H$ a dihedral group, there should be a simple algorithm for counting the number of homomorphisms. The meridians of $G$ normally generate, and are all conjugate, so they must be sent to conjugate elements in $H$. If they are sent to the cyclic subgroup of index 2, then the image is cyclic, and this is easy to count. </p> <p>If a meridian is sent to an involution, then an index 2 subgroup of $G$ is sent to a cyclic group. This amounts to computing the homology of the 2-fold branched cover of the knot, together with the action of the involution on this homology. This is certainly polynomial-time computable, and I'm pretty sure one can determine its dihedral quotients easily. In any case, at least this reduces it to the problem of finding dihedral quotients of abelian-by-$\mathbb{Z}/2$ groups. </p>