Skip to main content
Logo image

Activities to Accompany Applied Combinatorics

Mitchel T. Keller, William T. Trotter

Print preview

Paper size
Additional printing options
Print headers
Print footers

Worksheet 6.1 Posets and Graphs; Antichain Partitioning

Activity 6.1.1.

(a)

Classify each of the terms below as a poset term or a graph theory term. You will have six terms of each type.
  • Antichain
    🔗
  • Chain
    🔗
  • Chromatic number
    🔗
  • Clique
    🔗
  • Clique number
    🔗
  • Height
    🔗
  • Independent set
    🔗
  • Partition into disjoint antichains
    🔗
  • Partition into disjoint chains
    🔗
  • Partition into disjoint cliques
    🔗
  • Proper coloring
    🔗
  • Width
    🔗
🔗
Solution.
The poset terms are:
  • Antichain
    🔗
  • Chain
    🔗
  • Height
    🔗
  • Partition into disjoint antichains
    🔗
  • Partition into disjoint chains
    🔗
  • Width
    🔗
🔗
The graph theory terms are:
  • Chromatic number
    🔗
  • Clique
    🔗
  • Clique number
    🔗
  • Independent set
    🔗
  • Partition into disjoint cliques
    🔗
  • Proper coloring
    🔗
🔗
🔗
🔗

(b)

Write the six poset terms from the previous part on separate rows in the Poset column of the table below. Place each of the six graph theory terms into both the Comparability Graph column and the Incomparability Graph column, choosing the row in which a term is placed so that the graph term for that type of graph corresponds to the poset term in that row. You will have one empty cell in each of the graph columns and one cell in each graph column will contain two graph theory terms!
🔗
Poset Comparability Graph Inomparability Graph
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
\(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\) \(\phantom{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}\)
Solution.
Poset Comparability Graph Inomparability Graph
Antichain Independent set Clique
Chain Clique Independent set
Height Clique number / Chromatic number
Partition into disjoint antichains Proper coloring Partition into disjoint cliques
Partition into disjoint chains Partition into disjoint cliques Proper coloring
Width Clique number / Chromatic number
🔗
🔗
🔗

Activity 6.1.2.

(a)

Use the algorithm to find the height \(h\text{,}\) a partition into \(h\) antichains, and a maximum chain for each of the posets below.
🔗
Solution.
For the poset on the left, the height is \(4\text{.}\) A partition into \(4\) antichains is given by
\begin{align*} A_1 \amp= \set{6,7,10}\\ A_2 \amp= \set{2,4,8}\\ A_3 \amp= \set{1,5}\\ A_4 \amp= \set{3,9} \end{align*}
and a maximum chain is \(\set{9,5,4,6}\text{.}\)
🔗
For the poset on the right, the height is \(9\text{.}\) A partition into \(9\) antichains is given by
\begin{align*} A_1 \amp= \set{7,18,19,25}\\ A_2 \amp= \set{3,10,16,17}\\ A_3 \amp= \set{2,12,20,24}\\ A_4 \amp= \set{14,21}\\ A_5 \amp= \set{1,8,9}\\ A_6 \amp= \set{13,11,22}\\ A_7 \amp= \set{4,15}\\ A_8 \amp= \set{5,23}\\ A_9 \amp= \set{6} \end{align*}
and a maximum chain is \(\set{6,5,15,22,9,14,24,16,25}\text{.}\)
🔗
🔗
🔗

(b)

What can you say about the width of these posets? In particular, is one of the antichains in your antichain partition maximum?
🔗
Solution.
We will not learn an algorithm for chain partitioning in this class, as it requires material from Chapters 13 and 14. However, finding the width, a maximum antichain, and a partition into disjoint chains for the poset on the left is reasonable as homework or a test question. Will give the solution for the poset on the right, but it’s much larger than would be reasonable for a test question.
🔗
The width of the poset on the left is \(3\text{.}\) A maximum antichain is \(\set{2,4,8}\text{.}\) A partition into disjoint chains is given by
\begin{align*} C_1 \amp=\set{7,2,1,3} \\ C_2 \amp=\set{10,8} \\ C_3 \amp=\set{6,4,5,9} \text{.} \end{align*}
🔗
The width of the poset on the right is \(7\text{,}\) which is much larger than any antichain found by the height algorithm! A maximum antichain is \(\set{10,11,1,15,2,8,12}\text{.}\) A partition into disjoint chains is given by
\begin{align*} C_1 \amp=\set{25,16,24,14,8} \\ C_2 \amp=\set{18,3,2,13} \\ C_3 \amp=\set{19,17,12,6} \\ C_4 \amp=\set{20,21,22,15,5} \\ C_5 \amp=\set{9,11} \\ C_6 \amp=\set{1,4} \\ C_7 \amp=\set{7,10,23} \text{.} \end{align*}
🔗
🔗
🔗
🔗
described in detail following the image
The diagram of a poset with 10 points.
🔗
described in detail following the image
The diagram of a poset with 25 points.
🔗
🔗
PrevTopNext