Maths is just colouring-in, really!

Well, blog posts are just like buses, it seems - you wait ages for one, and then when they do come, they're a bit disappointing and rushed!  Wait, no, hang on...

Today, I want to talk to you about some maths.  Specifically, a branch called Graph Theory, which was the module that kept me sanest during my final year at Uni, primarily because it involved a lot of drawing pretty pictures (a fact which all my geographer friends were quick to take advantage of!).

In Graph Theory, a graph isn't something like this:

it's more like this:

A "graph" in graph theory terms is a collection of points (or "vertices") joined by lines (or "edges").  Graph theorists study various properties of graphs - the minimum number of edges that must be crossed to get between two vertices, the average number of edges meeting at vertices, and so on.  Since these graphs can provide very good models for road layouts and computer networks, you can see how the ability to concisely gather information about them could be useful - but, mostly, we just do it 'cos they're pretty (both mathematically and visually!)

I'm going to talk about something called a Ramsey number, and outline a simple but elegant proof.  This is something where you can follow along at home, kids!  Grab a pen and paper and meet me back here!  Actually, better make that at least two pens (of different colours), though three would be even more helpful.

Got 'em?  Good.

Right, first of all, draw yourself a hexagon - that's a six-sided regular shape, that looks like this:

(Do your best to make the corners sharply defined, rather than curves - it'll make your life easier later on.)

Congratulations, you've drawn your first graph!  Technically, this called C₆, (the C stands for "cyclic", since, as you can see, it resembles a circle in that you can go round in turn and return to your starting place) and there are various things that we could learn from examining it, but I have more a more interesting result in my sights.

Now join each vertex to every other vertex with a straight line.  This should end up looking like this (where the vertices have been highlighted in blue):

What you have drawn is called the "complete graph on 6 vertices", or K₆ for short.  For any number n, K_n is simply n vertices with each one joined to every other. K₁ is just a single vertex, K₂ is a line joining two vertices, K₃ is a triangle, K₄ is a square with the diagonals filled in, and so on, as shown below:

Now, to introduce the Ramsey numbers, I first have to introduce the notion of graph colouring.  This is just as it sounds - a colouration of a graph is a drawing of it where all of the edges have a particular colour.  So, for instance, this is a colouring in red, blue, and green, on an (incomplete) graph of 20 vertices;

and this is a colouring in 7 colours (we would say a "7-colouring") of K₈

(Note that it doesn't matter that the vertices of this graph aren't arranged around the points of an octagon - graph theory only cares about the connectedness (or unconnectedness) of points, not their relative positions.  K₃ is still K₃ whether it's represented as a small scalene triangle, or an equilateral triangle the size of the galaxy)

Now (and don't worry, I'll come back and explain this later), we define the Ramsey number R(m) as being the smallest number n such that, for any 2-colouring of K_m, there will always be a monochromatic K_n.

Phew...what on earth does that mean!  Well, let's start off with a simple example.  Let's try to find R(2) - that is, the smallest number n such that, if we link up all n vertices with either red or blue lines, we'll either have a red K₂ or we'll have a blue K₂.  Well, since K₂ is just a single edge, if there's more than one vertex in our graph, there's bound to be either a red or a blue K₂, otherwise we haven't coloured it all - but if there's only one vertex in our graph, there are no edges (nothing to link to!), so no K₂.  So R(2) is 2.

Let's get a bit more adventurous.  What's R(3)?  Well, it's clearly bigger than 3 - as long as you don't use the same colour to draw all three sides of the triangle, you won't end up with a monochromatic triangle in your colouration.  Similarly, we can 2-colour K4 (remember, a square with the diagonals drawn in) without making a mono-K3 - for instance, draw the outside square in red and the diagonals in blue.

This post is dragging on a little, so I'll set you a question to ponder and give the answer (and proof) in the next post - what is R(3)?  If you think you know it, try to consider how you'd prove it - how can you prove, for instance, that there isn't a satisfactory 2-colouring on a smaller complete graph?  I'll warn you now, while sketching out some ideas will help, trying to prove a result by exhausting all possible colourations will take you a while - there are, for instance, 378 possible colourations of K₈*, so you'll be there for a while!  I'll give the solution and proof next time.

* - where xCy is the choose function, there are 8C2 = 28 edges (for each of the eight vertices, there is precisely one edge for every way of choosing two of them), and so, since there is one colouration for every way of choosing a colour for each of these, there are 28C2 = 378 colourations.  For mathematicians - yes, I'm aware that I've double-counted isomorphic colourations, but if you're seeking a solution by brute force exhaustion like this, it's appropriate to warn of an appropriate upper bound!

EDIT: I tried to get a definitive answer on the number of 2-colourings of K₈ by using Wolfram Alpha, a "computational knowledge engine".  The results were...less than satisfactory:

And after the drought...

Ooooh, Blogger has had an overhaul!  Long overdue, the old interface really didn't fit in with the sleek shiny unified Google UI look they've been moving towards.  A little confusing for now, but I'm sure I'll get used to it!

<Insert tired excuse for not posting here> - yeah, I really have no excuse.  And this is going to be a bit short and sweet anyway.  Apologies for those hanging on my every word!

It may not surprise you to hear that I've been watching, and very much enjoying, the Game of Thrones TV series (adapted from the books by George R. R. Martin).  In Season Two (slightly confusingly, still titled Game Of Thrones, despite being adapted from the second book, A Clash of Kings), an increasing number of liberties have been taken with the canon, which is enraging some of the more die-hard fans.  Characters have been introduced or written out, conversations happen in different ways, at different times, and sometimes between different characters.  More commonly, the tone and subtext of exchanges is altered, both by the lack of internal monologue, and the choice of which lines to keep and which to cut/merge.

Personally, I think they're doing a fantastic job.  I'm very much of the opinion that to stay slavishly true to the original is the mark of a lazy adapter.  If you're reinterpreting a work, you are creating a new piece of art, which, by the nature of its different medium, must fulfil different demands and work in a different way.  The truly excellent comic book Watchmen, by Alan Moore (which you really should read, by the way - it is one of the best arguments for comics being "not just for kids anymore", along with the truly staggering Sandman series by Neil Gaiman) was adapted into an equally excellent film, which managed to please critics despite having a completely different ending!  The different interpretation of results, however, was not only well supported by the preceding drama, but also lent itself well to the silver screen, and so, it was a success.

The most obviously different conditions between books and TV are both caused by timing.  When reading a book, you can take your time over it, re-read sentences, and work your way to the subtext and the implications - two things that Martin loves to spread throughout his writing.  A TV viewer doesn't have that luxury, and so insinuations and hints have to be made a little more explicit.  Conversations must necessarily lose a little of their subtlety, or risk leaving non-readers stranded.

Additionally, a TV episode has to keep viewers wanting more, and so each episode must end on a cliffhanger, a dramatic scene, or at the very least something that makes viewers think that they will want to tune in again next week.  While books can employ similar techniques (and, indeed, several of Martin's chapters do end on notes that leave readers frantically scrabbling through pages to find the resolution), they are not forced to with the same regularity as episodes, and do not have to hit the same narrative "beats".  Chopping and changing of event orders is entirely understandable, under this pressure.  As a good example, a particular character would have, in the books, spent several weeks wandering the wilderness, hiding from marauders and would-be captors, in the narrative space between episodes 3 and 4, before finally being captures. In the show, she is taken directly from her previous escort.  While the intervening time helps build the sense of desperation, it is not, narratively, important, and so its removal is justified.

There are downsides, of course.  I fear that viewers are missing out on some of the rich backstory and history of the world, and that future plot twists might seem a little like Di ex machina without the subtle foreshadowing that peppered the books - but, on the whole, I feel that a hard job is being done very well, and the crew and cast should feel very proud!  Of course, it does help to have the author as an Executive Co-producer :)

Plus, at the end of the day, this way someone who has only seen the show can effectively discover a whole new depth to the series by reading the books, furthering their enjoyment - and that can't be bad!

[A personal plea - those links what you see up there are Amazon Affiliate links. If you click them and then buy anything (not necessarily the product they link to, as long as you browse in the same tab), a percentage of what you spend will go to me instead of Amazon, at no extra cost to you.  Obviously, if you're thinking of expanding your library, or indeed buying anything Amazon-wise, I'd very much appreciate it if you did so via these links!  It's completely anonymous and, once again, adds not a cent to the price you pay]

Meditations on Mass Effect 2

A quick and unpolished blog post because, well, I wrote most of this out on Facebook, and then I remembered that I hadn't posted anything here in a while!

OK, thoughts on Mass Effect 2;

It's better. A lot better. A LOT better. Almost every aspect has improved - the storyline, characterisation and voice acting, and level design, in particular, show a MARKED improvement.

One thing that feels worse, however, (and I seem to be in the minority in feeling this) is the combat. Finding cover is hit-and-miss, with Shepherd regularly diving into cover and then standing straight back up again, or outright refusing to duck behind/out of an area that is obviously intended as such. Add to that the fact that a number of enemy weapons appear to ignore cover, to the point of even knocking you OUT of cover, and it rapidly becomes frustrating. When you can find a safe place to fire from, the scatter radius is so large that I'm essentially spraying bullets in the approximate direction of the enemy (admittedly, this may be due to the fact that Vanguard appears to have been nerfed between games, but the rest still stands - though, on that topic, where'd all my skill customisation options go!?  And Lift!?  Lift was AWESOME!  Don't give me this "Charge" bullshit, that's crap and you know it.).

That's all the more frustrating since the combat difficulty has ramped up MASSIVELY between games. I think I died maybe ten times, if that, in the whole of Mass Effect, so I thought I'd try this game on Veteran. Even after I gave up and switched back to Normal after trying the same mission twenty times, I'm still dying two or three times on each non-mook fight. I'm switching weapons to prioritise barrier/amour/health etc., and making extensive use of biotics, but the deciding factor in most fights seems to be the suicidally depressed (or otherwise) impulses of the AI. If they break cover to flank me, I haven't got a hope (whereas if I try to do the same, I'm gunned down inside two seconds), but if they stay put I can whittle their health down inch by inch.  Maybe I haven't got the hang of the combat system, but I'm definitely finding the regular restarting is interrupting my enjoyment of an otherwise excellent story.

That said, the story *is* excellent, and I'm sure once I've had the chance to do a few side missions (which seem a lot thinner on the ground this time round) Shepherd will be more effective than a disable Chihuahua trying to hump the Collectors' collective legs and I'll enjoy combat a bit more.  I just hope it comes around sooner!