Abbot and Costello Meet Low-Dimensional Topology
My graduate training was (at least partially) in mathematical knot theory. I guess because of that I’ve had knot puns running around my head for some time. These finally crystallized into the following routine, which I wrote last night. Besides, I figured we need a little break from the hard-core recreational math of partitions of graphs.
[Costello enters the room where Abbott is seated reading a book whose title, "Knot Theory," is visible to the audience, but not to Costello.]
Costello: Whatcha readin’ Abbott?
Abbott: Knot Theory.
Costello: Oh good. I’m glad it ain’t theory. Every time you read somethin’ theoretical, you go and explain it to me and try to get me all turned around and confused.
Abbott: Mmmph…[not really paying attention to Costello.]
Costello: So whatcha readin’ Abbott?
Abbott: Knot Theory.
Costello: Glad to hear it ain’t theory, but just tell me what it’s about.
Abbott: [Looking up at Costello now] Look, it’s a theoretical book. Not the kind of stuff you’d be interested in.
Costello: It is theoretical?
Abbott: Yes.
Costello: It’s about theory…
Abbott: Yeah.
Costello: You just said it wasn’t!
Abbott: No I didn’t.
Costello: Did so!
Abbott: Hmph.
Costello: OK, then just tell me what kind of theory it’s about.
Abbott: It’s knot theory.
Costello: Abbott! You’re doing it! You’re tryin’ to run me around in circles!
Abbott: I am not–
Costello: I ask you what your book’s about–
Abbott: You want to know what my book’s about?
Costello: –And you won’t give me a straight answer. “It is about theory. It ain’t about theory.”
Abbott: Look. Calm down. I’ll tell you what my book’s about.
Costello: –You’re gonna run me around in circles…
Abbott: No I won’t. Now look. I’ll make it very simple. Every morning you wake up.
Costello: Yeah.
Abbott: You put on your shoes.
Costello: Yeah. Your book talks about that?
Abbott: Now listen. You put on your shoes, and you tie them, right? Tie them in what?
Costello: In a little bow.
Abbott: Yeah. You tie them in a knot.
Costello: I do not! I tie them in a little bow.
Abbott: Fine. You tie them in a little bow. Did you ever think about the theoretical aspects of that?
Costello: The theoretical aspects of puttin’ on my shoes?
Abbott: …of tying your shoes.
Costello: The theory behind puttin’ on my shoes is I don’t wanna get my feet wet when I go outside.
Abbott: I’m talking about tying your shoes.
Costello: The theoretical aspects of tying my shoes?
Abbott: Yes.
Costello: There’s some kinda theory there?
Abbott: Certainly. It’s theoretical.
Costello: What kind of “theoretical” is it?
Abbott: It’s knot-theoretical.
Costello: there you go again, Abbott! It is theoretical. It ain’t theoretical.
Abbott: Now I didn’t say that.
Costello: You were tellin’ me about your book.–
Abbott: –About my book.
Costello: It talks about my shoes in there.
Abbott:Well…
Costello: What size are they?
Abbott: What size are what?
Costello: My shoes.
Abbott: How should I know?
Costello: Your book doesn’t tell ya?
Abbott: It doesn’t say anything about your shoes!
Costello: Are you gonna tell me what’s in that book ?
Abbott: I’m trying to tell you.
Costello: You tell me it is in there and it isn’t in there . . .
Abbott: You’re confusing yourself.
Costello: Somebody’s confusing me, but it ain’t me!
Abbott: I’m trying to tell you what’s in this book.
Costello: I’m tryin’ to figure out what’s in that book!
Abbott: OK, look. It’s knot theory.
Costello: You said that. So what’s it about?
Abbott: It’s about a theory…
Costello: Abbott! you’re doin’ it again!
Abbott:Will you calm down? I havn’t said anything yet.
Costello: You can say that again.
Abbott: Look. I’ll give you another example.
Costello: OK.
Abbott: Were you ever a Boy Scout?
Costello: I sure was.
Abbott:You were.
Costello: Boy Scout, Second Class.
Abbott: OK. Did you ever do a unit on sailing in Boy Scouts?
Costello: Sure did.
Abbott: And you learned to tie sailors’ knots?
Costello: Sure did. I learned my bowline. I got my half hitches.
Abbott: That’s right, and you have a Lark’s head. Now did you know you only have one square knot, but two grannies: a left-handed one and a right-handed one.
Costello: I know I have two grannies, but what’s that got to do with knots?
Abbott: That’s what I’m trying to tell you. It’s all in this book.
Costello: It’s all in there?
Abbott: Yes.
Costello: Where you learned all these facts.
Abbott: Yeah.
Costello: When were they born?
Abbott: Who?
Costello: My two grandmothers.
Abbott:What are you talking about? It’s a book about tying a knot. It’s got nothing to do with babies being born.
Costello: My mother told me that Tying the Knot has everything to do with babies bein’ born!
Abbott: Now listen. You’re bing silly. Do you want to know what’s in this book or not?
Costello: I been askin’ ya what’s in that book.
Abbott: I’m trying to tell you.
Costello: You tell me it’s about my shoes and it ain’t about my shoes. You tell me it’s about my grandmother and which hand she used to write with. You tell me it’s about gettin’ married and havin’ babies. It’s about Boy Scouts and it ain’t about Boy Scouts.
Abbott: OK, OK. I was trying to give you some examples. It’s not about any of that.
Costello: None of it?
Abbott: No. None of those practical matters.
Costello: Nothin’ practical at all?
Abbott: Nothing practical. It’s a theory book.
Costello: Purely theoretical?
Abbott: Purely theoretical. all theory.
Costello: All theory from one cover to the other?
Abbott: Cover-to-cover theory.
Costello: OK.
Abbott: OK?
Costello: OK.
Abbott: OK.
Costello: Then just tell me. Answer me one question.
Abbott: What’s the question?
Costello: This book of theory here.
Abbott: My book of theory.
Costello: The book that explains the theoretical. What kind of theory does it explain?
Abbott: It’s knot theory.
Costello: Abbott!!!
3 comments March 18, 2009
Partitions of Graphs IX: The case of 13
This is the ninth in a series, the first being here: Part 1, and the previous here: Part 8.
Here is a Q1 graph for n=13
o
/
o-o-o-o-o-o-o-o-o-o
\
o-o
The corresponding Q1 partition is 5+5+3. Unfortunately this does not generalize. For instance, the following graph:
o
/
o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o
\
o-o
allows the partitions 5+5+3+3+3 and 6+5+5+3, so it is Q2.
So far we have found Q1 graphs (or proven that they don\’t exist) of all orders n up through 18. I have made very little progress with n=19. If anyone finds an order 19 Q1 graph, please let me know about it. I do have some more things to say about Q1 graphs and partitions, including work and suggestions by my friend Sean (as well as some more Q1 graphs). In my next post I will start to discuss those issues.
Add comment March 16, 2009
The Grapes of Math: A Review
I have three criteria for an excellent children’s math book: 1) it has to be exciting and intelectually accessible for children, 2) it has to hold my interest 3) it has to have good math.
The Grapes of Math by Gregory Tang, illustrated by Harry Briggs meets all of these criteria. Ostensibly it is a counting book, with lots of practice with mental addition and multiplication. Normally I would have no interest in such a book, so I was skeptical when my wife handed this one to me, but in truth this book is more about deep pattern-recognition schema fundamental to mathematics, while being appropriate for even the youngest children. I will say no more and let you check it out for yourself.
Add comment March 14, 2009
Partitions of Graphs VIII: The case of 11 (and 17)
This is the eighth in a series, the first being here: Part I and the previous here: Part 7.
We have shown that there are no Q1 graphs with n=5 nodes or with n=7 nodes. Also, in the case of n=9, it apears that the reason there are Q1 graphs is that 9 is divisible by 3 (3+3+3 being the Q1 partition). It is tempting to guess that for n=11 there are no Q1 graphs. This however is not the case. Here is one
o
|
o-o-o-o-o-o-o-o-o
|
o
The prohibited partition is 4+4+3. The easiest way to see this is to show that any partition which has a 1, 2, or anything larger than a 4 as a summand is allowed, so the only prohibited partitions have only 4s and 3s as summands. But there is only one way to represent 11 as a sum of 4s and 3s, namely 4+4+3. The same logic works to show that this 17 node graph is also Q1:
o
|
o-o-o-o-o-o-o-o-o-o-o-o-o-o-o
|
o
But adding another six nodes to the tail gives this graph which is not Q1:
o
|
o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o
|
o
Since there are two ways of representing 23 as a sum of 4s and 3s, namely 4+4+4+4+4+3 and 4+4+3+3+3+3+3.
Add comment March 13, 2009
Partitions of Graphs VII: The Cases of 5 and 7
This is the seventh in a series, the first being here: Part I, the previous here: Part VI.
In the previous post I defined a Q1 graph to be a graph G with q(G)=1. We found examples of Q1 graphs for every n between 2 and 10 except 5 and 7.
Let’s talk about the case n=1. There is only one graph with a single node. Here is a picture of it
o
Obviously p(o)=1 and q(o)=p(1)-p(o)=1-1=0, so there are no Q1 graphs for n=1. Let’s make the following:
Definition: If P is a partition prohibited by a Q1 graph, we will call P a Q1 partition.
Now for the case n=5.
Theorem 1: There are no Q1 graphs with five nodes.
Proof: Here are the partitions of 5:
5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
We will eliminate each of these in turn as possible partitions prohibited by a Q1 graph. In my previous post we saw that 5 cannot be prohibited by a Q1 graph. Let’s state that as a lemma. Refer to the previous post for a proof.
Lemma 0: Any Q1 graph with n>2 nodes is connected. In other words, n is not a Q1 partition.
Also, since 1+1+1+1+1 is allowed by every (five node) graph it cannot be a Q1 partition. In fact we can extend this result.
Lemma 1: Any partition that has a 1 as a summand is not Q1 (call such a partition a type 1 partition).
The idea behind the proof of Lemma 1 is that any connected graph, say with k nodes, has at least one node that can be cut off by snipping some edges without disconnecting the rest of the graph, to give a connected graph on k-1 nodes (plus a solitary disconnected node).
Lemmas 0 and 1 eliminate all partitions but 3+2 as possibilities for Q1 partitions. We take care of that with:
Lemma 2: Any partition of the form (m+k)+m+ . . . +m+k+. . .+k (let’s call this a type 2 partition, since it appears in lemma 2) is not Q1. In other words any partition with summands consisting of a bunch of k, a bunch of m and a single m+k is not Q1.
Proof of Lemma 2: Given a Q1 graph G, it is connected, by Lemma 0. Next, assuming a type 2 partition P: (m+k)+m+ . . . +m+k+. . .+k is prohibited by G, the partition (m+m+ . . . +m+k+k+. . .+k must be allowed by G. But since G is connected at least one of the size m subgraphs must be connected via an edge to at least one of the size k subgraphs. Color the nodes in these two subgraphs the same color to obtain a good coloring of G corresponding to P. Therefore P is not prohibited, a contradiction. Therefore P is not Q1. end of proof of Lemma 2.
3+2 is a type 2 partition, therefore it is not Q1. Since there are no partitions of 5 that are Q1, there are no 5-node Q1 graphs. This concludes the proof of Theorem 1.
Theorem 2: There are no 7-node Q1 graphs.
Proof: Here are the partitions of 7:
7
6+1
5+2
5+1+1
4+3
4+2+1
4+1+1+1
3+3+1
3+2+2
3+2+1+1
3+1+1+1+1
2+2+2+1
2+2+1+1+1
2+1+1+1+1+1
1+1+1+1+1+1+1
Eliminating the type 1 partitions and the partition 7 we have left:
5+2
4+3
3+2+2
These are all type 2 partitions:
5+2 = (3+2)+2
4+3 = (3+1)+3
3+2+2 = (2+1)+2+2
End of proof of Theorem 2.
We have seen that 5 and 7 do not permit Q1 graphs, but 9 does. In fact the reason 9 does is that it is divisible by 3. One might be tempted to guess that prime numbers do not admit Q1 graphs (with 2 and 3 being flukes). Of course the next number to test this guess on is 11. The case of n=11 will be the subject of my next post.
1 comment March 9, 2009
Partitions of Graphs VI: Q1 Graphs
This is the sixth in a series. The first is found here: Part I. The previous is found here: Part V.
I have defined q(G) to be:
q(G) = p(n) – p(G), where n is the number of nodes in G.
In other words q(G) is the number of partitions prohibited by G. We’ve seen graphs, G, with p(G)=1, that is with exactly one allowed partition. In fact we know that the one allowed partition is:
1+1+1+ . . . +1
and the graph consists of n nodes and no edges. But let’s say that we want a graph, G, with q(G)=1. I’ll call such a graph a Q1 graph (in fact if q(G)=k lets call it a Qk graph). It’s not quite as easy to find Q1 graphs as it was to find graphs with p(G)=1. For one thing it isn’t at all obvious what the one prohibited partition should be. A first guess might be that the prohibited partition should be n. This sounds plausible since in some sense the partition n is the alter-ego of the partition 1+1+1+ . . . +1. Following this lead we should look for graphs that are not connected, but that allow every partition of n other than n. Indeed, initially we find success:
q( o o ) = 1
and
q( o o-o) = 1
So far so good. We’ve done n=2 and n=3 (conspicuously skipping n=1, I’ll leave that case for you to ponder), but when we get to n=4 we hit trouble. If q(G)=1, with the partition 4 prohibited, then 3+1 must be allowed. That means that for a good coloring there are going to be three nodes that are the same color. All three nodes have to be part of a connected subgraph, but the other node, the fourth node, can’t be connected to those other three at all. In other words, the largest connected component of the graph has three nodes. If it were any bigger it would have four nodes and the whole graph would be connected, which we assumed wasn’t true. So there is a single solitary node floating all by it’s lonesome in space. But 2+2 is also allowed (every partition other than 4 is assumed to be allowed) which tells us that each node of G is adjacent to at least one other node (two nodes get colored red, two blue in a good coloring). But what about our single, solitary node floating in space? This says that he can’t be single or solitary or floating in space. You can’t be single, solitary and floating in space when you are closely tethered to your best buddy. That’s what we call a contradiction, which means that our hypothesis that q(G)=1 with 4 prohibited is impossible.
Of course in a previous post we’ve seen that
o
/
q( o-o-o ) = 1
with the prohibited partition being 2+2 (This is S4, I’ve drawn it slightly differently here). It took me some time to see that this is just the first of a whole family of graphs with q(G)=1.
Remark: If n is even, then
o
/
q( o-o-o-...-o-o-o ) = 1 (n even)
and the prohibited partition is 2+2+2+ . . . +2. If n is odd then
o
/
q( o-o-o-...-o-o-o ) = 0 (n odd)
Proof: We need to show that if there are an even number of nodes then 2+2+2+ . . . +2 is prohibited and all other partitions are allowed. To see that 2+2+2+ . . . +2 is prohibited is pretty easy. What would a good coloring look like? The node farthest to the right and on the bottom would be some color, let’s say it’s purple.
o
/
o-o-o-...-o-o-o
There must be two purple nodes and they have to be adjacent so the next node to the left has to be purple also.
o
/
o-o-o-...-o-o-o
But where does that leave the top node? High and dry, without a friend in the world. In other words it has to be a color other than purple, let’s say orange and it has to have an orange buddy, but there are none to be found.
o (Which other node should be orange?) / o-o-o-...-o-o-o
So 2+2+2+ . . . +2 is prohibited. Now we prove that every other partition is allowed. If P is a partition whose summands are not all 2’s then either P has a 1 as a summand or P has a summand that is 3 or greater. We consider thees two cases. First if P has a 1 as a summand then say that 1 gets colored purple. Then we color the node on the top purple
o / o-o-o-...-o-o-o
no other node is colored purple, and what remains of the graph is a path, so we will be able to find a good coloring for it. Here is an example of what I’m talking about. Say n=8 and P=4+3+1. We color P: and use this as instructions for coloring the graph. First we color the top node purple and then we color the first four of the path red and the next four green.
o / o-o-o-o-o-o-o
Here’s another example. A good coloring of 2+2+2+2+2+1+1:
o / o-o-o-o-o-o-o-o-o-o-o
Let’s address the other case of there being a summand of P greater than or equal to 3. Say the partition is 6+5+5+2+2+2, (n=22). We color P: 6+5+5+2+2+2 . Now we pick one of the summands which is 3 or greater. Let’s say we pick one of the 5’s. We color the 5 nodes farthest to the right the color of that 5. Let’s say we picked the green 5. What’s left over is a path.
o / o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o
In general pick any summand larger than 2 and color the right most nodes that color. What’s left will be a path and allow a good coloring no matter what the other summands are. This proves that all partitions other than the one consisting entirely of 2’s are allowed. Finally odd numbers do not have a partition consisting entirely of 2’s, so every partition of an odd number is allowed. QED.
So we have this family of Q1 graphs:
o / o-o-o-...-o-o-o
for even numbers, n. It turns out there is a similar family of Q1 graphs when n is divisible by 3. Here it is:
o / o-o-o-...-o-o-o-o
The proof that this is a Q1 graph when n is divisible by 3 (and a Q0 graph otherwise) is similar to the above proof. The prohibited partition is 3+3+3+ . . . +3. If P is a partition whose summands are not all 3, then there are three cases to consider: P has 1 as a summand, P has 2 as a summand and P has a summand that is 4 or larger. Here are three pictures illustrating the three cases respectively.
o / o-o-o-...-o-o-o-o
o / o-o-o-...-o-o-o-o
o / o-o-o-...-o-o-o-o
In each case what is left over is a path, so the rest of the graph can be given a good coloring.
We’ve found two families of Q1 graphs that give us examples for n even and n divisible by 3. So we have Q1 graphs for all n between 2 and 10 except n=5 and n=7. In my next post I will address the cases n=5 and n=7. In subsequent posts n=11 and n=13 will be addressed.
1 comment March 6, 2009
Partitions of Graphs V: Some Examples
This is the fifth in a series. See the first here: Part I, and the previous here: Part IV.
In my last post I said what I mean by p(G), when G is a graph. Namely, it is the number of partitions of n that are allowed by G. (n is the number of nodes of G. In fact through out this post G will always stand for a graph, and n for the number of nodes in G.) This is something that I completely made up. It is mostly just for fun, but I think that it might be interesting, and may even carry some significance. Also, remember that q(G) is the number of partitions prohibited by G. q(G)=p(n)-p(G).
Let’s get some examples under our belts. We’ll compute p(G) (and/or q(G)) for some specific examples of G.
Complete Graphs
I said in the previous post that p(G) is always between 1 and p(n), i.e. 
Below is K1
o
and here is K2
o-o
and K3
o
|\
o-o
And here is how I will draw K4
o-o
|X|
o-o
The X in the middle is supposed to be two edges that are crossed. I don’t think that there is a good way to draw K5 in ASCII. Here is a picture of K5 though:
Here the red dots are the nodes. Where the edges of the star shape cross there are not nodes.
It is pretty easy to see that p(Kn)=p(n): Every partition is allowed, because in fact every coloring is good. Said another way q(Kn)=0.
Edgeless Graphs
On the other extreme are the graphs with no edges at all:
o o o o o
The only allowed partition of this graph is 1+1+1+1+1, since any coloring with two or more nodes the same color is bad. Therefore:
p( o o o o o )=1.
Similarly, p of any edgeless graph is 1.
Stars
We’ve seen graphs that allow all partitions of n, and graphs that allow only one, what about something in between? The following graphs are called stars. Here are the stars S4, S6 and S7:
o
|
o
/ \
o o
o
|
o-o-o
/ \
o o
o o
\ /
o-o-o
/ \
o o
Of course the biggest star I can draw in ASCII is S9:
o o o
\|/
o-o-o
/|\
o o o
But you can have a star Sn for any whole number n (extra points for anyone who post a picture of S1,000,000). Here is my claim: p(Sn)=n. For example p(S5)=5, and here are the partitions that S9 allows:
5
4+1
3+1+1
2+1+1+1
1+1+1+1+1
It is pretty easy to see that these and only these partitions are allowed. Here are the good colorings:
o o \ / o / \ o o o o \ / o / \ o o o o \ / o / \ o o o o \ / o / \ o o o o \ / o / \ o o
I’ll leave it to you to convince yourself that no other partitions are allowed.
Paths
We went a little overboard with the complete graphs. Not nearly that many edges are needed for p(G) to be equal to p(n). In fact what I consider to be the most important example I’ll talk about in this post is the path. Below is a P3
o-o-o
and a P4
o-o-o-o
and for fun a P13
o-o-o-o-o-o-o-o-o-o-o-o-o
It is not hard to see that paths allow every partiton of n. Say n=13, and the partition you are interested in is 7+3+2+1, then to get a good coloring just color the first 7 nodes red, the next 3 blue, the next two green and the last one pink.
o-o-o-o-o-o-o-o-o-o-o-o-o
Pretty slick huh? For paths (and complete graphs) it seems more natural to talk about the function q. Remember that q(G)=p(n)-p(G), so q(Pn)=0. Paths, I think, are beautiful examples of graphs G with q(G)=0. In my next post I will talk about some slick examples of graphs G with q(G)=1.
1 comment March 2, 2009
Partitions of Graphs IV: Partitions of Graphs
This is the fourth in a series. (See also Part I: Partitions of Whole Numbers, Part II: Graphs, Part III: Ramanujan meets Kevin Bacon.)
Here are the partitions of 7:
7
6+1
5+2
5+1+1
4+3
4+2+1
4+1+1+1
3+3+1
3+2+2
3+2+1+1
3+1+1+1+1
2+2+2+1
2+2+1+1+1
2+1+1+1+1+1
1+1+1+1+1+1+1
So p(7)=15.
Here’s a graph:
o
/
o-o
\
o
I could also have drawn it like this:
o
|
o
/ \
o o
What I plan to tell you in this post is what is meant by:
o
/
p( o-o )
\
o
Here are some values of p(n), where n stands for a whole number.
p(1)=1
p(2)=2
p(3)=3
p(4)=5
p(5)=7
p(6)=11
p(7)=15
p(8)=22
p(9)=30
p(10)=42
Connectedness
I have one more thing to mention about graphs before saying what the partitions of a graph are. If I ask you what you see in the picture below, you will probably say two graphs
o
/ \ o-o
o o \|
| / o-o
o-o
and you would be right, of course. But, you could equally well take this to be one graph. It has nodes (nine of them) and edges (nine of them, also), it just happens to break up into two pieces. We say that the above graph is not connected. Of course a connected graph is one where you can get from any node to any other by traveling along edges. Below is a connected graph (it’s kind of a big one).
o-o-o o-o-o-o-o-o-o-o-o o o o
\ | / / / |
o-o-o-o-o-o o-o-o o-o-o-o-o-o-o-o
\ |
o-o-o-o-o
We will be dealing with the issues of connectedness and disconnectedness. In fact, below is kind of a “degenerate” example, a graph that is totally disconnected. It has no edges at all (it’s a little on the big side also, with 14 nodes).
o o o
o
o o o
o
o o o
o o o
The Partitions of a Graph
Now we are ready for what I have been building up to. We need a graph to work with. Let’s use the one below
o
/
o-o
\
o
Let’s call this graph S4. In a moment I will say what p(S4) is, but first I need to say what it means for the graph S4 to allow a partition or to prohibit a partition. Our graph S4 has four nodes, so we will be working with the number n=4 in this example. Let’s choose, at random (more or less), a partition of 4. Say 2+1+1. Now color each of the summands (the numbers that are being added) in this partition. They each have to be a different color. I will use red, blue and green: 2+1+1. Next, we color the nodes of S4, using 2+1+1 as an instruction guide. In other words, since the first summand is a red 2 we will color two nodes red. The second summand is a blue 1, so we color exactly one node blue and the third is a green 1 so we color one node green. It might look like this:
o / o-o \ o
Once the nodes are colored, you consider one color at a time. First red. Erase all of the graph, except the red nodes and any edges that go from a red node to a red node. It will look like this:
o o
Call this graph the red subgraph (a subgraph is just a graph within a graph, e.g. our red graph within the graph S4). Now ask yourself if what you have left is connected. If the red subgraph is connected, then go on to the blue subgraph and if that is connected then look at the green subgraph. In this case we stop at red, since the red subgraph is not connected. If any of the monochromatic subgraphs is not connected then we call that coloring of the nodes a bad coloring. If each of the monochromatic subgraphs is connected then it is a good coloring. The coloring we chose here is bad.
But, you are probably already thinking that I could have chosen a different coloring that would have been good. Here is one such good coloring:
o / o-o \ o
The monochromatic subgraphs look like:
o / o
and
o
and
o
Yes, a graph consisting of a single, lonely node, with no edges, is considered to be connected. Since all of these monochromatic graphs are connected, this is a good coloring.
Given a partition of n (in this case n=4 and the partition is 2+1+1, if there is a coloring of G (in this case the graph S4) associated with this partition that is good, then we will say that G allows the partition. If every possible coloring of G associated with 2+1+1 is bad, then we will say that G prohibits the partition 2+1+1.
good coloring: all of the monochromatic subgraphs are connected bad coloring: at least one of the monochromatic subgraphs is not connected. allowed partition: at least one coloring of G (following the partition as instruction guide) is good. prohibited partition: all of the colorings of G (following the partition as instruction guide) are bad.Let’s figure out which of the partitions of 4 are allowed by the graph S4. Here are the partitions of 4:
4
3+1
2+2
2+1+1
1+1+1+1
We color the first partition: 4. This tells us to color all four nodes of G red:
o / o-o \ o
In this case the red subgraph is the whole graph and it is connected so this is a good coloring and the partition 4 is allowed by S4.
We color the next partition: 3+1. Now we want to see if we can use these instructions to get a good coloring of S4. Of course we can:
o / o-o \ o
The red subgraph is:
o / o-o
and the blue one is:
o
both are connected so this coloring is good and 3+1 is an allowed partition. Of course there is also a bad coloring associated with 3+1. It is pictured below.
o / o-o \ o
The red subgraph is not connected, so this coloring is bad, but that doesn’t matter. There is at least one good coloring so 3+1 is an allowed partition.
We color the next partition: 2+2. Now we get into trouble, because using these instructions always leads to a bad coloring. Here is one of the bad colorings:
o / o-o \ o
In this case the red subgraph is not connected. It is pretty easy to see that you can’t color two nodes red and two blue and get both the red and blue subgraphs connected. Since all of the colorings are bad, 2+2 is a prohibited partition.
The next partition is 2+1+1. We have already done this one, and seen that it is an allowed partition.
We color the last partition: 1+1+1+1. Here is a coloring of the graph:
o / o-o \ o
Since every node is a different color all of the monochromatic subgraphs are connected. So this is a good coloring and 1+1+1+1 is allowed.
So for the graph
o / o-o \ o
which we are calling S4, the following are allowed partitions:
4
3+1
2+1+1
1+1+1+1
and 2+2 is the only prohibited partition. We say that p(S4)=4.
In general p(G) is the number of allowed partitions of n, where n is the number of nodes in G.
Here is a summary:
good coloring: all of the monochromatic subgraphs are connected bad coloring: at least one of the monochromatic subgraphs is not connected. allowed partition: at least one coloring of G (following the partition as instruction guide) is good. prohibited partition: all of the colorings of G (following the partition as instruction guide) are bad. p(G)=# of partitions allowed by G.Here are some things to think about (henceforth n will always be the number of nodes in G):
p(G) could also have been defined as p(n) minus the number of partitions of n prohibited by G. In fact lets call q(G) the number of partitions of n prohibited by G. In other words q(G)=p(n)-p(G), or p(G)=p(n)-q(G).
p(G) is always between 1 and p(n). (Every graph allows at least one partition. Do you know which one it is?).
Also, think about some graphs yourself and calculate p(G) for some of them.
In my next post I will talk more about p(G) and q(G), especially for some specific example of graphs.
1 comment February 24, 2009
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.
1 comment February 22, 2009
Partitions of Graphs II: Graphs
This is the second in a series. The first being Partitions of Graphs I.
A graph is what most people call a network. It’s a bunch of dots (called nodes) connected by lines (called edges). Here are some pictures of graphs:
Loads of real-world systems can be modeled by graphs. Some examples are: the Web, with pages as nodes, and hyperlinks as edges (Google makes lots of money off of having a good mathematical grasp of the graph-theory intrinsic to the Web); Maps, with cities as nodes and freeways as edges; A chess game, with position as nodes, and legal moves from one position to the next as edges.
Mostly I like graphs because they are fun to draw and play with.
For this series I’m going to have to draw some graphs. I think what I want to do here is go totally old school and draw my graphs as ascii art. I do this because it is easy and it should be sufficient for my purposes. Most graphs you wouldn’t be able to draw very well with ascii art, but the ones I will need I don’t think I will have any problems with.
So I will use
o
as my nodes and these lines
- \ / |
as my edges. The graph below
becomes:
o
/
o o
|/ \
o o
| |
o o
Ok, not as pretty, and I haven’t labeled the noeds here, but humor me. Next post I’ll talk a little more about graphs and partitions of whole numbers and why I want to relate the two. Mean while, have fun drawing some graphs.
2 comments February 20, 2009
