From Daan
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.