Partitions of Graphs XI: The Case of all Sufficiently Large n

This the eleventh in a series, the first being found here: Part 1, and the previous here Part 10.

In this post I provide examples of Q1 graphs of all orders n, for sufficiently large n.  In particular this will provide examples of Q1 graphs of almost all prime orders (which are the cases for which I have not previously provided examples).  This family is very closely related to the family of Q1 graphs for composite orders.  If n can be written as:

Where and .  Of course the first inequality implies:   If n has the form , then there is exactly one partition of n whose parts are all m’s and (m-1)’s; namely, P = (m,…,m,m-1,…,m-1), where there are i m’s and j (m-1)’s.  In this case, P is a Q1 partition, and the following is a Q1 graph prohibiting P:

Again, m can either be even or odd.  If m is even, then we let m=2k and the graph looks like this:

If m is odd then m=2k+1 and the graph looks like this:

To prove that this graph is Q1 we must show that the partition composed entirely of m’s and (m-1)’s is prohibited and any partition not composed entirely of m’s and (m-1)’s is allowed.  The argument that any partition composed of m’s and (m-1)’s is prohibited is essentially the same as for the previous family of Q1 graphs of composite order.  Likewise for the proof that all other partitions are allowed except for the case of partitions composed of m’s, (m-1)’s and 1′s (with at least one 1).  If there are at least two 1′s, then we are good, as demonstrated here:

If there is at least one m, again, we are good:

The only case left is a partition composed of (m-1)’s and exactly one 1, but this partition does not exist when n satisfies the condition (*).  I claim that all sufficiently large numbers can be written in the form (*) and in particular that all prime numbers larger than 13 can be (though 13 itself cannot).  I will leave a proof of this to a future post.

An Evening of Math I

My wife has taken on the challenge of homeschooling our children this year. My main participation in this is a weekly math session with the kids in the evening on any subject of my choosing!

Tonight was our first session. I decided to do partitions with them. I am priming them to be able to help me with my research on Q1 graphs.

We pulled out cubical blocks and I told the kids to make partitions with them. The hardest part about this is keeping my mouth shut and staying out of their way.

B invented Ferrers diagrams. Meanwhile I set A to work on making all partitions of the small numbers. She found 1 partition of 1, 2 partitions of 2 and 3 partitions of 3. She started working on 4 and found 4 partitions. Then B chimed in with a 5th partition of 4. This upset A and she refused to accept it as a partition, because it didn’t follow the pattern that she had seen. She stormed off, but came back and was ready to accept the 5th partition of 4.

I tried to get them thinking about how we could know that we had got all of them. They haven’t come up with anything along those lines yet. B (of his own volition) started working on an algorithm to generate all of the partitions of a given number. The algorithm needs work, so far only generating the n partitions of n: (1,1,…,1), (2,1,1,..,1), (3,1,1,..,1),…,(n-1,1), (n). He was also working on an algorithm for getting partitions of n+1 from partitions of n. I think that one was pretty incomplete too.

Their minds were still going, but it was getting late, so I sent them to bed. It was a good evening of math.

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.

Part VIII: The Case of 11 (and 17)

Partitions of Graphs I: Partitions of Whole Numbers

I’ve been meaning to blog about this for some time.  I guess that I had just better do it.  But it will be in pieces.  A little at a time.  That’s the way blogs are supposed to be right?

Let’s say you give me a whole number, like 5.  A partition of 5 is some other whole numbers that add up to 5.  For instance 4+1 is a partition of 5.  OK, everyone knows that 4+1=5.  So what’s the game we are playing here?  We are counting 4+1 and something else like 3+2 as different things.  Never mind that they equal the same thing, we are going to count them as different.  However, we want to count 4+1 as the same as 1+4.  We also want 3+2 to be the same as 2+3.

Ok, those are the basic rules.  Matheticians like to count things, so let’s count how many partions of 5 there are:

5 (did I mention that this one counts even though there isn’t a plus sign in it?)

4+1

3+2

3+1+1

2+2+1

2+1+1+1

1+1+1+1+1

That’s all of them (how do I know that? . . .).  You can check yourself.  There are seven.  Let’s do another one.  The partitions of 4 are:

4

3+1

2+2

2+1+1

1+1+1+1

There are five of them.

Try some yourself.

Ok, this seems pretty stupid.  2+2=4, duh. But counting how many partitions each whole number has is a big deal. There’s lots of beautiful math going on here and this is an active area of current research.  The partitions of whole numbers touches lots of other areas of math in strange ways.

So what do I have to say about partitions of whole numbers?  Not much today, except that I find them fascinating and a while ago I decided I wanted to relate them to another family of intriguing mathematical objects, what mathematicians call graphs and non-mathematicians usually call networks . . .What those are will be the subject of my next post.  Stay tuned.

Part II: Graphs

Baseball

Happy Ruth-Aaron days!

Sequences and Creative Math for Kindergartners

I visited my kids’ classes for career day in May. I have a son in Kindergarten and a daughter in pre-K. I also visited two other kindergarten classes. I told the kids that I am a research mathematician: mathematician means I do math. Research means I do math that nobody has ever seen before, math that I make up.

I mentioned that math is lots of things: It’s thinking about shapes and numbers and patterns, and other stuff. This day we were going to do numbers and patterns.

I showed them a board covered with three lines of (blank) sticky notes. Under each note was a number.The point is to try to guess which number is coming next.

We started with the blue line of numbers.

Once I had uncovered the 1 and 2 almost everyone expected the next number to be 3.

When I showed them that it was a 1, they caught on pretty quickly.

They had fun shouting out the 1-2-1-2-1-2 pattern as I frantically tried to keep up with them on the board.

Next, the pink ones.

I started by showing the 1-2-1 with a warning that I was being tricky. A 2 should come next, right? Wrong! But I didn’t tell them what it was yet. I put the sticky notes back on and explained that I was going to pull them off in a different order to see if it gave them a hint. (At this, some kids suggested I pull them off starting at the right instead of the left.)

I pulled off every other sticky: 1-skip a sticky-1-skip a sticky-1-skip… Okay, done with the ones. Next we have:

2-skip a sticky-2-skip a sticky-2-skip… (pulling off every other sticky that is left after the first pass). Okay, done with the twos. So the next one should be (the one that everyone thought should be a 2):

It’s a 3! And most of the students guessed that it was a 3!

And so it goes: 3-skip a sticky-3-skip a sticky-3 skip…

Next we have the fours: 4-skip a sticky (at this point we hit the end of the board, but if the board were longer…we would continue 4-skip a sticky-4-skip a sticky-4-skip…

Only one pink number left…

Everyone knows it’s a 5 by now! If we had a long enough board we would have 5-skip a sticky-5-skip a sticky-5-skip…

The pink numbers are:

1-2-1-3-1-2-1-4-1-2-1-3-1-2-1-5-1

Some interesting things (I think) about these pink numbers: Once you’ve done the ones and twos the row looks exactly like it would if you had pulled off the same patterns on the blue row! Nevertheless, most kids pick up on the fact that 3 should come next (well…I did give a big clue “done with the ones! . . . Done with the twos!”)

These pink numbers are called the ruler sequence, which comes up in the towers of Hanoi problem.

Now for the greens (the stickies look yellow in these pictures, but they are really green (yellowish-green)).

What do you think I will start with? Most kids had figured that I am into ones by now. So naturally, I start with a one again.

This row is really sneaky (but usually the kids understand it before their teachers! A testament to the freedom that young minds who haven’t had mathphobia drilled into them are capable of!), so I give a big hint. What do we have so far (on the green row)? One. How many ones? One one.

So that is what comes next. You start with a 1 then you say “look, it’s 1 one,” and that’s what you put next 1-1.

Now what do you have? 1-1-1. You have 3 ones. So next comes:

3-1.

Now you have 1-1-1-3-1. Four ones and one three. So next is:

4-1-1-3.

Now you have:

1-1-1-3-1-4-1-1-3. That is, six ones, two threes, and one four. So next will be:

6-1-2-3-1-4.

And now you have:

1-1-1-3-1-4-1-1-3-6-1-2-3-1-4. That is eight ones, one two, three threes, two fours and one six.

There is only room on the board to put 8-1. But if we had more room we would keep going. If we had paper going all the way around the school… I asked the kids if they thought we would ever get a 5. We haven’t so far! (At this someone always pointed out that we got a 5 on the pink line. A good observation! But we are just looking at the green line now.) What about 10? If we kept going would we get a 10? Would we ever get a 20? Or 100? Would we ever get a thousand or a million or a billion?

I’m pretty sure that you do get a 5 and a 10. I don’t know about 20, 100, 1,000, 1,000,000 or 1,000,000,000. I’m guessing that you do get them… Why? well, my reasoning is this: in some sense you have infinitely many chances to hit those numbers. Maybe at one point you will have 20 ones. If not, maybe you will get 20 twos. Of course maybe you will skip right over 20 twos. So maybe you will get 20 threes or 20 fours or 20 fives or…, you get the idea.

I told the kids that I didn’t know if you ever get 20 or 100 or 1,000. All I know is that you keep getting bigger and bigger numbers (can you see why?). I pointed out to the kids that this is a math question that I don’t know the answer to, and (as far as I know) neither does anybody else. This is math research, and it’s math research that they can do! They can figure out if we ever get a 5 or a 10. A million…probably they won’t figure that out until they learn some computer programming…

The kids were perfectly willing to accept that this is a math question that has an answer, but nobody knows that answer yet.

As for me, I’m conjecturing (conjecture=educated guess) that if you continue with the blue numbers, you will eventually hit any positive, whole number that you might care about. I already told you my reasons for making this conjecture. Can you prove it? Can you prove me wrong? If you’re a teacher, give the problem to your students. Maybe they’ll have an idea about it. Then let me know.

Finally, I wanted to let the kids make up their own number sequences. I handed out sheets of paper with five slots for numbers and five sticky notes. I told them that they could write any numbers they want in the blanks. They could be tricky, or they could be easy (like 1-1-1-1-1). Then, cover them up, and see if someone can guess the numbers.

Do they have to be able to articulate some reasoning for the patterns behind their numbers? No. But if they can, that’s great. There doesn’t have to be any reasoning at all. The point of this exercise was for the kids to do some free-form creative math. Just release your inhibitions (actually the kindergartners don’t have many inhibitions. The grown-ups on the other hand…) and write down some silly or crazy or boring or weird or hard-to-guess or happy, or sad pattern. The kids loved this part. They especially loved seeing if I could guess their numbers.

Let me know what you think about these sequences and this activity!

Synchronicity

I first heard the word synchronicity when I was sitting in an airport, waiting for a plane, working on this math problem (for fun) and over-hearing a man’s cell phone conversation. I thought that it was a good word for this phenomenon. Here it is:

Have you noticed that 3 times 7 is 21 and if you expand 7 base 3 it is 21. That is:

This seems like an interesting coincidence. Could it be that this happens for any other numbers? Maybe it happens infinitely often, maybe never. Asking such questions is where the adventure begins. Of course we are implicitly working base 10 here. That is, in the first line the string of numerals “21″ is interpreted as a base 10 number. In the second one it is (explicitly) interpreted base 3. You could allow 10 to be replace by other bases also.

If we restrict our attention to base 10 (in the first line), I claim that, by exhaustive computer search, there are only five other instances of this phenomenon. They are:

and

and

and

and

and