In Quanta Erica Klarreich recently wrote up Yaroslav Shitov’s new counter example which disproves Stephen Hedetniemi’s 50 year old conjecture, original dissertation, that the number of colors required to color the tensor product of two graphs is the lesser of the numbers used to color the original graphs. These colorings have applications in areas from scheduling to seating plans, and it is clear from Klarreich’s reporting that mathematicians are excited about this result. In fact, Hedetniemi responded very positively when asked by Klarreich about the counter example, saying it “has a certain elegance, simplicity and definitive quality to it.” The counter-example may show Hedetniemi’s conjecture is not true, but Klarreich points out that we do not yet know just how false it is. So, while Shitov has closed one door on this problem, there are still many which are open.

# You're reading: Posts Tagged: graph theory

### LaTeX/TikZ to draw a star graph $K_{1,n}$

For a diagram for a class this week, I’ve written a LaTeX command to draw star graphs using TikZ. A star graph $K_{1,n}$ is a graph with a single central node, $n$ radial nodes, and $n$ edges connecting the central node to each radial node. I am sharing this here in case it is useful to anyone else.

### The chromatic number of the plane is at least 5

A long-standing mathematical problem has had a recent breakthrough – scientist Aubrey de Grey has proved that the chromatic number of the plane is at least 5.

### 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.

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

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

### Nope!

In a paper just uploaded to the arXiv, Vincent 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.*1

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.

- Though technically it’s not a Nobel prize, and actually the
*Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel*. Perhaps Alfred Nobel’s made-up wife also had an affair with a fantastical economist. [↩]