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.

Part V: Some Examples

Advertisements
This entry was posted in graphs. Bookmark the permalink.

2 Responses to Partitions of Graphs IV: Partitions of Graphs

  1. Pingback: Partitions of Graphs V: Some Examples « MATH with my KIDS

  2. Pingback: Partitions of Graphs III: Ramanujan meets Kevin Bacon « 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