Forgot your glasses

You’re an old blade runner trying to capture a rogue replicant but forgot your reading glasses and can’t see them clearly up close. That’s the idea for the mathematical game I’m going to describe.

There are two players, a set of cops (the blade runner) and a robber (the replicant), who are loose on a network or graph. They can move from vertex-to-vertex along edges, alternating moves, with the cops going first. If you know about the original game of Cops and Robbers, then this should sound familiar.

One big difference in the present game is that the robber is invisible—at least part of the time. We imagine the network edges correspond to competition, rivalry, or just plain enmity. For that reason, you can’t see what’s close to you, in the sense that you can’t see the robber when they are on one of your neighbors. If they are at least two steps away, then you can see them.  You can also see the robber if you are on their vertex.

The point of the game is to capture the robber by moving the cops so they land on them. How should the cops play on a graph like this one? How many hyperopic cops do we need to capture the robber?

There is no chance in the game, so the cops win only if they can guarantee the position of the robber. For example, in a triangle with three vertices all adjacent, one cop is not sufficient to win as they can’t guarantee which of the remaining two vertices contain the robber.

We call this game Hyperopic Cops and Robbers, as hyperopia is the condition of being farsighted. The minimum number of cops needed to guarantee a win in a graph G is the hyperopic cop number, denoted by c_H(G). If the cops capture the robber in Hyperopic Cops and Robbers, then they do so in the classical game of Cops and Robbers; hence, c(G) ≤ c_H(G), where c(G) is the cop number of G. For more on the cop number, see this previous post.

I proposed the game after hearing a talk at a conference where the robber is visible only if they are close to the cops. That is, the cops have a kind of limited visibility or are nearsighted. I realized after the talk that Hyperopic Cops and Robbers wasn’t a simple variation of having limited visibility; in particular, by exchanging edges and non-edges we couldn’t translate hyperopic cops into ones with limited visibility.

Working with my colleagues we arrived at the following paper:

A. Bonato, N.E. Clarke, D. Cox, S. Finbow, F. Mc Inerney, and M.E. Messinger, Hyperopic Cops and Robbers, arXiv 1710.10112

When hyperopia helps and hinders

Cliques are graphs where all vertices are adjacent, such as in the triangle graph above. In the usual game of Cops and Robbers, they are what is called cop-win: one cop is sufficient to capture the robber. Our triangle example above shows this is false for hyperopic cops. In fact, for a connected graph with n vertices, c_H(G) is at most the ceiling of n/2, and the unique connected graphs with maximum hyperopic cop number are cliques.

There are many examples of graphs G where c(G) = c_H(G). Trees are connected graphs with no cycles. Trees are examples of cop-win graphs.  We showed that one hyperopic cop can win precisely when they are trees, and these are the unique hyperopic cop-win graphs.

By an early result of Aigner and Fromme, planar graphs (i.e. those which can be drawn without edge crossings) have cop number at most three. We proved that cops playing on planar graphs have a lonely winning strategy: they can win the game and never occupy the same vertex during gameplay. This, along with the excluded subgraphs forced in planar graphs, gave us the result that the hyperopic cop number is also at most three. An analogous result is true for outerplanar graphs, which have cop number at most two.

So this tells us that the Tutte graph above has hyperopic cop number 3.

Diameter

The diameter of a graph is the maximum distance between all pairs of nodes, where distance is the length of a shortest path connecting them. Intuitively, if your graph has large diameter, then the cops should be able to see more of the network as the vertices are spread out. In fact, if your graph G is diameter at least 3, then you only need two more cops more than the cop number to win. That is, c_H(G) ≤ c(G) + 2. To see this, place two cops distance 3 apart in G. The robber is never joined to both of these cops and hence, remains visible throughout the game. The remaining c(G) cops can play as in Cops and Robbers and win.

We didn’t find an example of a graph G where c_H(G) = c(G) + 2. In fact, for many classes of graphs: triangle-free, graphs with cut vertices, or diameter at least three graphs where the cop number is at least the minimum degree, we have that c_H(G) = c(G) + 1.

In the diameter at most two graphs, the hyperopic cop number can be very large, as we saw with cliques (which are diameter 1). A fun exercise is that the Petersen graph has hyperopic cop number 3.

Densities

If we form the ratio of the number of vertices of a graph to its hyperopic cop number, then we obtain a rational number greater than 0 but less than 1/2. We call this the hyperopic cop density for short. The nice thing about densities is that they allow you to talk in interesting ways about graph parameters for infinite graphs.

Imagine a (countably) infinite graph G as a kind of limit, or union of an infinite chain of finite induced subgraphs. The density of the infinite graph G is the limit of the density of the chain. Sometimes, the choice of the chain doesn’t affect the density. For example, for the usual cop number, if every subgraph in the chain is connected, then it can be shown the limiting cop density is always 0.

We showed something very different for hyperopic cop numbers. There are examples of countably infinite graphs where the hyperopic cop density over connected chains can be any real number in [0,1]!

The result surprised us and is one of many that shows how different Hyperopic Cops and Robbers is from the usual game of Cops and Robbers.

Anthony Bonato