graph theory | The Aperiodical

You're reading: Posts Tagged: graph theory

Aperiodical News Roundup – August 2023

By Katie Steckles. Posted September 7, 2023

Here’s a selection of mathematical stories that crossed our desk in August.

Maths Research News

Researchers have discovered that a shape can be designed to trace almost any infinite periodic trajectory when rolling down a slope, as seen in this Nature.com video (via Jeroen van Dorp)

A new diamond open access journal, Innovations in Graph Theory, has been founded. The first issue of the journal is expected to appear in 2024. (via Peter Cameron)

And in important publication news for silly season: Erik Demaine and Martin Demaine have achieved “the true ideal of an unordered set of equal authors, where every author comes first”. Their paper Every Author as First Author proposes a new standard for writing author names on papers and in bibliographies, which places every author as a first author, with the names all superimposed on top of each other, including details of the \namestack LaTeX command for this purpose. The results are predictably hilarious (see below). (via Nalini Joshi)

Screenshot from paper: "being equal. In our own writing, we try to avoid this practice, and instead write all authors' surnames whenever citing a paper, e.g., "X, Y, and Z [#]". But this workaround becomes impractical for references with over a dozen authors, such as some of our papers (*incomprehensible black smear of overlaid names* 2020; *incomprehensible black smear* 2020) or some papers in astronomy (*incomprehensible black smear* 2006) and biology (*incomprehensible black smear* 2001)."

Other News

Alison Kiddle has been posting daily conversation prompts involving LEGO to stimulate mathematical thinking on their blog every day in August, and people have been responding on Twitter and Mastodon.

Mathematician and logician Peter Aczel has died, as has Ian G. Macdonald (who introduced Macdonald polynomials).

Each Edge Peach Pear Plum

By Christian Lawson-Perfect. Posted March 5, 2022

At the 2021 UK MathsJam Gathering, I gave a talk on a subject that has bothered me more than is reasonable: the graph-theoretic layout of the narrative of the baby’s book Each Peach Pear Plum, by Janet and Allan Ahlberg.

It’s one of my son’s favourite books to fall asleep to. It was his older sister’s favourite, and mine and my wife’s when we were little. I agree with the quote on the back cover, that it’s “the perfect first book”.

BUT

Hedetniemi’s Conjecture in graph theory disproved

By Samuel Hansen. Posted June 24, 2019

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.

via Thomas Lin on Twitter.

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

By Peter Rowlett. Posted December 4, 2018

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

By Katie Steckles. Posted April 17, 2018

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

By Christian Lawson-Perfect. Posted April 9, 2017

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

By Christian Lawson-Perfect. Posted May 26, 2016

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.