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:

n = im+j(m-1)\qquad(*)

Where 2\le i\le m-2 and 1\le j\le m-1.  Of course the first inequality implies: 4\le m.  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.

Advertisements
This entry was posted in graphs and tagged , , , , . Bookmark the permalink.

One Response to Partitions of Graphs XI: The Case of all Sufficiently Large n

  1. Pingback: Partitions of Graphs X: The Case of Composite Integers « MATH with my KIDS

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s