From Daan
Jump to: navigation, search


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.