Partitions of Graphs III: Ramanujan meets Kevin Bacon

This is the third in a series (see also Partitions of Graphs I and Partitions of Graphs II).

Chances are you’ve played with graphs before.  If you’ve ever played the Kevin Bacon game, you’ve played with graphs.  The game goes like this: someone names an actor and your job is to link that actor to Kevin Bacon, through actors who co-starred in films.  One claim is that every actor has at most six degrees-of-seperation from Kevin Bacon.

This is graph theory.  The graph has actors for nodes and two nodes are linked with an edge if they were in a film together.

The last film that I saw starring Kevin Bacon was Quicksilver, in which Bacon plays a New York bike messenger (on a sweet fixed-gear).  In my mind I imagine Kevin Bacon hurtling toward Srinivasa Ramanujan, who stands placidly awaiting the inevitable collision.

Who is Ramanujan?

Srinivasa Ramanujan, to me, embodies all that is mystical about mathematics.  Born and raised in India, with little formal education in mathematics, he was essential self-taught.  He was undisputably a mathematical genius of the first degree.  He discovered strange and wonderful mathematical formulas.  G. H. Hardy, a top English mathematician at the time to whom Ramanujan sent some of his formulas said that they “must be true, because, if they were not true, no one would have the imagination to invent them.”   Ramanujan himself said “An equation for me has no meaning, unless it represents a thought of God.”  Unfortuanetly Ramanujan suffered from poor health and died in 1920 at the age of 32.

Here is an example of a problem he worked out:

The three dots mean that you continue the pattern on forever.  Ramanujan discovered the answer to be 3.

Why do I bring Ramanujan up, and why do I imagine Kevin Bacon hurtling toward him on a fixed gear bicycle?  Well, Ramanujan did fundamental work on partitions of whole numbers.  He proved some formulas that to me look strange, beautiful and mystical.

And so I see Ramanujan as representing partitions of whole numbers and standing dignified and unperturbed.  He is deep in thought as he stares down the unwitting-popularizer of graph theory in our day, Kevin Bacon, who has a beret on his head and a bicycle between his legs.  The collision is inevitable.

While you’re picturing that scene, think about this also: mathematicians like to use what we call functional notation.  It’s just a short way of writing things.  For instance, we can find the partitions of three:

3

2+1

1+1+1

We like to write “the number of partitions of three is three” as p(3)=3.  Likewise p(4)=5:

4

3+1

2+2

2+1+1

1+1+1+1

Now, say we have a graph, and for convenience let’s call it G.  In my next post I will say what I want p(G) to mean.