Let me remark that much more is now known about the topics that are covered in that preprint. A starting point is Vatter's recent survey article http://arxiv.org/abs/1409.5159

@Paul What I was trying to say is that we can do this in effectively constant time per item (I think that's correct - may take a bit of work to avoid adding items to the queue on multiple occasions - but it's certainly right if we're treating N as a constant). So if the objective is "list the first 1000 points" that's easily done. If it is "tell me the 1000^th point" then it's less clear.

We have to be a bit careful using phrases like "NP-complete" here, since, as posed, the problem isn't really in the right form. Would it also be possible to clarify - do you really want an algorithm that uses say O(N) memory beyond the initial data? [Otherwise we're just solving shortest path problems from a single source in the obvious graph, and the usual queue based approaches will be O(1) time per item output.]

No, we didn't really consider such games. As the heart of the argument is a symbolic representation of a game state based on encoding the "bumping" algorithms for finding longest increasing and decreasing subsequences, it's not clear to me how one would emulate it. Of course the general idea of looking for a strategy stealing argument would certainly be a line to pursue.

I don't understand how the graphs can be connected at every stage. Do you mean that there is at most one non-singleton component? If so (and I guess that's it) then ignore my comment about Cayley's theorem!

Typo, I think you mean $p(k)$ in the definition. The formula doesn't feel quite right, but should follow from Cayley's formula for labelled trees on $n$ vertices (in this process, when $n$ edges have been added we're asking for a tree plus an edge.)

There may be copyright issues with an arXiv submission, but at least at a first reading of the help files there it does not seem to be out of scope. I'd suggest contacting the arXiv administrators for further clarification.

Absolutely the correct answer to the question as asked. For more detailed statistics, the Goulden-Jackson cluster method (which is hard to explain in a comment - but the phrase is a good start for google) could be used in this, and many similar contexts.

Such objects are called Latin squares.