PPA & Hard Hamiltonian Graphs

Paper

Here is our paper.

Errata

The title of the paper is somewhat misleading; we're actually no looking for hard Hamiltonian graphs, but hard Hamiltonian problem instances, and the result of that are actually non-Hamiltonian graphs only.

On the first page it says "The hardest graphs reside in between, right around the Komlos-Szemeredi bound of average degreev·ln(v) +v·ln(ln(v)) edges". This is a mixeup. There are two possibilities:

1) The hardest graphs reside in between, right around the Komlos-Szemeredi bound of average degree ln(v) +ln(ln(v)).

2) The hardest graphs reside in between, right around the Komlos-Szemeredi bound of 1/2v·ln(v) + 1/2v·ln(ln(v)) edges.