You're reading: Posts Tagged: graph theory

Timetabling choreography with maths

Earlier this week my sister-in-law (“SIL” from now on) sent me an email asking for help. She’s a dance teacher, and her class need to rehearse their group pieces before their exam. She’d been trying to work out how to timetable the groups’ rehearsals, and couldn’t make it all fit together. So of course, she asked her friendly neighbourhood mathmo for help.

My initial reply was cheery and optimistic. It’s always good to let people think you know what you’re doing: much like one of Evel Knievel’s stunts, it makes you look even better on the occasions you succeed.

I’d half-remembered Katie’s friend’s Dad’s golf tournament problem and made a guess about the root of the difficulty she was having, but on closer inspection it wasn’t quite the same. I’m going to try to recount the process of coming up with an answer as it happened, with wrong turns and half-baked ideas included.

This video about the proof of the Kelmans-Seymour conjecture is adorable

Theorem: every 5-connected non-planar graph contains a subdivision of $K_5$.

The above statement, conjectured independently by Alexander Kelmans and Paul Seymour in the 70s, is very easy to say. And the video below, starring Dawei He, Yan Wang, and Xingxing Yu, makes it look very easy to prove:

It’s like they got Wes Anderson to film an academic PR video. In the normally uninspiring world of maths press releases, it’s quite refreshing. And the written press release is pretty snappy, too. Let’s not make this a thing, though.

Steinberg’s conjecture is false

Conjecture   Every planar graph without 4-cycles and 5-cycles is 3-colourable.


In a paper just uploaded to the arXivVincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li and Esteban Salgado show the construction of a graph with no cycles of length 4 or 5 which isn’t 3-colourable: it isn’t possible to assign colours to its vertices so that no pair of adjacent vertices have the same colour, using only three different colours. This is a counterexample to a conjecture of Richard Steinberg from 1976.

The problem was listed in the Open Problem Garden as of “outstanding” importance.

Read the paper: Steinberg’s conjecture is false

via Parcly Taxel on Twitter

Nobel prize for economics awarded to a mathematician

There may be no Nobel in mathematics, but that needn’t stop mathematicians winning one: Lloyd Shapley has just won the Nobel prize for economics, for the theory of stable allocations and the practice of market design.

Lloyd Shapley described himself in an Associated Press interview:

“I consider myself a mathematician and the award is for economics. I never, never in my life took a course in economics.”

But if you don’t take his word for it, look on over at his entry on the Mathematics Genealogy Project, and you’ll find his thesis is on “Additive and Non-Additive Set Functions”.

The Nobel prize website has some details on the theory of stable allocations and market design, but an old AMS feature column gives a gentler mathematical introduction, via the elegant graph theory of Hall’s Marriage theorem.

Gaffe Theory: Mitt Romney’s followers are almost definitely robots, says analysis

An analysis published in The Atlantic sought to test a hypothesis whether Mitt Romney’s Twitter followers are real or whether they display ‘bot-like’ behaviour. This follows a sudden recent spike in followers to his account. The same analysis was completed for Barack Obama’s account as well. So, are Mitt and Barack’s followers real?