Who else has an Erdős-Bacon-Sabbath number?

A little while ago, I did some sleuthing to find out the Erdős number of Brian May, astrophysicist and guitarist from Queen. My travels led me to Timeblimp, who threw together three measures of professional collaboration to make a rather fun parlour game. Assuming that the people in your parlour are three kinds of nerds and enjoy long and complicated internet scavenger hunts. Which I am and I do.

The game is to find a well-known person who has published academically, released a song, and been involved in a movie or TV show. Then, you play three versions of Six Degrees of Kevin Bacon: find a series of movies to connect them to prolific actor Kevin Bacon, a series of coauthored papers to connect them to the eccentric mathematician Paul Erdős, and a series of musical collaborations to get to Black Sabbath. Add up all the links and you get the Erdős-Bacon-Sabbath number.

To even have an Erdős-Bacon-Sabbath number puts you in quite an exclusive club. Only four people — Richard Feynman, Natalie Portman, Stephen Hawking, and the aforementioned Brian May — are known to be on the list. Until now. In this post, I’m going to throw out a few more potential names and put in the legwork to add two of them to the list of People at the Center of the Universe.

Conjectures

Winston Churchill

The former British prime minister is a bit of a wild guess, but I thought he’d have a shot at an Erdős-Bacon-Sabbath number thanks to his historical research, the zillion documentaries he’s been in, and Supertramp. Sadly, it seems that all of Churchill’s historical research was written solo, so he doesn’t have an Erdős number.

Shaquille O’Neal

Another crazy idea from another field entirely, Shaq ought to have Bacon and Sabbath numbers thanks to his various off-court activities. He took the project option for his recent doctorate, so he doesn’t have a peer-reviewed academic paper to his name, but perhaps an argument could be made for an Erdős number through his senior supervisor.

Phil Plait, Neil deGrasse Tyson, and Carl Sagan

BadAstronomer Phil Plait and badass astrophysicist Neil deGrasse Tyson both have spent a fair time on TV communicating science to the public and have the academic credentials to back it up. They ought to have finite Erdős-Bacon numbers, but I have no idea if either can sing. Carl Sagan is in the same boat as the above two guys, except he does have one credit as record producer under his belt.

Bill Nye

The Oracle of Bacon gives him a Bacon number of 2 through an EPCOT Center movie, and if that’s too flimsy for you he’s got plenty of mainstream TV show appearances. A better detective than I could certainly parlay the Soundtrack of Science into a Sabbath number for the Science Guy. But since Bill’s background is engineering and comedy rather than academia, any Erdős number will have to come through his patent portfolio.

Sir David Attenborough

The famous naturalist and BBC broadcaster should have a well-defined Erdős-Bacon number through his academic books and documentaries (although his Bacon number should be bigger than his brother’s 2). Apparently he’s also done narration for two musicals — Yanomamo and Ocean World — so perhaps he has a Sabbath number as well?

Thomas Edison

Clearly, you have to be some sort of wizard to have a finite Erdős-Bacon-Sabbath number — how about the one from Menlo Park? I am convinced that Thomas Edison has a finite Erdős-Bacon-Sabbath number, but the degree of difficulty for finding it is through the roof. Thanks to the Mathematics Genealogy Project, I have managed to assign Edison a tenuous Erdős number of six: he collaborated with Francis Upton, who studied under and was recommended to Edison by Hermann von Helmholtz, who taught Freidrich Schottky, who taught Konrad Knopp, who has an Erdős number of two via George Lorentz. It is unclear whether Edison ever directed or whether he had any collaborators on his spoken-word performance of “Mary Had a Little Lamb”, but his role in creating the entire recorded music and motion pictures industries should count for some sort of Bacon-Sabbath number.

New Member: Brian Cox, EBS #13

Sean from Timeblimp floated the possibility of rock star/particle physicist Brian Cox having a well-defined Erdős-Bacon-Sabbath number, but to my knowledge nobody has actually worked out what it is. So here goes.

It’s easy to find Brian Cox’s Bacon and Sabbath numbers (they’re both three) but his Erdős number is somewhat harder. I managed to find a path of length seven using only papers with three coauthors or fewer, but Cox has worked in gigantic collaborations like ATLAS. It may be possible to get a shorter path through one of the papers he shares with thousands of coauthors.

Erdős number 7

Brian Cox
Hard colour singlet exchange at the Tevatron
Leif Lönnblad
Small-x dipole evolution beyond the large-Nc limit
Gösta Gustafson
The action-angle variables for the massless relativistic string in 1+1 dimensions
Bo Söderberg
Scaling laws for mode lockings in circle maps
Boris Shraiman
Scaling theory for noisy period-doubling transitions to chaos
C. Eugene Wayne
The Euler-Bernoulli beam equation with boundary energy dissipation
Steven George Krantz
Intersection graphs for families of balls in Rn
Paul Erdős
 

Bacon number 3

