Imagine an intruder is loose on a network, and you are trying to capture them. You control a team of searchers, and both you and the intruder have clear rules about the limits of your powers. For example, you could be restricted to move only to nodes, and move between nodes which share a connection. The intruder could be visible, or invisible; maybe the intruder moves faster than you, or you can capture the intruder from some fixed number of steps away.

Mathematicians, specifically graph theorists, think of these situations in terms of games, so called graph searching games.  In graph searching, a graph is specified, and one team consists of the intruder, and the other a group of searchers. There could be one more searchers, but usually there is only one intruder.  The analysis of these games is surprisingly intricate, and even simple variations of the graph searching theme lead to open problems and deep conjectures.

The most popular graph searching game is Cops and Robbers. In this game, players occupy nodes, and can only move to nodes from which they share a link or “edge”. Searchers are called cops, and the intruder is the robber. The cops move first, occupying some set of nodes, followed by a choice of node of the robber. The cops’ goal is to capture the robber by landing on the vertex that it occupies.  The robber tries to escape capture indefinitely, if they can. You can always arrange this by putting a cop on each node of the graph, but usually much fewer cops are needed. For example, two are needed on a cycle graph (and one does not suffice): one cop is stationary, and the other cop sweeps the cycle to force the robber to collide with the stationary cop.

The minimum number of cops needed to capture the robber is the cop number of the graph. For a graph G, we write c(G) for its cop number. If a graph is disconnected (contains two or more parts with no edges between them), then the cop number is the sum of the cop number of the connected parts.  Hence, it is only interesting to consider the cop number of connected graphs. And this leads immediately to a hard conjecture!

Meyniel’s conjecture states that the maximum cop number of a connected graph of order n is: Dn^(1/2), where D is a constant. In other words, c(G) = O(n^(1/2)) (if you are familiar with asymptotic notation).  Despite our best collective efforts, this conjecture is open. While we know some upper bounds, none of them are nearly as low as the square root bound. Even proving an upper bound of n^(0.99999999) would be a major breakthrough.

Henri Meyniel was a respected graph theorist, who worked on many areas especially coloring problems. He only published one short paper on Cops and Robbers, unrelated to the conjecture. We don’t know much about the personal life of Meyniel, and his conjecture appears as a cryptic personal communication in a 1987 paper of Frankl.  My colleague Gena Hahn told the story about how Meyniel committed suicide in Paris. I would like to know more about this event (even a newspaper article or obit), and I only have one photo of him (courtesy of Gena).

You can read more about the conjecture in my book on Cops and Robbers, or my survey article: http://www.math.ryerson.ca/~abonato/papers/meyniel_0712.pdf

-Anthony Bonato