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.

Partitions of Graphs X: The Case of Composite Integers

This is the tenth in a series, the first being found here: Part 1, and the previous here: Part 9.

In this post I introduce a family of graphs that provides examples of Q1 graphs for all composite orders.  If n is composite then it has a partition of the form m+m+…+m, where 1<m<n.  For future convenience I am going to start using a different notation for partitions. Rather than m+m+…+m, I will write (m,m,…,m).  I claim that (m,m,…,m) is a Q1 partition and the graph below is a Q1 graph that prohibits it

The above picture is ambiguous.  I need to tell you how many vertices are in each section.  There are two cases.  If m is even then m=2k for some k.  In that case the graph looks like this:

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

Proof of claim:  To demonstrate that this graph is Q1, I have to convince you of two things:

1) That the partition (m,m,…,m) is a prohibited partition, and

2) that all other partitions P are allowed.

First, suppose that (m,m,…,m) were an allowed partition.  Then consider the vertex labeled a below.  It must be contained in a connected subgraph of order m (one of the monochromatic subgraphs of a good coloring).  The the set of vertices labeled A must be in the same subgraph with a (that is colored the same color).  A only contains k+1 vertices, so we need more colored the same color as a.  At this point there appears to be a choice: should the vertex labeled b be the same color as a?  If it is the same color, then the row of vertices on the bottom right will be connected to no other vertices other than each other, but this would be a monochromatic subgraph of at most k vertices, which would not make a good partition.

Therefore, the vertex labeled b is not colored the same color as a, and so there are no other choices for the monochromatic subgraph of a than the one below:

But of course this would leave the vertex labeled c disconnected, this is a contradiction since a good coloring would have c in a monochromatic subgraph of size m.

Now for part 2) All other partitions P are allowed.  If the parts (coordinates) of P are not all m then there is at least one (call it i) that is not equal to m.  There are three subcases: a) i<k+1, b) k<i<m or c) m<i.

Subcase a) Let a monochromatic subgraph of size i be the one circled below.  As shown by the green line, the remaining graph contains a Hamiltonian path and so is Q1 and can be partitioned according to the remainder of P.

Subcase b) Let a monochromatic subgraph of size i be the one circled in red below.  Again, a Hamiltonian path for the remainder is shown in green, so we are done as in the previous subcase.

Subcase c)  Let a monochromatic subgraph of size i be the one circled in red below.  What remains is a path, and we are done.

We are now left to wonder for which prime orders there are Q1 graphs (we have seen that for orders 2 and 3 there are Q1 graphs and for orders 5 and 7 there are not.  We have also seen several other prime orders for which there are Q1 graphs.)  My next post will address this issue further.

Part 11

Evening of Math VI

It was late and rushed tonight, but I did manage to do some math with the kids. Actually, A was throwing fits, so I put her to bed. I had B working on the fact that if you have a connected graph on 5 vertices then there is a connected subgraph on 4. He worked out this conjecture himself, but doesn’t have any justification for it. I’m thinking he should develop the idea of a spanning tree, but I’m not sure how to nudge him in that direction. I guess I’ll have to think up an intermediate problem.

A Morning of Math

I’ve been sick and had to stay home from work the last several days. This morning I told my kids that they could choose to put away their clothes or do math. They chose math. I set both B and A working on different problems in our partitions of graphs research project. B had previously shown that 2+2 is a Q1 partition with the claw being it’s Q1 graph. I asked him to decide whether any of the other partitions of 4:
4
3+1
2+1+1
1+1+1+1
could be Q1. He started with 1+1+1+1. He said this partition you can always make with any 4-vertex graph, so it is not Q1. Next he tackled 2+1+1. He gave me an algorithm to make this partition from any (connected [all of our graphs start out connected so far. I think next time I might introduce the idea of a graph not being connected and still being considered one graph]) 4-vertex graph. Here is the algorithm: choose two adjacent vertices. Do not cut the edge between them, but cut all other edges in the graph. This gives the partition 2+1+1. Next he dealt with the partition 4. If the graph is connected, then of course 4 is a partition you can make trivially (again we’ll have to come back to this once we talk about starting with disconnected graphs). 3+1 he doesn’t believe can be Q1. He thinks that it may also be a partition allowed by any connected 4-vertex graph. He is going to think about why, and we’ll return to it at our next session.

A had started analyzing what she called the ice cream cone. I had her redraw it for me today. I think that it had more vertices before, but today it ended up being a 4-cycle (the square). We checked one by one that you can make any partition of 4 with this graph. Next I had her think about the 5-cycle, then 6 and 7 and finally 8. After doing 7 she was pretty sure that you can always make all partitions of n with an n-cycle. She hasn’t given me any justification, but I think she sees what’s going on. Next session I think I will have her think about what partitions can be made with stars.

The Chicken’s Claw

I had my fifth evening of math with my kids.  I got a box of 100 washers from the hardware store and some yarn.  I had the kids draw some graphs and then make some graphs with the washers as nodes and the yarn as the edges.  I let them make some of thier own, then I had them make these:

The square:

o-o
| |
o-o

and the claw:

  o
  |
  o
 / \
o   o

and asked them if they were the same (“What do you mean, Dad? Of course they’re not the same.”)

Then I had them make the pentagon and the pentagram. I asked if they were the same (again “of course not”). So I took two copies of the square. “Are they the same?” “Of course.” “Well then, why aren’t the square and the claw the same?” With time they answered that one had a node that was hooked to three other nodes rather than just two. Next they spent some time trying to get the pentagon to look like the pentagram. I suggested they try to work with the pentagram itself. B picked it up and it immediately fell apart into the pentagon.

Next I showed how I could cut two edges of the pentagon to get two connected graphs, one with two nodes and the other with three, thus making the partition of 5: 3+2. I then asked how many partitions of 4 they could make with the claw. They discovered that the only one that they couldn’t make was 2+2. I asked this question.

Q: How many partitions of 4 can’t you make with the claw?

The answer is 1, so we call the claw a Q1 graph.

A couple nights later I had them look for more Q1 graphs. B tried one that he called the chicken claw:

    o
    |
    o
    |
    o
   / \
  o   o
 /     \
o       o

He quickly figured out that this is not a Q1 graph. In the mean time A worked on what she called the ice cream cone:

o-o-o
|  /
o o
|/
o

But she wasn’t able to finish her analysis of it inthe time we had.

Math with Bananas

Tonight was my fourth evening of math with my kids.  It was rather frustrating, but turned out good in the end.  I pulled out the number line again, which had markings for 0, 1 and 2, as well as 1/2, 1/3, 1/4, etc. through 1/17 and then an annotation saying: “infinitely many more like these.”  I said “the zero has lots of friends, but what about the one?”  Mostly they grumped around and doodled for a while.  Then they kind of stared at me blankly as if expecting me to answer my own question.  They weren’t talking to each other at all, so I left the room and told them to work it out on their own.  B called me back a while later saying that 1 had some more friends now.  I came back into the room and he showed me that he had written 1/2, 1/3, 1/4, etc. through 1/17 between the 1 and 2.  I prompted him to tell me what the difference between the 1/2 between the 1 and 2; and the one half between the 0 and 1 was.  He said that they were the same, except that they were in different places.  I asked him what he meant and he continued to insist that they were the exact same number, but that they show up in those two places.  Next he told me that the 1/2 between the 0 and 1 is supposed to mean half of zero, while the 1/2 between 1 and 2 is half of one.  Hmmm…something was going wrong here.  I asked what half of something means.  B said that it means you split a number up.  A basically wasn’t participating.  I was starting to get frustrated, so I took down a bunch of bananas.  I asked them to show me one banana.  Now A perked up and B shut off.  A held up one banana.  I told here to put it in its spot on the number line.  She did.  Then I asked them to show me two bananas.  A picked up two bananas, and I prompted her to put it in its spot.  Then I asked B if she was right that this was two bananas.  He said that he didn’t know (!).  Obviously he was frustrated.  He knows what two bananas is.  Finally he agreed that A was right with her two bananas.  Next I asked for zero bananas.  They both understood that with no problem.  “Now, how many bananas do we put by this 1/2?” I asked.  B claimed that we should put zero there.  He was still thinking of it as half of zero.  I’m beginning to understand that he was confused with the concept of half as a number (an element of the real numbers) and half as a scalar multiplier of the integers.  (“half of zero is zero.  Half of one is, well it’s half of one.  Half of two is one,..etc., but what is one half?  It’s a different kind of object…right?”  that’s what I imagine was going on in his brain, but I’m not sure.)  Finally I got out a knife: “Show me half a banana.”  He was starting to get it now.  He cut a banana in half.  There was lots more frustration before the night was out, but eventually we got 5/3, “one and a half,” 4/3, and 2/3 on the number line in their correct places (!) and ended up with a bunch of cut up bananas.  Smoothies for breakfast!

Ok, tonight was not tons of fun for any of us.  We’ll give the number line a break for a while.  It’s tough for me to work with the kids on something where I know the answer and they don’t.  I need to get better at that.  But next week I plan on moving them closer to doing some math research where I don’t know the answers.