Brian Cox
Stargazing Live
Jonathan Ross
Valiant
John Hurt
Jayne Mansfield’s Car
Kevin Bacon
 

Sabbath number 3

Brian Cox
Dare
Darren Wharton
Thin Lizzy
Tomy Aldridge
Ozzy Osbourne
Ozzy Osbourne
 

Note: Jonathan Ross can be connected directly to Kevin Bacon if you allow for TV review shows. Thanks to Mike Whitaker for pointing this out in the comments.

New Member: Tom Lehrer, EBS #9

Tom Lehrer is a mathematician-turned-musical-satirist; you might have heard his song listing the chemical elements. Starfish13 on the QI forums suggested Lehrer as a candidate: he’s got an an Erdős number of four according to MathSciNet and a Bacon number of two according to the Oracle.

The only missing link is the connection to Black Sabbath. I managed to find quite a short path via the Muppets.

Erdős number 4

Tom Lehrer
The distribution of the number of locally maximal elements in a random sample
WF Penney
The number of components in random linear graphs
John Riordan
The solution of a certain recurrence
Ronald Graham
On sums of Fibonnaci numbers
Paul Erdős
 

Bacon number 7

Tom Lehrer
The Frost Report
John Cleese
The Big Picture
Kevin Bacon
 

Sabbath number 3

Tom Lehrer
“Silent E” from The Electric Company
Joe Raposo (producer/lyricist)
“The First Time it Happens” from The Great Muppet Caper
Frank Oz as Miss Piggy
“Born to be Wild” from Kermit Unpigged
Ozzy Osbourne
 

If you allow for Joe Raposo’s non-performing credits, this gives Tom Lehrer the lowest-known Erdős-Bacon-Sabbath number of 9 — making him tied with Stephen Hawking for Person Closest to the Center of the Universe!

Q: Does anyone else have an Erdős-Bacon-Sabbath number?

How to catch Legendary Pokémon

The year was 2000, a few years after Nintendo made Pokémon Red and Blue. I was in grade 7, and had spent much of the last few years finding, capturing, training, and battling every Pokémon I could. Finally, I had caught all 150 available species and completed my Pokédex, and I desperately wanted Nintendo to make more.

mascots

That Christmas, I got my wish. My 12-year-old eyes lit up when I unwrapped Pokémon Silver at my grandparents house: Colour graphics! A whole new world to explore! And a hundred new Pokémon! As soon as I could escape from present-opening, I raced downstairs and started playing. By the time it was time to leave at the end of the week, I already had four badges — and then, on the car ride home, I encountered a new legendary Pokémon with a very unique quality.

Normally, each species of Pokémon can be found in a handful of fixed habitats; for example, Jigglypuff can always be found on Route 46. But this new encounter, the legendary beast Entei, didn’t stay put. It ran away as soon as I stumbled across it, and moved to a different route every time I stepped into a new location. Catching this roaming Pokémon would be an interesting challenge.

jigglypuff-location
Jigglypuff can always be found on Route 46, but Entei moves from route to route.

Months passed, and though I had long since beaten the rest of the game, I still hadn’t succeeded in catching Entei. I had spent hours chasing it around the world map, only to have it run away each time I threw a Pokéball at it. Exasperated, I wondered: What strategy would catch the roaming Pokémon as quickly as possible?

Since the 1970s, mathematicians have studied graph pursuit games like this one. Classically, researchers have asked how many “cops” it takes to guarantee the capture of an evasive “robber” travelling around a graph. Depending on the graph, many cops might be needed to catch a clever robber.

Unfortunately, the graph corresponding to the Pokémon region of Johto contains a long cycle as an isometric subgraph, so its cop number is at least two. In other words, it’s possible that a roaming Pokémon could theoretically evade a single Pokémon trainer forever! But there’s still hope. The legendary beasts don’t devote their movements to avoiding a little kid, so the assumption of perfect play doesn’t apply to our game of cops and robbers. We might be able to use their random behaviour to find a strategy to capture them in a short amount of time.

How did I come across Entei in the first place? As it turns out, a roaming Pokémon can be expected to visit each of the n locations on an arbitrary map after roughly 4n3/27 steps. So any trainer who isn’t actively trying to avoid Entei should end up bumping into it eventually — and an intelligent trainer should be able to do much better.

A good place to start is the “greedy” strategy I originally used: at each step, move closer to the robber’s current position. At each step, let’s say that the robber has at most Δchoices of adjacent places to run to. Since Entei moves randomly, it has at least a 1/Δchance of moving towards the trainer. If the trainer starts d steps away, she only needs to get lucky d/2 times before crossing paths with Entei. The capture time follows a probability distribution bounded by the negative binomial distribution and has expectation E[capture time] ≤ Δ⋅d/2. In the grand scheme of things, this isn’t too bad — especially if Δ is low. But it still takes a frustratingly large time for a 12-year-old, and in general it’s possible to do better.

