Tuesday, 15 April 2008

Graph Homomorphisms

So, it seems I finally have a project that could last a good while. Counting Graph Homomorphisms
modulo primes numbers. I've already done Independent Set, and when I finally get round to finishing the corrections on my paper, that's hopefully going to go up on ArXiv (I guess that X is supposed to be a chi, but I can't be bothered to figure out how to generate special characters, so I'm not going to).

So far, we know that counting graph homomorphisms exactly is hard (except when it's trivial), that counting colourings mod p is also hard (except when it's trivial), and that counting independent sets is hard. Conjecture: if H has trivial automorphism group, then counting the H-colouring problem is hard modulo p for all p. Actually, I guess that doesn't qualify as a conjecture yet - it's more of a speculation. So far the only evidence we have in favour is that we can't see why it wouldn't be true.

So, I'm off to read Dyer and Greenhill (paper is probably gated if you're not in an academic institution, and probably completely incomprehensible if you don't study computational complexity at at least postgraduate level). And hope that some of their proof techniques can be extended to my world.

No comments: