MATH with my KIDS

The UHT

There are two things that you need to know about the UHT.

First YOU NEED TO KNOW THAT IT IS FALSE!

Second you need to know what it is. I’ll explain that right now.

The UHT is the Universal Homomorphism Theorem. Don’t let the words scare you. I’ll explain them in a second. Chances are you or someone you know believes in the UHT.

A homomorphism is any mathematical operation that you can do to a number (we call those functions) with the property that if you do it to the sum of two numbers, you get the same answer as if you do it to the two numbers seperately and then added the results together.

In math-speak, $f$ is a homomorphism if $f(x+y)=f(x)+f(y)$ .

The UHT is the belief that all functions are homomorphisms.

Here’s the problem: THERE ARE LOTS AND LOTS OF FUNCTIONS THAT ARE NOT HOMOMORPHISMS!

Here’s one example:

The square function $f(x) = x^2$

It is not true that $(x+y)^2 = x^2 + y^2$ . For instance, does $(1+1)^2 = 1^2+1^2$ ? If you believe that the answer is yes, then come to my house and I will give you $1^2 + 1^2$ dollars if you will give me $(1+1)^2$ dollars.

Today a friend told me of a group of students who insisted that $\sin(x+y)=\sin(x)+\sin(y)$ . The students also said that one of their teachers had taught them this (supposed) fact. The true fact is that $\sin(x+y) = \sin(x)\cos(y) + \cos(x)\sin(y)$ . When the teacher was confronted he or she (is reported to have) said “Well, we were teaching them to do it that way ( $\sin(x+y) = \sin(x)\cos(y) + \cos(x)\sin(y)$ ), but they weren’t getting it, so we just started teaching them this easier way ( $\sin(x+y)=\sin(x)+\sin(y)$ ).”

This teacher knew that the UHT is false, but taught it to the students anyway.

Let’s leave the math-speak behind and talk plain English. The sine function describes waves. Let’s say you’re standing in the ocean on a sandy beach. A wave approaches. Now the water level is at your ankles. In a couple of seconds it is up to your knees. What happens next? You know that in a couple more seconds the water-level will drop back to ankle-level. But the UHT says that it doesn’t. The UHT says that the water will keep rising. A couple seconds after being at your knees it will be at your waist. Then your chest. By the end of the day the entire continent will be inundated. But the wave won’t stop there. It will keep going. Rising and rising and rising forever. That is what the UHT says. Let’s all be glad that the UHT is false. Let’s hope that there are not any other teachers that teach it.

2 comments August 26, 2009

How to Eat an Equilateral Cheeseburger

My friend Sean worked out an elegant and practical solution to the Cheeseburger problem of my previous post. I will try to summarize it here.

There are fifteen toppings. To make things simpler we’ll represent them with the numbers one through fifteen.

1 = Mayo
2 = Relish
3 = Onions
4 = Lettuce
5 = Pickles
6 =Tomatoes
7 = Grilled Onions
8 = Grilled Mushrooms
9 = Ketchup
10 = Mustard
11 = Jalapeno Peppers
12 = Green Peppers
13 = A-1 Sauce
14 = Bar-B-Q Sauce
15 = Hot Sauce

Arrange these numbers around a circle at equal intervals, like the hours of a clock with fifteen rather than twelve hours. Each cheeseburger can be represented on this circle as three points. Think of these three points as the vertices (corners) of a triangle. As has been shown in the comments of the previous post, there are 455 cheeseburgers total. So the totality of cheeseburgers are represented by 455 triangles inscribed in the circle, which is a tangled, nasty mess (but not as big a mess as all 455 cheeseburgers sitting on your kitchen table).

Let’s get a handle on the mess. We need some notation to make it easier to talk about these triangles. If a triangle has vertices at points marked x, y and z, we’ll denote it by (x,y,z). Some of the triangles will have the same shape as each other. Others will be differently shaped. For instance, (1,2,3) has the same shape as (2,3,4), but (1,2,4) has a different shape than (1,2,3).

In fact there are fifteen triangles with the same shape as (1,2,3) (including (1,2,3) itself). They are: (1,2,3), (2,3,4), (3,4,5), (4,5,6), (5,6,7), (6,7,8), (7,8,9), (8,9,10), (9,10,11), (10,11,12), (11,12,13), (12,13,14), (13,14,15), (1,14,15) and (1,2,15). Each of these triangles can be obtained from (1,2,3) by rotating it around the circle. These fifteen triangles together form an equivalence class.

Likewise there are fifteen triangles with the same shape as (1,2,4). Said another way (1,2,4) has fifteen triangles in its equivalence class (but we need to be careful here to emphasize that we are considering (1,2,4) and say (1,3,4) to have different shapes: they are mirror images of each other, but not rotations of each other).

In all, the 455 triangles fall into 31 equivalence classes. 30 of these classes have fifteen triangles. The final equivalence class consists of five triangles. More on that in a moment.

The strategy is this: Pick an equivalence class. Rotate through all of the cheeseburgers in that class. Next move on to another equivalence class.

Let’s list the equivalence classes by writing down a single triangle in each class. OK, I’m not actually going to write all of them out, but I will do the next best thing. You’ll see.

First we have twelve equivalence classes with triangles of the form (1,2,n), where n=3,4,5,…,14. We don’t allow n=15 (i.e. (1,2,15) because that is the same class as (1,2,3). That gives us 180 cheeseburgers.

Then there are nine classes of the form (1,3,n), where n=5,6,7,…,13. (n=15 would give the same class as (1,2,4) and n=14 the same class as (1,3,5)). That’s another 135 cheeseburgers.

Next we get six classes of the form (1,4,n), with n=7,8,9,…,12. Another 90 cheeseburgers.

Similarly there are three classes of the form (1,5,n), with n=9,10,11. 45 more cheeseburgers.

Finally, we have our one strange class with only five cheeseburgers in it. This class is represented by (1,6,11). Let’s list all of the triangles in this class: (1,6,11), (2,7,12), (3,8,13), (4,9,14), (5,10,15). These are the five equilateral triangles in the set. Just for fun let’s list the five cheeseburgers that these triangles represent.

The equilateral cheeseburgers are:

Mayo, Tomatoes, Jalapeno Peppers

Relish, Grilled Onions, Green Peppers

Onions, Grilled Mushrooms, A-1 Sauce

Lettuce, Ketchup, Bar-B-Q Sauce

Pickles, Mustard, Hot Sauce

So go into a burger joint. Ask for an equilateral cheeseburger. See what kind of look you get. Then just tell them you want mayo, tomatoes and jalapeno peppers on it.

OK, seriously, back to the math for a minute. Sean also realised that you can rotate through the classes such that no two burgers in a row have any of the same toppings. Great! That’s what I was asking for in the first place. Let’s use our first equivalence class as an example. We start with the triangle (1,2,3). Now we can rotate one slot by adding one to each number in this triple to get (2,3,4). But that’s not what we want: we would have two burgers in a row where only one topping changed. So instead let’s rotate three slots so that none of the toppings are the same twice in a row. We get (1,2,3) then (4,5,6). Keep going to get: (7,8,9), (10,11,12), (13,14,15). Now when we do the next addition: (13+3,14+3,15+3) we have to be careful to do clock arithmetic on a 15-hour clock. That is, counting up one from 15 gives one, rather than 16 (we mathematicians call this modular arithmetic). So (13+3,14+3,15+3)=(1,2,3). That’s a problem because we’ve already visited the triangle (1,2,3), but there are still ten triangles that we haven’t visited in this class. Our problem was moving three slots at a time. 15 is divisible by 3. In fact, what we should do is pick a number that is relatively prime to 15, which means a number that is not divisible by three or five (the prime factors of 15). Four will work. So start with (1,2,3). Add four to each slot: (5,6,7). Add four again: (9,10,11). And again: (13,14,15). Again: (2,3,4). Continue in this manner. Here is the list we get for this whole equivalence class:

(1,2,3)

(5,6,7)

(9,10,11)

(13,14,15)

(2,3,4)

(6,7,8)

(10,11,12)

(14,15,1)

(3,4,5)

(7,8,9)

(11,12,13)

(15,1,2)

(4,5,6)

(8,9,10)

(12,13,14)

and we’re done with this class. We will now move on to the next class starting with (1,2,4). For this class rotating four slots will also work:

(1,2,4)

(5,6,8)

(9,10,12)

(13,14,1)

(2,3,5)

(6,7,9)

(10,11,13)

(14,15,2)

(3,4,6)

(7,8,10)

(11,12,14)

(15,1,3)

(4,5,7)

(8,9,11)

(12,13,15)

Done with that class. The next one in line starts with (1,2,5). Now if we rotate by four we will get overlap between successive triangles. Instead, we could choose to rotate by two:

(1,2,5)

(3,4,7)

(5,6,9)

(7,8,11)

(9,10,13)

(11,12,15)

(13,14,2)

(15,1,4)

(2,3,6)

(4,5,8)

(6,7,10)

(8,9,12)

(10,11,14)

(12,13,1)

(14,15,3)

And we’re done with that class. And so the process continues through all 455 cheeseburgers. So the amount we rotate depends on the equivalence class we’re working in, but we can always pick a rotation that is both relatively prime to 15 and doesn’t result in any overlap between consecutive triangles. In fact, it turns out that we can always choose our rotations from the set {1,2,4}.

Notice that my first 15 cheeseburgers will be isoceles. Then I will be eating scalene burgers for quite some time. Not until the very end do I get to the equilateral cheeseburgers. I have decided that I am going to try to do two per month. That way it will take me just under 19 years to finish. Read Mayo, Relish Onions: A Cheeseburger Review for an account of the first trial of this experiment. Bon Appetit!

3 comments August 12, 2009

Two Problems in Elementary Cheeseburger Theory

A favorite hamburger joint of mine has the following 15 choices for toppings:

Mayo
Relish
Onions
Lettuce
Pickles
Tomatoes
Grilled Onions
Grilled Mushrooms
Ketchup
Mustard
Jalapeno Peppers
Green Peppers
A-1 Sauce
Bar-B-Q Sauce
Hot Sauce

After much experimentation, I’ve decided that three toppings is about the right number to have on any one burger (too many toppings masks the flavor of the burger itself). So, being a mathematician, I’ve decided that I should try all possible combinations of 3 toppings. Here are the problems then:

1) If I visit the burger joint once a week (ordering one burger per visit), how long will it take me to reach my goal?

2) Can you devise an algorithm for working through all combinations that is not too complicated and provides a reasonable amount of variation (for instance, I don’t want to have 13 visits in a row where I have mayo and relish and one other topping. I probably don’t even want that for two or three visits in a row).

6 comments July 29, 2009

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 being 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

prohibits 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.

grapes

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

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:

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:

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. $1\le p(G)\le p(n)$ . So are there graphs with p(G)=p(n)? Yes, in fact, there are. the easiest example is probably the complete graph on n nodes. A compete graph has an edge between every pair of nodes. It is usually denote Kn (the particular number being substituted for n).

Below is K1

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:

graph31 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:

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:

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

Next Posts Previous Posts

MATH with my KIDS

The UHT

How to Eat an Equilateral Cheeseburger

Two Problems in Elementary Cheeseburger Theory

Abbot and Costello Meet Low-Dimensional Topology

Partitions of Graphs IX: The case of 13

The Grapes of Math: A Review

Partitions of Graphs VIII: The case of 11 (and 17)

Partitions of Graphs VII: The Cases of 5 and 7

Partitions of Graphs VI: Q1 Graphs

Partitions of Graphs V: Some Examples

Complete Graphs

Edgeless Graphs

Stars

Paths

my kind of math

Meta

Blog Stats

Blogroll

November 2009
S	M	T	W	T	F	S
« Oct
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30