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.

101 Philosophy Problems Part 3 - Protagoras

Problem 3 is very similar in nature to problem 1 - it's just another classical, and mildly more complicated rewording of the Epimenides paradox (actually, I think it's probably Russel's paradox). Anyway, it was so uninteresting that it's taken me three month to write this, but here goes:

Protagoras was a lawyer, and a teacher. He was a teacher so confident in his own abilities that he used to agree very unorthodox remuneration packages with his students - with one, Euathlus, he agreed that he would receive *no* payment unless the student won his first case. Having completed his training, Euathlus decided that he didn't want the shame of losing a case, but he also didn't want the cost of paying Protagoras: his solution? Don't take on any cases.

Protagoras' was not happy with this turn of events, and decided to sue for his tuition fee. His argument was simple. If Eualthus won, he had won his first case, and must pay Protagoras. If he lost, then he had to pay Protagoras by order of the court. Either way, Protagoras must be paid.

Eualthus, however, had obviously been listening in his lessons. He argued that if he won, he did not have to pay Protagoras, by order of the court. However, if he lost, he clearly would not have to pay by virtue of their agreement.

To me this has never seemed either very interesting or very paradoxical - Eualthus should win, as he hasn't yet won a case. Then Protagoras can sue him *afterwards* for the tuition fee (as Eualthus will now have won his first case). However, if we are to take the paradox at face value, it is simply another liar paradox, which we will meet again, and discuss at greater length at that juncture.