Sequences of Rationals (rerun)

Here’s a rerun of an earlier post.  It ends with an open question that I hope someone can help me out with.

If I start giving you some numbers like:

or

That’s a sequence. You can take a sequence and make the sequence of averages. The average of is . The average of and is . The average of , and is . and so on. So the sequence of averages for

is

,

and the sequence of averages for

is

.

Now for some questions (the answers are known)

1) Can you come up with a sequence of rational numbers such that the sequence of averages hits every rational number?

2) Can you come up with a sequence of positive rationals such that the sequence of averages hits every positive rational number?

3) Can you come up with a sequence of positive rationals such that the sequence of averages hits every positive rational exactly once?

4) How about a sequence of unique positive rationals (no repeats) whose sequence of averages hits every positive rational exactly once?

Finally, one that I don’t know the answer to:

5) Can you come up with a sequence of positive rationals that itself hits every positive rational exactly once and whose sequence of averages also hits every positive rational exactly once?

Please let me know if you get number (5). Also let me know if you are stuck on any of them.

An Evening of Math III

I’ve been reading Out of the Labyrinth: Setting Mathematics Free, by Robert and Ellen Kaplan, who are the founders of “the Math Circle.”  As I understand it a math circle is where you get a bunch of people together, ask a couple of provocative questions to get them thinking, and then get out of the way and let them create mathematics.

I decided that I would try something akin to their math circle with my kids.  I settled on using the opening example from the book:  draw a number line with 0 and 1 labeled, ask if there are any other numbers in there, and step back to see what numbers the kids can find.  The idea is that they start marking fractions, get comfortable with those and eventually come up with an irrational number.

A was easily distracted tonight.  She kept wanting to put in numbers beyond 1.  B put in 1/2, then 1/4 in approximately hte right places.  Later he moved them so that he could fit more numbers in.  He ended up with 1/2, 1/3, 1/4, etc. down to 1/13 spaced approximately evenly.  A added 1/14, 1/15, 1/16.  I asked how many more there were.  ” I can’t say how many.  Lots more.  Infinity many.”  Is what B replied.  He ended up writing “infinitely many numbers like these” between 1/16 and 0.  We also ended up with 1/1 somewhere between 1 and 1/2.  For now I’m letting that persist until they figure out that its the same thing as 1.  A wanted to put in 0/2, but B told here that that was the same thing as 0.

A also said that one thousand two hundred thirty four was her favorite number and wrote it out: 1234, with a box around it.

Next week we’ll pull the number line out again and since 0 has so many friends next to it, I’ll ask whether 1 has any.

An Evening of Math II

Tonight I gave the kids the choice of doing more partitions, or something else. They chose something else. In the book Math Tricks, Puzzles & Games by Raymond Blum I found this problem:

TUNNELS

Try to connect each rectangle with the triangle that has the same number.  Lines cannot cross or go outside the diagram.

When I showed the problem to the kids, A was very upset and said that she didn’t know how to do it because she had never learned.  She threw a fit and started drawing a picture instead of working on it.  B immediatly started working on it.  He worked for about 20 minutes, drawing lines, erasing, drawing more lines.  He eventually got frustrated, saying that it was impossible.  In spite of A’s protests I brought her over next to B and had him explain what he had tried, and why it was impossible.  B connected rectangle 1 to triangle 1, then connected rectangle 2 to triangle 2, but at that point rectangle 3 was completely cut off from triangle 3.  Then A took a pencil and a copy of the puzzle and without pausing connected rectangle 1 to triangle 1 and rectangle 3 to triangle 3.  Just as B was saying that she wouldn’t be able to connect the last pair, she did!

Getting A to look at a problem is 95% of the battle.  I reminded her that it was B’s work on the problem that helped her to her solution.

Puzzles with Japanese Names

Here are some of my favorite puzzles that happen to have Japanese names:

Sudoku.  Sudoku is so popular that my readers have almost certainly heard of it.  Here are some unconventional versions:  Math Games: Sudoku Variations.

Tentaizu.  A good example and explanation is found at this blog: y of x (the puzzle originally comes from Southwest’s in-flight magazine).

Kenken.  The Wikipedia article gives the history, rules and some sample puzzles: Kenken on Wikipedia.

Kakuro.  I’ll refer you to Wikipedia for this one also: Kakuro on Wikipedia.

Takegaki.  Those geniuses who write the puzzles for Southwest Airlines have done it again:  Southwest Magazine Takegaki.

Thanks go to Evelyn for pointing me to the last one, and for reminding me of this post that had been sitting in my draft-box for months.