Zooming On My Cycle

I started my job with the University of Florida in April 2020, right as the COVID work-from-home policies were starting up. As a result, all my meetings are conducted over Zoom. Now and then I get a little bored with the subject at hand (but only very rarely!) and I start thinking about the layout of the meeting participants on my screen:

I try to move my mouse from each window to an adjacent one, visiting each once and returning to the start. This type of problem is the subject of graph theory, which assesses the attributes of nodes (the windows in this case), which are connected by edges (whether two windows are adjacent). The quality we're looking for is called a Hamiltonian cycle. My various meetings have different numbers of participants, and I've been fascinated by whether a given arrangement contains one or more of these cycles.

It turns out this problem is in a category called NP-complete, which is broadly defined as problems that are hard to find solutions for, but easy to check if a given answer works. In this case, given a path through the windows, it's easy to check we visit each once and end at the start, but the only way to find those is to check every possible path. As long as the number of nodes is small, this isn't too taxing, but the complexity scales quickly as we add more people.

Luckily, Zoom only puts 25 people on the screen at a time, and will break the group into pages if there are more. That means I can make a script to test every case! I used the package NetworkX to handle the connections between nodes, which let me generate paths to check. The animation below pages through different numbers of meeting participants, and gives the number of unique cycles at the top.

I find it really interesting how the number of cycles relates to the number of nodes: Even ignoring the drops to zero, the numbers aren't strictly increasing. I'm also surprised by the high numbers of cycles for the bigger groups – I usually only find 1 or 2 before I manage to refocus on the meeting!