Season 10 Episode 2

It's another CS takeover on OOMC, with Marcela bringing us maths challenges to do with models of networks.

Watch on YouTube

Further Reading

Machine Learning and Artificial Intelligence

Marcela mentioned at the start of the episode that last year’s Nobel Prize in Chemistry was awarded in part to two people at Google DeepMind for protein structure prediction. One of them is Demis Hassabis. Marcela recommends the documentary The Thinking Game about Demis Hassabis and the journey to artificial general intelligence.

Last year’s Nobel Prize in Physics was also awarded to people working on networks.

Eulerian paths

Marcela started the episode with a description of the Bridges of Konigsberg problem. I said that I’d put the solution in the further reading, but I've decided instead to link you to this NRICH activity to explore the problem first . If you’d like to see the solution to the problem in the livestream, follow the link on that NRICH page to the “Can You Traverse It?” activity.

Planar graphs

In general, when you draw a graph, you’re allowed to have the edges crossing (and you are not required to have a vertex at the point where the edges cross, even though it looks a lot like a vertex on the page – that's why I always try to draw vertices as solid blobs instead of just dots). There are some graphs which you can draw without any edges crossing, and those are called planar graphs.

To be clear, you’re allowed to use curved lines, but you’re limited “to the plane” i.e. you’re drawing on a flat piece of paper.

Lots of nice things are true about planar graphs. You can define “faces” of the graph to be the regions of the plane bounded by edges. If you do that, then the number of vertices, \(V\), the number of edges, \(E\), and the number of faces, \(F\), satisfy Euler’s formula \(V-E+F=2\). Not to be confused with Euler’s formula \(e^{ix}=\cos x + i \sin x\). Euler has too many formulas!

You might have seen this formula before for polyhedra; that’s because there’s a lovely connection between polyhedra and planar graphs. Provided that your polyhedron looks a bit like a sphere (no doughnut-like holes), then you can draw it on a balloon, then pop the balloon at some point and stretch out the rubber to form a planar graph. The edges of the polyhedron become edges of the graph, and the faces of the polyhedron become faces of the graph (including one infinitely large face around the outside; the one where you popped the balloon).

For planar graphs with three or more vertices, the maximum number of edges is \(3V-6\). You might like to try to draw a sequence of graphs that have more and more vertices and that have exactly \(3V-6\) edges. The easiest way to prove that you can’t have more edges is to start with Euler’s formula and argue that \(2E\) is at least \(3F\) by counting the edges on each face.

Erdős number

We briefly looked at this website to explore the graph of “has published a paper with” on the set of mathematicians (broadly defined).

I briefly confused George G. Lorentz with Edward Norton Lorenz, and I'm fixing that by linking to both their MacTutor pages here. The MacTutor website has biographies of more than 3000 mathematicians.

The movie equivalent is the “Bacon number”. Kevin Bacon has a Bacon number of zero. Anyone else who has been in one of these films has a Bacon number of 1. Then anyone who’s been in a film with one of those people has a Bacon number of 2, and so on. This website lets you explore the graph.

Maths Genealogy

The Mathematics Genealogy Project is online here. This graph connects mathematicians not if they wrote a paper together, but if one supervised the other’s PhD. The homepage shows a bit of the graph with Jacobi supervising Gordan supervising Noether, and so on. With a bit of searching I can find examples of people finishing their PhDs in 2017 descended from that chain (see also the descending chain condition). It’s a reminder to mathematicians that we might not all be closely related by birth, but we are all closely related by maths.

Game of Thrones

Marcela has made an interactive graph for all the characters in the book/TV series Game of Thrones, with vertices for the characters and edges for interactions between them.

The Travelling Salesman Problem

Marcela mentioned some route-planning algorithms in the episode, and recommends this video about the Travelling Salesman Problem; What is the Traveling Salesman Problem? | AlphaOpt | YouTube.

Halting Problem

Here’s an interesting CS problem. Given the code for a computer program, and some input for that program, will that computer program terminate or run forever? Alan Turing proved that this is undecidable; there’s no “does-it-halt app” that we can give the code and input to which will always get the right answer.

The proof involves presenting a computer program with a version of its own code, which reminds me of Russell’s paradox and also reminds me of Cantor’s theorem.