Ice and Land

I am recharging my batteries with a quick trip to Iceland. For that reason, my post will be short this week. So this post is more “travel blog” than “math in pop culture”. Mathematics will sneak in at the end, of course.

My spouse and I arrived in Reykjavík Friday, which is a small but very modern, liberal city. Everyone speaks English, and it is easy to escape the tourist crowds.

As friends told us before we came, Reykjavík is cool, which pretty much sums things up.

This is the North Atlantic, so bring your rain gear. We are also here in late June, so the sun is up until well past midnight. The joke is that the sun peaks through the clouds around 10 pm.

Waterfalls, geysers, and black sand beaches

We spent a few days on the road touring the famous Golden Circle, which contains lovely parks, falls, and geysers.

The scenery here is captivating and otherworldly. Here I am at Gulfoss, and on the right is a live shot of the geyser Stokkur erupting in all its glory.

The southern coast around Vik is beautiful, with stunning black sand beaches.

University of Iceland and Cops and Robbers

Always one to mix business with pleasure, I am speaking in the Mathematics Seminar at the University of Iceland on Thursday. I tend to be relaxed whenever I am in a university. They are like my second homes all over the planet.

I will be speaking on conjectures in Cops and Robbers games. I wrote a book The Game of Cops and Robbers on Graphs a few years ago on this topic which got some attention.

In the game of Cops and Robbers, a set of cops is attempting to capture a robber lose in a network. While the rules of the game may vary considerably, the mainstream version is where both players and all moves are visible, and the cops and robber move at unit speed from vertex-to-vertex along edges. The cops move first, followed by alternate moves with the robber. The cops capture the robber if they simply land on its vertex.

In this classic version, now over thirty years old, many deep problems remain. The deepest problem on Cops and Robbers is about the relative size of the cop number.  Meyniel’s conjecture states that the minimum number of cops needed to capture the robber on a connected graph is O(n^1/2), where n is the number of vertices of the graph. We know of families of graphs which asymptotically need that many cops, but no one can prove the stated upper bound for all connected graphs.

Cops and Robbers is a part of the larger field of pursuit evasion games played on networks, with names like Seepage, graph burning, Zombies and Survivors, graph cleaning, robot crawler, and Firefighter. See my posts on meme spreading and the robot crawler.

The cliché is true: travel does broaden the mind. Iceland is truly a special place and I look forward to returning in the coming years.

Anthony Bonato