Recently, Peter Winkler and Natasha Komarov found a strategy for general graphs which gives a better bound on the expected capture time. Somewhat counterintuitively, it involves aiming for where the robber was — rather than his current location — until the cop is very close to catching him. The Komarov-Winkler strategy has an expected capture time of n + o(n), where n is the number of locations on the map. This is better than the above Δd/2 bound when the graph has vertices with large degree, and is essentially best possible on certain graphs.

For graphs without high-degree vertices — like the Pokémon world map — it is possible that a simpler solution could beat the Komarov-Winkler strategy. The problem is: simpler strategies may not be simpler to analyse. In her PhD thesis, Natasha wondered whether a greedy algorithm with random tiebreakers could guarantee n + o(n) expected capture time. It is an open question to find a general bound for the “randomly greedy” strategy’s expected performance that would prove her right.

runaway

Nintendo has embedded an interesting mathematical problem in the Pokémon video game series: to catch the roaming legendary Pokémon, trainers play a variant of the cops-and-robbers graph pursuit game. We’ve seen a few strategies for the game on general graphs, but still haven’t found an answer to the question I asked as a Pokémon-obsessed 12-year-old.

The solution for the particular game played in Pokémon is a little anticlimactic: since the roaming legendaries are forced to move when the player character changes locations — regardless of how little time that takes — the optimal strategy is to hop back and forth between two routes and let your target come to you! The expected capture time can be found with the theory of random walks on graphs, and is inversely proportional to the number of routes adjacent to the place you wait.

Brian May has an Erdős number

If you’ve heard of Erdős Numbers, Erdős-Bacon Numbers, and the fact that Queen lead guitarist Brian May has a PhD, you may have wondered whether Brian May has a well-defined Erdős-Bacon number. As a matter of fact, he does. Here’s how the rock legend is connected to the centres of cinema and academia.

Bacon number: 3

Thanks to IMDB and the Oracle of Bacon, Bacon numbers are easy to find. The guitarist’s credited voice role as “Massed Peasant Chorus/Chamberlain” in The Adventures of Pinnochio makes him only three films away from Kevin Bacon.

Erdős number: 7

In mathematics, the equivalent tool to the Oracle of Bacon is MathSciNet’s collaboration distance tool. Unfortunately, it does not catalogue the astrophysics journals Brian May has published in, so his Erdős number has to be found manually. The best previous attempt I found was a path of length eight, through a popular science book cowritten by May. However, I managed to find a shorter path, starting with a letter published in Nature.

This gives Brian May an Erdős-Bacon number of at most 10, and the smallest known Erdős-Bacon-Sabbath number of 11.

Exponential growth in Katamari Damacy

Katamari Damacy is a wonderful game: simple, fun, delightfully bizarre, and deceptively mathematical. Katamari and its sequels follow the tiny Prince of All Cosmos as he rolls a magical sticky ball (called a katamari) around Japan. As things stick to the katamari, it becomes bigger, enabling it to pick up larger and larger objects. Eventually, the Prince builds up a massive enough katamari to roll up people, cars, buildings, islands, rainbows, and just about everything else in the game.

Katamari’s core game mechanic is the exponential growth model. As long as the stage has plenty of objects to pick up, the katamari grows at a rate roughly proportional to its size. Katamari delivers an aesthetic experience that conveys the essential intuitions behind exponential functions, similar to short films like Powers of Ten.

In the above chart, I explore how closely katamari size tracks an exponential curve. I watched five Let’s Play videos of different YouTubers playing the final level of Katamari Damacy and plotted their progress. Sure enough, each run traces an approximately straight line on the logarithmic scale, indicating exponential growth.

Most English words are short

This chart was inspired by a piece of folk wisdom from an old email forwarding-spam:

Aoccdrnig to rseearch at Cmabrigde Uinervtisy, it deosn’t mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteer be at the rghit plcae. The rset can be a toatl mses and you can sitll raed it wouthit porbelm. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.

The form of this email appears at first glance to provide direct evidence of its own “azanmig” claim. But something’s a little fishy: a lot of the words aren’t actually scrambled. Short words aren’t affected by the message’s middle-muddling, and if a paragraph mostly consists of words under six letters, there’s just not that much unscrambling to do!

So is the chain letter’s prose typical, or has it been carefully written to exaggerate our anagramming abilities? This depends on how English words are distributed according to their length. Although the median word has seven letters, shorter words are used more frequently:

  • Over a third (38%) of the words in an average paragraph have three letters or fewer — too short to scramble.
  • Four- and five-letter words, which admit only easy rearrangments, account for a further quarter (25%) of written words.
  • The average word length is just 4.95 letters.

By these metrics, the email is on the easy side. Almost half of its words don’t need to be deciphered; 79% of the words have fewer than six letters; and the average word length is 4.10. A random Wikipedia article will take a fair bit more effort to unscramble. Unfortunately, we don’t have amazing anagram abilities — at best, we can claim a form of error correction against small numbers of transpositions.