The game of cops and robbers, played on a fixed graph G , is a two-player game, where the cop and the robber (the players) take turns in moving to adjacent vertices. The game finishes if the cop lands on the robber’s vertex. In that case we say that the cop wins. If the cop can always win, regardless of the starting positions, we say that G is a cop-win graph. For a finite cop-win graph G we can ask for the minimum number n such that, regardless of the starting positions, the game will end in at most n steps. This number is called the maximum capture time of G . By looking at finite paths, we see that any non-negative integer is the maximum capture time for a cop-win graph. What about infinite cop-win graphs? In this case, the notion of capture time is nicely generalised if one works with ordinals, and so the question becomes which ordinals can be the maximum capture time of a cop-win graph? These ordinals are called CR (Cop-Robber)-ordinals. In this paper we fully settle this by showing that all ordinals are CR-ordinals, answering a question of Bonato, Gordinowicz and Hahn.

Abstract. How small can a set of vertices in the [Formula: see text]-dimensional hypercube [Formula: see text] be if it meets every copy of [Formula: see text]? The asymptotic density of such a set (for [Formula: see text] fixed and [Formula: see text] large) is denoted by [Formula: see text]. It is easy to see that [Formula: see text], and it is known that [Formula: see text] for [Formula: see text], but it was recently shown that [Formula: see text] for [Formula: see text]. In this paper, we show that the latter phenomenon also holds for [Formula: see text] and [Formula: see text].

A (finite or infinite) graph is called constructible if it may be obtained recursively from the one-point graph by repeatedly adding dominated vertices. In the finite case, the constructible graphs are precisely the cop-win graphs, but for infinite graphs the situation is not well understood. One of our aims in this paper is to give a graph that is cop-win but not constructible. This is the first known such example. We also show that every countable ordinal arises as the rank of some constructible graph, answering a question of Evron, Solomon and Stahl. In addition, we give a finite constructible graph for which there is no construction order whose associated domination map is a homomorphism , answering a question of Chastand, Laviolette and Polat. Lehner showed that every constructible graph is a weak cop win (meaning that the cop can eventually force the robber out of any finite set). Our other main aim is to investigate how this notion relates to the notion of ‘locally constructible’ (every finite graph is contained in a finite constructible subgraph). We show that, under mild extra conditions, every locally constructible graph is a weak cop win. But we also give an example to show that, in general, a locally constructible graph need not be a weak cop win. Surprisingly, this graph may even be chosen to be locally finite. We also give some open problems.