You're reading: Posts Tagged: group theory

Christmas Symme-tree

Christmas wrapping paper is sold in thousands of different variations, including plain, coloured, patterned, foiled and even flock, but one thing it’ll have in common is that it will repeat whatever pattern it has, regularly across the design.

I’m interested in symmetry, and was intrigued to find a curious fact about the symmetries of such repeating patterns – their symmetries are quite limited.

László Babai reckons he can decide if two graphs are isomorphic in quasipolynomial time

László Babai in Chicago. Photo by Gabe Gaster, used with permission.

We’ve been slow to cover this, but if this week has taught us anything, it’s that taking your time over Important Maths News is always a good idea.

A couple of weeks ago, rumours started circulating around the cooler parts of the internet that László “Laci” Babai had come up with an algorithm to decide if two graphs are isomorphic in quasipolynomial time. A trio of mathematicians including Tim Gowers were on BBC Radio 4’s In Our Time discussing P vs NP while these rumours were circulating and made a big impression on Melvyn Bragg as they talked so excitedly about the prospect of something big being announced.

If Babai had done what the rumours were saying, this would be a huge advance – graph isomorphism is known to be an NP problem, so each step closer to a polynomial-time algorithm raises the P=NP excite-o-meter another notch.

Poetry in Motion

Phil Ramsden gave an excellent talk at the 2013 MathsJam conference, about a particularly mathematical form of poetry. We asked him to write an article explaining it in more detail.

Generals gathered in their masses,
Just like witches at black masses.

(Butler et al., “War Pigs”, Paranoid, 1970)

Brummie hard-rockers Black Sabbath have sometimes been derided for the way writer Geezer Butler rhymes “masses” with “masses”. But this is a little unfair. After all, Edward Lear used to do the same thing in his original limericks. For example:

There was an Old Man with a beard,
Who said, “It is just as I feared!-
Two Owls and a Hen,
Four Larks and a Wren,
Have all built their nests in my beard!”

(“There was an Old Man with a beard”, from Lear, E., A Book Of Nonsense, 1846.)

And actually, the practice goes back a lot longer than that. The sestina is a poetic form that dates from the 12th century, and was later perfected by Dante. It works entirely on “whole-word” rhymes.

How to solve a Rubik’s Cube in one easy step

Note: If you’re looking for instructions on solving Rubik’s cube from any position, there’s a good page at Think Maths.

One day some years ago I was sat at my desk idly toying with the office Rubik’s cube. Not attempting to solve it, I was just doing the same moves again and again. Particularly I was rotating one face a quarter-turn then rotating the whole cube by an orthogonal quarter-turn like this:


Having started with a solved cube, I knew eventually if I kept doing the same thing the cube would solve itself. But this didn’t seem to be happening – and I’d been doing this for some time by now. This seemed worthy of proper investigation.

“Futurama theorem” slightly improved

The “Futurama theorem”, also known as Keeler’s Theorem after its creator, was a bit of maths invented for the Futurama episode The Prisoner of Benda, to solve a problem where the characters get their heads mixed up and need to swap them back without any one pair swapping heads twice. It was enthusiastically reported by the geeky press, and rightly so, because it’s a fun bit of real maths with a wonderful application. Dana Ernst has written some very good slides about the theorem, working from “what is a permutation?” up to the algorithm itself.

Anyway, some students from the University of California, San Diego have extended the result, giving a better algorithm for finding the minimum number of switches to put everyone’s head back in the right places, give optimal solutions for two particular situations, and give necessary and sufficient conditions for it being possible to represent the identity permutation as $m$ distinct transpositions in $S_n$.

Paper: http://arxiv.org/abs/1204.6086

via James Grime