MSU MATHEMATICS

MTH 482
Old Homework

Spring 2008

Announcements
- Test 1: Fri Feb 1 in class. Come 5 min early for extra time. Topics:
  - Max-Flow/Min-Cut (FCM Sec 1)
  - Vertex connectivity, edge connectivity, Menger's Theorem (FCM Sec 2)
  - Hall's Matching Theorem (FCM Sec 3)
Homework: I will not collect homework, but the weekly quizzes will be based on them. For extra points, you may turn in the problems marked Extra Credit, preferably within a week of the HW date.These problems are an essential component of the course, and I strongly recommend you do all of them.
References are listed at the end of this page.
- Graph Theory Review Problems
- HW 1/14: Connectivity (FCM pp 73-75)
  We defined the vertex-connectivity κ(G) to be the minimum number of vertices whose removal disconnects the graph. Menger's Theorem says that this is the maximum number of independent paths between a pair of vertices of G (i.e. between the least connected pair of vertices).
  We can define an analogous notion of edge-connectivity κ'(G) to be the minimum number of edges whose removal disconnects G. (When we remove edges, we leave their vertices in the graph.) As before, this is the maximal number of edge-independent paths between a general pair of vertices, meaning that two paths can share vertices but not edges.
  1. Show that we always have: κ(G) ≤ κ'(G) ≤ δ(G) ,where δ(G) is the smallest vertex degree deg(v) of G.Find examples of G for which each of these inequalties is a strict < .
  2. Determine κ(G) and κ'(G) for all our favorite graphs: trees, the platonic solid graphs, the Petersen graph (HHM Fig 1.55, p 44), complete graphs K_n , and complete bipartite graphs K_n,m . (By definition, the complete graph has κ(K_n) := n-1 .) Hint: Use Menger's Theorem and the inequalities above.
  3. Extra Credit: For any k ≤ m , find examples with κ(G) = k and κ'(G) = m .
  4. Extra Credit: Connectivity of planar graphs
    1. Show that any maximal planar graph with n ≥ 4 vertices has 3 ≤ κ(G) ≤ κ'(G) ≤ 5. Hint: Any planar graph has a vertex of degree ≤ 5.
    2. Do there exist maximal planar graphs G having each of the possibilities (κ(G), κ'(G)) = (3,3), (3,4), (3,5), (4,4), (4,5), (5,5)?
- Quiz 1/14: Definition of k-connectivity (FCM pp 73-75).
- HW 1/23: Max-Flow/Min-Cut Theorem (FCM Sec III.1 pp 68-73)
  1. Consider the following network with vertices V = {s,a,b,c,d,t}, source s, sink t, and directed edges as follows:E = { (s,a) (s,b) (a,c) (a,d) (b,c) (b,d) (c,t) (d,t) }.Let the capacity function be cap(e) = 2 for each edge except cap(a,c) = 1. Consider the flow f defined by:f(s,a) = f(a,c) = f(c,t) = 1 and f(s,b) = f(b,d) = f(d,t) = 2 ,
    1. List all 2⁴ = 16 edge-cuts (S,T), and for each compute its capacity cap(S,T) as well as the flow volume flow_f(S, T), which should be the constant flow(f). Is flow(f) equal to the minimal capacity of a cut? If not, then f is not a maximal flow for this network?
    2. Apply the Augmenting Algorithm starting with f₀ = f . Draw the graph G' . Find an augmenting path P in G' from s to t, and compute the augmented flow f₁ = f '. Notice how the algorithm corrected a "mistake" in f to give a better f' .
    3. Repeat the algorithm if necessary, and in the end produce a flow f_n which is demonstrated to be maximal by an edge cut (S,T) with flow(f_n) = cap(S,T) .
  2. For a general network (G,s,t,cap) and flow(f), suppose the the Augmenting Path Algorithm breaks down as in case (ii). Prove that the resulting cut (S,T) has the required property flow(f) = cap(S,T).
    Hint: If (x,y) ∈ G is an edge from S to T, show that f(x,y) = c(x,y); while if (x,y) ∈ G is an edge from T to S, show that f(x,y) = 0 .
  3. For a directed graph G = (V,E) with source s and sink t, define a dam to be a set of edges F ⊂ E such that there is no directed path from s to t in G − F (removing the edges in F, but not vertices). For a cut (S,T) according to our definition above, define E(S,T) = {(x,y) ∈ G s.t. x ∈ S and y ∈ T}, the set of edges from S to T.
    Show that if F ⊂ E is a dam, then F contains E(S,T) for some cut (S,T). Indeed, a dam with a minimal number of edges is equal to E(S,T).
- Quiz 1/23: Max-Flow/Min-Cut Theorem and Augmenting Algorithm.
- HW 1/28: Connectivity and Menger's Theorem(FCM Sec III.2 pp 73-76)
  1. Generalizations of MF/MC Theorem.
    1. Let us generalize our notion of a network to allow multiple sources s₁, s₂,... and sinks t₁, t₂.... State an appropriate MF/MC Theorem for this situation. (Modify the definition of a flow and an edge-cut.) Prove your statement by reducing it to the original MF/MC.
    2. A different modification to the original MF/MC: instead of specifying edge-capacity, specify vertex-capacity: at each vertex v ≠ s,t, we impose a bound cap(v) on the outflow volume (= inflow volume) of a flow f at v. Again prove the appropriate MF/MC Theorem by reducing it to the original theorem.
    3. Formulate and prove the most general version of MF/MC you can.
    4. What generalizations of Menger's Theorem correspond to the above generalizations of MF/MC?
  2. Extra Credit. I made the following conjecture, but it turns out to be false. Give a counterexample.
    Let G = (V,E) be a simple graph and fix a set of k vertices S ⊂ V.Suppose that for each x ∈ V , there exist k paths P₁,..., P_k from S to x, all of them vertex-disjoint except for their endpoint x. Then G is k-edge-connected, κ'(G) ≥ k .The idea is to construct edge-disjoint paths between any x and y based on a set of paths from S to x and S to y. Compare to FCM Ex 13 p 93.
  3. Proof of the Menger Theorems from MF/MC. In each case, we made a simple graph correspond to a network, so that a path family with k paths corresponds to a flow with volume k.
    1. Edge Menger Theorem. We let a simple graph G with marked vertices x,y correspond to the network (G, x, y, c), where each edge xy ∈ G corresponds to a pair of edges (x,y) and (y,x) ∈ G ; x is the source, y the sink; and the capacity function c(x,y) = 1 for all edges. Given a family of edge-disjoint paths ℘ = {P₁,...,P_k}, write the corresponding flow f on G with flow(f) = k. ~~Show that this f has no circulation.~~ This flow might have circulation, i.e. a directed cycle C in G with f(x,y) > 0 for every edge of C. (Thanks to Ian Desilva for the correction.)
    2. Let f be an arbitary flow on the above network (G, x, y, c). Since the net flow at any vertex v is zero, there must be as many edges with inflow 1 as edges with outflow 1. Make an arbitrary matching of these in-edges with the out-edges at each vertex. Show that this makes f correspond to an collection of edge-disjoint paths and cycles in G, and the number of paths is the volume of the flow. Show further that a maximal-volume flow corresponds to a maximal path family, and vice-versa.
    3. Show that a minimal edge-cut of the graph G (a set of edges which disconnects G) corresponds to the edges E(S,T) between the parts of a minimum-capacity cut (S,T) of G.
    4. Vertex Menger Theorem. We let a simple graph G with marked vertices x,y, correspond to the new network G_± . For each vertex v ∈ G with v ≠ x,y we define two vertices v_- , v₊ ∈ G_± , and an edge (v_-,v₊) ∈ G_± with capacity c = 1. We do not split x and y, making these be the source and sink vertices of G_± . For each edge uv ∈ G, we define two edges(u₊,v_-) , (v₊,u_-) ∈ G_± with capacity c = ∞. Show the same analogies as above between vertex-independent path families in G and flows in G_± ; and between minimal vertex-cuts of G and minimal-capacity cuts (S,T) in G_± .
- Quiz 1/28: Menger Theorems & relation to MF/MC.
- HW 1/30: Hall Matching Theorem (FCM Sec III.3, pp 76-78)
  1. Applications of Matching.
    1. Suppose there are senators A,B,C,D,E,F, from whom are chosen committee 1 (members A,B,C,D), committee 2 (members A,E,F), committee 3 (members D,E,F) and committee 4 (only A). Draw a bipartite graph which reflects this situation (with vertices corresponding to committees and senators). We wish to choose an executive council with one member representing each committee, but no member representing more than one committee. Show that a matching of committees to their member senators corresponds to a choice of executive council. (HHM p 60)
    2. Consider a family of sets A₁ ,..., A_m . We wish to choose a set of distinct representatitives a₁ ∈ A₁, ... , a_m ∈ A_m.
      Claim: If for every I ⊂ {1,...,m}, we have: |∪_i∈I A_i| ≥ |I| . Then the family {A₁ ,..., Am} does possess a set of distinct representatives. Prove this using the Hall Theorem. (HHM p. 65; FCM p. 78)
  2. Consider the bipartite graph G with A = {1,2,3}, B = {1', 2', 3'} and edges E = {11', 12', 22', 23', 33'} and the partial matching M = {12', 23'} from A' = {1,2} to B.
    As in class, make G correspond to a network G with:
    - vertices A ∪ B ∪ {s,t} with source s, sink t
    - edges {(a,b) for ab ∈ E} ∪ {(s,a) for a ∈ A} ∪ {(b,t) for b ∈ B} ;
    - all edge capacities c = 1.
    The partial matching M in G corresponds to the flow f in G with f(s,a) = f(a,b) = f(b,t) = 1 for (a,b) ∈ M and f(x,y) = 0 otherwise.
    Use the Augmenting Path Algorithm to increase f to a maximal flow f ', and find the corresponding minimal cut (S,T) of G. Also, write the corresponding matching M' from A to B in G.
- HW 2/11: Connectivity & k-blocks
  1. We defined a k-block of a graph G as a maximal k-connected subgraph B ⊂ G. We showed that any k-connected subgraph is contained in a unique k-block, but some vertices and edges might not be in any k-connected subgraph.
    Determine the k-blocks of the following graphs G, for all k. (Note: whenever G is connected, it is a single 1-block.)
    1. The Platonic graphs.
      Answer: For G a d-regular Platonic graph , κ(G) = d. Thus for k ≤ d, the whole G is a k-block, while for k > d , there are no k-blocks.
    2. The hypercube graph defined in Test 1.
      Answer: This G is 4-regular and 4-connected, and the same analysis holds as above.
    3. The graph whose vertices are V = {a,b,c,d,a',b',c',d'}, with K₄ subgraphs on {a,b,c,d} and on {a',b',c',d'}, and one extra edge aa'.
      Answer: 2- and 3-blocks {a,b,c,d} and {a',b',c',d'}, and no k-blocks for k > 3.
    4. Same, but with extra edges aa', bb'.
      Answer: 2-block G, 3-blocks {a,b,c,d} and {a',b',c',d'}, and no k-blocks for k > 3.
    5. Same, but with extra edges aa', bb', cc'.
      Answer: 1- 2- and 3-block G, and no k-blocks for k > 3.
    6. The wheel graph W_n+1 consisting of a n-cycle C and an extra vertex adjacent to every vertex of C.
      Answer: This graph is 3-regular and 3-connected, so the analysis is same as (a) & (b).
  2. For each of the graphs above which are 3-connected, find an edge e such that the edge-contracted graph G/e is still 3-connected. (We gave an algorithm that always finds such an edge.) If possible, find another edge e' such that G/e' is not 3-connected.Hint: If {x,y,z} is a minimal separating set of G and xy is an edge, then G/xy is separated by {v_xy,z}, so it is not 3-connected.
- Quiz 2/11: Connectivity & k-blocks
- HW 2/18: Kuratowski Theorem (KUR). Corrections in red.
  1. Fill in the details for the following parts of the Kuratowski Theorem algorithm in the Notes 2/15 below.
    1. As in part (ii) of the algorithm, let G = G₁ &cup G₂ such that G₁ &cap G₂ = {x,y} is a minimal separting set. Suppose TK₅ or TK_3,3 ⊂ G₁ + xy . Then construct TK₅ or TK_3,3 ⊂ G.
      Answer: If G₁ has a TK₅ containing the edge xy, let x',y' ∈ G₂ be neighbors of x and y respectively, lying in a single component of G₂ - {x,y}. (Such x', y' exist because {x,y} is a minimal separating set of G.) Let P be a path from x' to y' in G₂ - {x,y}. Then replacing the edge xy in TK₅ ⊂ G₁ by the path xx'Py'y gives a TK₅ in G. Same applies for TK_3,3 .
    2. As in part (iii) of the algorithm, suppose G' = G/xy has a TK₅ or TK_3,3 . Then construct TK₅ or TK_3,3 ⊂ G. Hint: Expanding TK₅ ⊂ G' might produce TK_3,3 ⊂ G.
      Answer: If we have a TK₅ subgraph H' ⊂ G', and we expand any vertex v ∈ H' into two new vertices x,y to get a new graph H, at least one will have degree ≤ 2, so that H is still a TK_3,3 . The same holds for TK₅ ≅ H ⊂ G , unless we expand a degree 4 vertex v into vertices x, y ∈ H both of degree 3. Then if we divide the degree 3 vertices of H into y, y', y'' which are connected to x by a path, and the others x, x', x'', this shows H contains a TK_3,3 .
    3. In part (iv) of the algorithm, convince yourself that if none of the listed obstructions occur, then it is possible to insert the necessary vertex y and its neighbor, obtaining G from G''.
    4. Show how to modify a plane drawing of a graph so that any given vertex or edge is on boundary of the infinite region.
      Extra Credit: If the original drawing has straight-line edges, find a way to do the above process that keeps the edges straight.
  2. Apply the Kuratowski Theorem algorithm below to the following graphs, producing either a plane drawing (with straight-line edges) or TK₅ or TK_3,3 ⊂ G.
    1. G = K₅ - {45}. Apply the algorithm via the contracted graph G' = G/xy with x = 3, y = 4; and alternatively with x = 4, y = 3. Answer: The graph is shown to be planar, built from a plane drawing of K₄ = G/xy.
    2. The graph with vertices {1,...,5} and edges {12, 34, 15, 25, 35, 45, 13, 24}. Answer: The graph is planar.
    3. G = K₆ - { i(i+1) for i = 1,...,6 }. That is, remove the outer 6-cycle from the complete graph K₆ . Hint: G/14 is isomorphic to the previous graph. Answer: Draw a 4-cycle with vertices 2,5,3,6; then inside the cycle draw 1 adjacent to 3,5, then draw 4 adjacent to 1,2,6.
    4. G = Peterson graph on vertices {1,...,10}, with a 5-cycle 1,2,3,4,5; another 5-cycle 6,8,10,7,9; and five edges i(i+5) for i = 1,...,5. This can be drawn as a small 5-point star inside a large pentagon, with each vertex of the star connected to the closest vertex of the pentagon. Answer: Despite its shape, this graph cannot contain a TK₅ since each vertex has degree 3.Instead, G - {16,68,69} is clearly a TK_3,3 .
    5. Addition: G is one of the graphs in HW 2/11 #1c,d,e. These can be taken as examples of the Algorithm cases (i), (ii), (iii).
    6. Addition: G = the hypercube graph from HW 2/11 #1b.
- Quiz 2/18: Kuratowski Theorem (KUR)
- HW 3/17: Method of Generating Functions. (See Notes below.)
  1. Taylor's formula in calculus says that almost any function f(x) can be expressed as a power series (an infinite polynomial):
    f(x) = a₀ + a₁x + a₂x² + ....
    The coefficients are given by Taylor's Formula: a_k = f^(k)(0) / k! , where f^(k)(0) means the k^th derivative of f(x) at x = 0.
    1. Apply this to write the Taylor series of f(x) = 1/(1−x) = (1−x)⁻¹. Write the answer in "dot-dot-dot" notation (writing out enough terms to make the pattern clear, then "..."), and also in Σ notation.
      Answer: 1/(1−x) = 1 + x + x² + x³ + ... = ∑_k≥0 x^kThis is the geometric series, the most important of all power series.
    2. Use the geometric series to evaluate the infinite sum 1 + 1/3 + 1/3² + ... and the repeating decimal 0.11111....
    3. Apply Taylor's Formula to write the series of f(x) = log(1+x) , using the derivative log'(z) = 1/z . That is, compute the coefficients a₀, a₁, a₂,...., until you see the pattern.
      Answer: log(1+x) = x − x²/2 + x³/3 − x⁴/4 + ... = ∑_k≥1 (−1)^k+1x^k / k .
    4. Approximate log(3/2) by substituting x = 1/2 into your Taylor series, and adding the terms up to x⁴. How good is the approximation?
    5. For which values of x are the above Taylor series formulas valid? For example, could we compute log(3) by substituting x = 2?
      Answer: The formulas hold only when the series converge to a finite value, namely for |x| < 1 . The series for log(1+x) also converges for x = 1, giving the remarkable formula: log(2) = 1 − 1/2 + 1/3 + 1/4 − ....
  2. Generating functions for counting multi-sets
    1. Suppose you have 2 apples and 2 bananas and you put any or all of them in your lunch bag, for example 0 apples and 2 bananas, which we can think of as the multi-set {B,B} . (Recall that a multi-set is an unordered collection of objects with repeats allowed.) What are all the possibilities for the contents of the bag? Figure this by logically expanding the expression:
      (0A or 1A or 2A) and (0B or 1B or 2B)
      using the logical distributivity rule from above. Expand until you have an expression like: (0A and 0B) or (0A and 1B) or .... or (2A and 2B)
    2. Re-do the entire computation in (a), replacing 0A, 0B by x⁰; 1A, 1B by x¹; 2A, 2B by x²; "or" by + ; "and" by ×. Start with f(x) = (x⁰ + x¹ + x²) (x⁰ + x¹ + x²) and expand using algebraic distributivity. Collect like terms to get a polynomial a₀ + a₁ x +...+ a₄ x⁴ . That is, f(x) is the generating function of the coefficient sequence {a_k}.
      Question: What is the combinatorial meaning of the coefficients a₀,...,a₄? That is, what do these values count about ways of filling the bag?
      Answer: On expanding, we end up with 9 terms:x⁰x⁰ + x⁰x¹ + x⁰x² + x¹x⁰ + x¹x¹ + x¹x² + x²x⁰ + x²x¹ + x²x²corresponding to the 9 allowed multisets {}, {B}, {B,B}, {A}, {A,B}, {A,B,B},{A,A}, {A,A,B}, {A,A,B,B} .Each term xⁱx^j corresponds to a multiset with i apples and j bananas, so its exponent k = i+j is the total pieces of fruit. The coefficient a_k is the number of such terms, i.e., the number of ways to bag k pieces of fruit.
    3. Now expand f(x) = (1 + x + x²)² again, this time using the binomial theorem (a+b)² = a² + 2ab + b² twice: first with a = 1, b = x + x², and then again with a = x, b = x². Thus, re-compute the coefficients a₀,...,a₄.
      Answer: (1 + x + x²)² = 1 + 2(x+x²) + (x+x²)²
      = 1 + (2x + 2x²) + (x² + 2 x x² + (x²)²)
      = 1 + 2x + 3x² + 2x³ + x⁴ .Thus there is 1 way to give no pieces, 2 ways to give 1 piece, 3 ways to give 2 pieces, etc.
  3. Double deck hands. Recall that in class (and in Notes 3/12 below) we compute the number of k-card hands that can be dealt from two identical decks of 52 cards each.
    1. We obtained the formula: a₅ = (52 | 5) (5 | 0) + (52 | 4) (4 | 1) + (52 | 3) (3 | 2) .Prove this formula directly by the sum and product principles. That is, split the problem into 3 cases, each giving one of the terms in the answer.
      Answer: Case 1: 5 distinct cards, (52 | 5). Case 2: one double, i.e. 4 distinct cards and one of the four doubled, (52 | 4)(4 | 1). Case 3: two pairs of doubles, i.e. 3 distinct cards and 2 of the 3 doubled: (52 | 3)(3 | 2).
    2. Extra Credit: Similarly, give a direct proof of the general formula: a_k = ∑_i=0^⌊k/2⌋ (52 | k-i) (k-i | i) .
  4. Use generating functions to compute how many distinguishable 5-card hands can be dealt from a triple deck (so that each of the 52 distinct cards can appear 1, 2, or 3 times).
    1. Step 0: Generalize the problem by letting a_k be the number of k-card hands dealt from a triple deck.
      Step 1: Reduce the choice of a hand to a sequence of simple choices to give a neat product formula for f(x). Hint: You can simplify your answer further by writing 1 + x + x² + x³ = (1 + x) (1 + x²) Answer: f(x) = (1 + x + x² + x³)⁵² = (1 + x)⁵² (1 + x²)⁵².Step 2: Use algebra (especially the Binomial Theorem) to expand the product expression for f(x), obtaining an explicit formula for a_k.
      Hint: Start with (1 + x)⁵² = ∑_i (52 | i) xⁱ and (1 + x²)⁵² = ∑_j (52 | j) x^2j
      Answer: f(x) = (1 + x)⁵² (1 + x²)⁵² = ( ∑_i (52 | i) xⁱ ) × ( ∑_j (52 | j) x^2j )
      = ∑_i ∑_j (52 | i) (52 | j) x^i+2j = ∑_k [ ∑_i+2j=k (52 | i) (52 | j) ] x^k
      so: a_k = ∑_(i+2j=k) (52 | i) (52 | j)where, for a given k, the summation runs over all i,j ≥ 0 such that i+2j = k . For k = 5, the allowed pairs are (i,j) = (1,2) , (3,1), (5,0), so the number of 5-card hands from a triple deck is:
      a₅ = (52|1) (52|2) + (52|3) (52|1) + (52|5) (52|0) = 3,817,112 .
      To make this computation more understandable, use ellipsis (+ ...) notation instead of summations:
      f(x) = [ 1 + (52 | 1)x + (52 | 2)x² + (52 | 3)x³ + (52 | 4)x⁴ + (52 | 5)x⁵ + ... ]
      × [ 1 + (52 | 1)x² + (52 | 2)x⁴ + ... ] Now multiply out and collect all the x⁵ terms to get a₅ .
    2. Extra Credit Explain the formula for a₅ using only elementary counting principles.
    3. Extra Credit Generalize the above arguments to the case of n decks for various n, say n = 4,5,6. For example, what can you make of:1 + x + ... + x⁵ = (1 + x)(1 + x + x²)(1 - x + x²) .
  5. Jellybeans.
    1. How many ways are there to choose 20 jellybeans of 3 kinds (red, green, yellow)? Hint: Think of a bag of 20 jellybeans is a multiset of letters R,G,Y. Repeat our argument from class for counting multisets, where we computed (n multi-choose k) = ((n | k)) = n(n+1)(n+2)...(n+k−1) / k! .
    2. You Can't Have Just One. How many ways are there to choose 20 jellybeans of 3 kinds, with the rule that you cannot choose just one of any kind? That is, if you choose any reds, you must take at least 2 of them, and the same way with greens and yellows.
      Answer:
      Step 0: Generalize the problem to give a sequence. Let a_k be the number of ways to choose k jellybeans with the given rule.
      Step 1. Form the generating function f(x) = ∑_k≥0 a_k x^k . To find a simple formula for f(x), consider that a handful of beans can be chosen by the logical expression: (0R or 2R or 3R or ...) and (0G or 2G or 3G or ...) and (0Y or 2Y or 3Y or ...)which translates to the algebraic expression:f(x) = (1 + x² + x³ + ...)³ = ( 1 + x²/(1-x) )³.Step 2. To expand the above expression for f(x), first apply the binomial theorem (a+b)³ = a³ + 3a²b + 3ab² + b³ , then expand each term using 1/(1-x)ⁿ = ∑_k≥0 ((n | k)) x^k . f(x) = 1 + 3x²/(1-x) + 3x⁴/(1-x)² + x⁶/(1-x)³
      = 1 + 3x² + 3x³ + 6x⁴ + 9x⁵ + ∑_k≥6 [3 + 3((2 | k-4)) + ((3 | k-6))] x^kThe coefficient at k = 20 is:3 + 3((2 | 16)) + ((3 | 14)) = 3 + 3×17 + 16×17/2 = 174 .Extra Credit: Explain the above formula for a_k by elementary means.
Quiz 3/17: Using the Method of Generating Functions.
HW 3/24: Counting rooted and unrooted trees.
1. Recurrences for r_n. (Thanks to Ian Desilva for corrections.)
  1. Given that r₁ = r₂ = 1, r₃ = 2, r₄ = 4, r₅ = 9, compute r₆ and r₇ using the First and Second Recurrence Formulas (in Notes 3/14 and 3/19 below). Is the second formula simpler?
  2. In Notes 3/14 below, we used the First Recurrence Formula to compute:
    r₅ = ((r₁ | 4)) + ((r₁ | 2)) ((r₂ | 1)) + ((r₂ | 2)) + ((r₁ | 1)) ((r₃ | 1)) + ((r₄ | 1))
    = 1 + 1 + 1 + 2 + 4 = 9 .
    Verify this using the combinatorial recurrence: construct the 9 rooted trees by adding a new root to multi-sets of smaller rooted trees. For example, the second term of the formula corresponds to the unique multiset H with two 1-vertex trees and one 2-vertex tree:H = { ® , ® , ®−−O } ,which produces a 5-vertex tree T by attaching a new root to each of the roots in H:
    T = ®−− ® −−® −−O
    |
    ®
    Do this for all the other terms.
    In fact, the First Recurrence Formula is a straight-forward consequence of the combinatorial recurrence; generating functions are not really needed.
  3. Extra Credit: Can you prove the Second Recurrence Formula by a combinatorial correspondence, or in any way without generating functions? I don't know any way to do this.
2. Take log of both sides of r(x)/x = h(x) to show the following functional equation for r(x):
  log( r(x)/x ) = ∑_i≥1 r(xⁱ) / i .
  Hint: Begin the right side of the dlog method, but don't collect terms, and don't go on to do d/dx. Instead, interchange the order of summation, rewriting ∑_j ∑_i as ∑_i ∑_j .
  The above formula is equivalent to:
  r(x) = x exp( ∑_i≥1 r(xⁱ) / i ) .
  If we could solve this equation for r(x), we could get an explicit, non-recursive formula for r_n . This is clearly impractical, however, which supports the notion that there is no such explicit formula.
3. Define the exponential function by its power series exp(x) := ∑_n≥0 xⁿ / n! , and show by means of power series that exp(a + b) = exp(a) exp(b) . That is, substitute a, b, and (a+b) into the power series for exp(x), expand both sides into terms of the form c_i,j aⁱ b^j, and verify the formula by comparing coefficients on both sides. Hint: The formula is equivalent to the Binomial Theorem.
4. Finding recurrences: a toy example. Let c_n be the number of ways to make n cents using pennies (1¢) and nickels (5¢). For example, 6¢ can be made as 1+1+1+1+1+1 or 1+5, so c₆ = 2.
  1. Show that the generating function of the sequence is:
    f(x) = ∑_k≥0 c_k x^k = (1 − x)⁻¹(1 − x⁵)⁻¹ .
    Hint: Break the choice of a handful of change into two simple choices, and translate into algebra so that the exponent of x is the value of the handful.
  2. Use the dlog method to find a recurrence for c_n. That is, take x d/dx log of both sides, as we did for the First Recurrence for rooted trees, and simplify to give a recurrence
    c_n+1 = an expression in c₀,...,c_n .
    Hint: As for trees, write the left side as x f '(x) / f(x) and simplify the right side starting with log(ab) = log(a) + log(b). Then clear denominators and equate coefficients.
  3. Find a simpler recurrence from expanding the formula:
    f(x) (1 − x)(1 − x⁵) = 1 = 1 + 0x + 0x² + ....
    This shows the dlog method does not necessarily give the best recurrence.
  4. Find an explicit, non-recursive formula for c_n by using
    (1 − x)(1 + x + x² +x³ + x⁴) = 1 − x⁵
    to write:
    f(x) = ∑_k≥0 c_k x^k = (1 + x + x² +x³ + x⁴) (1−x⁵)⁻² .
    The result shows that this is really a trivial problem, and fancy methods are wasted on it.
    Hint: Use (1 − z)⁻² = ∑_k≥0 ((2 | k)) z^k , where ((2 | k)) = k + 1.
  5. Verify each of the above formulas by using it to compute c_n for n = 5, 6, 7, 8, 9, 10.
  6. Extra Credit: Do all the same for handfuls of pennies, nickels and dimes, which is a less trivial problem.
    Answers: (b)    c_n = ¹/_n ∑_1≤i≤n c_n−i + ⁵/_n ∑_{1≤j≤⌊n/5⌋} c_n−5j for n ≥ 1, where ⌊⌋ means round down.
    (c)    c_n = c_n−1 + c_n−5 − c_n−6 for n ≥ 1, where we take c_k = 0 for k < 0.
    (d)    c_n = ⌊n/5⌋ + 1 for n ≥ 0.
HW 3/31: Rooted vs unrooted trees.
1. In class we analyzed the relationship between unrooted and rooted trees. In this problem, go through this analysis for the case of n = 6 vertices.
  1. For each of the t_n = 6 unrooted trees T, determine:
    - p_T, the number of symmetry classes of vertices;
    - q_T, the number of classes of non-flipped (non-symmetry) edges;
    - the quotient tree T.
    Verify Otter's Lemma that T is indeed a tree and q_T = p_T − 1 .
  2. For each T, list the distinct rooted trees T ' that are formed by designating one vertex of T as the root.
    Example: the path T = P₆ has T = P₃, the path with p_T = 3 vertices and q_T = 2 edges. The associated T ' are formed by marking the first, second, or third vertices as the root (corresponding to the vertices of T).
  3. Compute r₆ = ∑_T p_T , and verify this number from previous HW.
  4. For each T, list the corresponding distinct edge-rooted trees T". That is, we designate one of the q_T inequivalent non-flipped edges of T as a root edge. For each such T", draw the set of unequal vertex-rooted trees {T₁', T₂'} obtained by removing the root edge (but keeping its endpoints).
    Example: The path T = P₆ has q_T = 2 possible distinct edge-roots (since the middle edge is flipped by a symmetry and is not allowed to be a root). Removing the first edge gives {P₁ , P₅}; removing the second edge gives {P₂ , P₄}. Removing the flipped edge would give the multi-set {P₃ , P₃}, but we exclude this case.
  5. Compute e_n = ∑_T q_T the number of edge-rooted trees, and verify the formula:e_n = ½[ ∑_1≤i≤n r_i r_n−i − r_n/2 ] .
  6. Finally, verify Otter's Formula:
    t_n = r_n − e_n = r_n − ½[ ∑_1≤i≤n r_i r_n−i − r_n/2 ] .
    Display the trees corresponding to each term in this formula.
2. Use the formula for t_n above to derive the corresponding relation for generating functions, also known as Otter's Formula:t(x) = r(x) − ½ [ r(x)² − r(x²) ] .Hint: Expand both sides of the generating function equation and collect xⁿ terms. This will give the equation involving the coefficients.
3. Extra Credit: Can every tree be obtained as T for some T (or maybe some non-tree graph)? For example, can T ever be the star-tree with vertices {1,2,3,4} and edges {12, 13, 14}?
4. Extra Credit: Comparing asymptotics.
  1. Rooted vs unrooted trees. We stated in class that asymptotically:
    r_n ∼ b aⁿ n^−3/2, t_n ∼ c aⁿ n^−5/2,
    where we use the constants:
    a ≅ 2.9558, b ≅ 0.4399, c ≅ 0.5349 .
    Any of the n vertices of an unrooted T may be chosen as the root, but only p_T of these give distinct rooted trees. Thus, if p_n is the average of p_T over all n-vertex unrooted T, we have: r_n = ∑_T p_T = p_n t_n . From the above formulas, determine p_n asymptotically. If p_n ∼ α n for some constant α, this is the expected proportion of vertices of T (of any size) which are distinct up to symmetry.
  2. Labelled vs unlabelled trees. Cayley's Formula states that there are nⁿ⁻² labelled trees.
    For a labelled tree L, any of the n! permutations of the vertices give an equivalent unlabelled tree T, but really there are only n! / g_T distinct L corresponding to T, where g_T = |Γ_T| = |Sym(T)|. If g_n is the average value of g_T, the number of labelled trees should be approximately:
    nⁿ⁻² = ∑_T n! / g_T ≅ (n! / g_n) t_n .
    Using Stirling's Formula (corrected from class): n! ∼ (2πn)^1/2 (n/e)ⁿ, approximate g_n , the expected number of symmetries of an n-vertex tree. Does a typical large tree have many symmetries, or not?
Quiz 3/31: Rooted vs unrooted trees.
HW 4/7: Graph Coloring. References: HHM Ch 1.4 & 2.3; Notes 4/2 & 4/4 below. Thanks to Ian Desilva for corrections.
1. Compute the chromatic polynomial P_G(k) for each of the following graphs G by (i) direct combinatorics of colorings; (ii) the Subgraph Formula; or (ii) the Deletion-Contraction formula.
  1. G = T a tree. Derive the answer using (i), then again with (ii), and again with (iii). Hint: A forest with n vertices and m edges has n − m components.
  2. G = K_n the complete graph. Use (i).
  3. G = K_n−e for any edge e. Use (iii).
  4. G = K_n₁n₂ the complete bipartite graph with n₁ = 1,2. Use (i).
    Extra Credit: Do this for general n₁, n₂.
  5. G = C_n the cycle. Do twice: (ii) & (iii).
  6. G = W_n+1 the wheel graph, a cycle C_n with an extra vertex in the center connected to all the other vertices. Use the previous answer, and (i).
  Answers: (a) k(k−1)ⁿ⁻¹ . (b) k(k−1)...(k−n+1) . (c) (k−n+2)⋅k(k−1)(k−2)...(k−n+2) .
  (d) For n₁ = 1 this is a tree. For n₁ = 2 : k(k−1)^n₂ + k(k−1)(k−2)^n₂ .
  (e) (k−1)ⁿ + (−1)ⁿ(k−1) . (f) k [(k−2)ⁿ + (−1)ⁿ(k−2)] .
2. Let P_G(k) = ∑ a_i kⁱ.
  1. For each of the polynomials computed in the previous problem, verify that a_n = 1 , a_n−1 = −m , a₀ = 0 .
  2. Show that for any graph, a_n−2 is equal to (m choose 2) minus the number of triangles (3-cycles) in G. Verify this for each of the examples.
  3. We stated Stanley's Theorem that (−1)ⁿ P_G(−1) equals the number of acyclic orientations of G (i.e., ways of giving a direction to each edge, without creating any oriented cycles). Verify this for each of the examples.
3. Factoring chromatic polynomials
  1. Recall that a bridge of G is a disconnecting edge e, so that G − e = G₁ ∪ G₂ (disconnected pieces). Show that:P_G(k) = ^(k−1)/_k P_G₁(k) P_G₂(k) .
  2. Let G be a connected graph, and list its 2-blocks (maximal 2-connected pieces) and bridges as: B₁, B₂, ... , B_r . (Recall that these form part of the 2-block tree of G.) Show that:P_G(k) = k^−r+1 P_B₁(k) ⋅⋅⋅ P_{B_r}(k) .
Quiz 4/7: Compute the chromatic polynomial of a graph.
HW 4/14: Stanley's Theorem. See notes below.
1. Stanley's Theorem 1.1 gives a correspondence between proper k-colorings c of a graph and strictly compatible pairs (O,c), where O is an acyclic orientation and c is a k-coloring. Strictly compatible means that c(u) > c(v) for every oriented edge u→v ∈ O. For each graph G below, list or describe the proper k-colorings, and give the unique orientation O corresponding to each. Hint: You know the number of proper colorings.
  1. G = K₃ , k = 3.
  2. G = C₄ , k = 3 .
  3. G = C₅ , k = 2 . Show directly that there exist neither proper colorings nor compatible pairs.
2. Stanley's Theorem 1.2.
  1. Verify that (i) P_K₁(k) = k and (ii) P_G∪H(k) = P_G(k) P_H(k) , where G ∪ H means the disconnected union of graphs G and H. We know that P_G(k) can be computed for any graph G using only rules (i), (ii) along with (iii) the Deletion-Contraction formula .
    Problem: Perform this computation all the way through for G = C₄ .
    Hint: Do Deletion-Contraction until there are no edges left, then use (i), (ii).
  2. Let P'_G(k) := (−1)ⁿ P_G(−k). We showed (Notes 4/9) that P'_G(k) also satisfies rules (i), (ii), (iii), modified slightly because of the minus signs, and that these rules are enough to compute P'_G(k).
    
    Problem: Repeat your computation from the previous part to compute P'_G(k) for G = C₄ .
  3. Stanley defines P_G(k) to be the number of weakly compatible pairs (O,c), where O is an acyclic orientation of G and c is a k-coloring with c(u) ≥ c(v) for every oriented edge u→v ∈ O. Verify from the definitions that P_G(k) satisfies the same version of (i) and (ii) as P'_G(k).
    Theorem 1.2 states that P_G(k) = P'_G(k) for all G and k. The bulk of Stanley's proof is to verify the appropriate rule (iii) for P_G(k). This shows that P_G(k) and P'_G(k) can be computed according to the same rules, so they have the same value.
  4. List all the weakly compatible pairs (O,c) for G = C₄ , k = 1, and verify that P_G(k) = 14 = P'_G(k).
3. P_G(k) and P_G(k) for the complete graph G = K_n .
  1. Show that a proper k-coloring of G is equivalent to an acyclic orientation O along with set S of n elements chosen from {1,..,k}. Hint: Think of a proper n-coloring as a way of giving a rank to each player in a tournament. This is equivalent to a way of specifying who beats whom in any matchup of two players, which in turn is equivalent to an acyclic orientation. Argue similarly for a proper k-coloring for k ≥ n.
  2. Show that a weakly compatible pair (O,c) is equivalent to O along with multi-set S of n elements chosen from {1,..,k}.
  3. Using the above equivalences, show directly that P_G(k) = (−1)ⁿ P_G(−k) for this graph.
Quiz 4/14: Acyclic orientations, proof of Stanley's Theorem.

Notes

Notes 1/14-1/28
- A network consists of a directed multi-graph G = (V,E) with distinguished vertices s (the source) and t (the sink), along with a function specifying the capacity of each edge (a positive integer, possibly infinite). That is, cap : E → Z_≥0 ∪ {∞} .
- A cut of G is a partition of the vertices into disjoint sets, V = S ∪ T, with s ∈ S and t ∈ T.
- A flow on G is function f : E → Z_≥0 such that, at any vertex v ≠ s,t, the net flow from v (outflow minus inflow) is zero. We say f is c-limited if f(x,y) ≤ c(x,y) for all edges (x,y).
- The volume flow(f) is the net flow from the source s, which is negative the net flow from the sink t.
- For any cut (S,T), define flow(f;S,T) to be the net flow from S to T:flow(f;S,T) := ∑ f(x,y) − ∑ f(y,x)where the sums are over pairs of vertices (x,y) such that x &isin S and y ∈ T , and we count f(x,y) = 0 if (x,y) is not an edge of G.
- Lemma: flow(f;S,T) = flow(f) for any cut (S,T).
- The capacity of a cut is cap(S,T) := ∑ cap(x,y) where the sum is over edges (x,y) with x ∈ S and y ∈ T.
- Lemma: for any c-limited flow f and any cut (S,T), we have flow(f) ≤ cap(S,T) . If this happens to be an equality, then there can be no flow with a larger volume, and no cut with a smaller capapcity.
- Max-Flow/Min-Cut Theorem: The maximum volume of a c-limited flow is equal to the minumum capacity of a cut.
- The MF/MC Theorem is proved by the Augmenting Path Algorithm. This takes any c-limited flow f and produces either:
  1. an augmented c-limited flow f ' with flow(f ') = flow(f) + 1
  2. a cut (S,T) such that flow(f) = cap(S,T), which proves that f is a maximal flow and (S,T) is a min cut
- The Augmenting Path Algorithm: Start with a c-limited flow f on a network G, and define an auxiliary directed graph G' with the same vertices as G, and edges:(x,y) ∈ G' ⇔ (x,y) ∈ G and f(x,y) < cap(x,y)
  or (y,x) ∈ G and f(y,x) > 0 .
  1. If there exists a directed path P = x₀x₁...x_k ⊂ G' from s = x₀ to t = x_k , then define the augmented flow f ' by:f '(x,y) = f(x,y) + 1 if (x,y) ∈ P
    f(x,y) − 1 if (y,x) ∈ Pand f '(x,y) = f(x,y) otherwise. Then f ' is a c-limited flow with volume flow(f ') = flow(f) + 1.
  2. If there is no augmenting path P, then define the cut:S = {v s.t. ∃ directed path in G' from s to v} and T = V − S .We have flow(f) = cap(S,T).
Notes 1/28: Hall Matching Theorem
Notes 2/8: Given a 3-connected graph, produce an edge e = xy such that the contracted graph G/e is still 3-connected.
Algorithm: Take any edge x₀y₀. If G / x₀y₀ is 3-connected, DONE. Otherwise we can find a 3-element set {x₀,y₀,x₁} which separates G. Let C₁ be the smallest component of G − {x₀,y₀,x₁}, and let y₁ ∈ C₁ be a neighbor of x₁ . Now repeat. At step k, take the smallest component C_k of G − {x_k-1,y_k-1,x_k} which does not contain x_j , y_j for j = 1,2,...,k-2. We showed that C_k+1 ⊂ C_k − y_k for all k, so the algorithm must terminate.
Notes 2/15 Kuratowski Theorem: Given a graph G, we can produce either a plane drawing of G (without edges crossing) or non-planar subgraphs TK₅ or TK_3,3 ⊂ G.
Algorithm:
1. If κ(G) = 1, we examine each of its 2-blocks in turn; if these turn out to be planar, then the 2-block tree of G can easily be used to combine the drawings of the 2-blocks into a drawing of G (provided the cut-vertices of G are drawn on the exterior of each 2-block). If one of the 2-blocks contains TK₅ or TK_3,3 , then so does G.
2. If &kappa(G) = 2 and G ≠ K₃ , we find a minimal set of disconnecting vertices {x,y} and write G = G₁ &cup G₂ with G₁ &cap G₂ = {x,y}. We examine the graphs G₁ + xy and G₂ + xy (i.e., add the edge xy if it is not already present in G). If these graphs turn out to be planar, their drawings can easily be combined along the edge xy to produce a drawing of G (provided xy is on the exterior of the drawing). If these graphs contain TK₅ or TK_3,3, then so does G (exercise).
3. If &kappa(G) ≥ 3 and G ≠ K₄ , then we find an edge xy ∈ G such that G' = G/xy is still 3-connected (see above algorithm). If G' has a TK₅ or TK_3,3 , then so does G (exercise). If G' has a plane drawing, then the contracted vertex v = v_xy is inside some region of G' - v, and the boundary of this region is a cycle C (since G' − v is 2-connected). Let: G'' = G' − {vy' s.t. yy' ∈ G , xy' ∉ G} .Then clearly G'' ≅ G − y, so to construct G we only need to draw the vertex y and the edges yy' ∈ G.
4. Continuing the previous case, we may add to G'' the vertex y and the edges yy' ∈ G when the vertices y' ∈ N_G(y) all lie in a single sector of C, i.e. between consecutive neighbors of x along C. The possible obstructions are (exercise):
  - Four vertices y',y'' ∈ N_G(y) and x', x'' ∈ N_G(y), distinct from each other and from x,y, whose order around C is: x', y', x'', y''. Then the graph consisting of {x, x', x'', y, y', y''} with the edges between them and the arcs of C between them, clearly forms a TK_3,3 ⊂ G.
  - Three vertices x', x'', x''' ∈ N_G(x) ∩ N_G(y). Then the graph consisting of {x, x', x'', x''', y} with the edges and arcs of C between them, clearly forms a TK₅ ⊂ G.
  - Four vertices x', x''' ∈ N_G(x) ∩ N_G(y) and with x'', x''' ∈ N_G(x), whose order around C is: x, x', x'', x''', x''''. Then the graph consisting of {x, x', x'', x''', x'''', y} with the edges between them and the arcs of C between them, clearly contains a TK_3,3 ⊂ G.
Applying the above algorithm repeatedly (recursively), we terminate either with a plane drawing of G or a copy of TK₅ or TK_3,3 ⊂ G.
Notes 2/22: The crossing number cr(G) of a graph is the minimal number of crossings in a plane drawing of G. (We assume that all crossings are at the interior of two edges only, never three or more edges at one point, or an edge running over a vertex.)
Notes 3/10:
Method of Generating Functions.
- Goal: Explicitly compute a sequence of numbers a_k = #A_k which count a sequence of combinatorially defined sets A₀, A₁, A₂,....
- Step 1. Form the generating function:
  f(x) = a₀ + a₁x + a₂x² + .... = ∑_k≥0 a_k x^k .
  This is a function of the variable x, a polynomial if the sequence {a_k} is finite, or a Taylor series if the sequence is infinite. Use combinatorial properties of the sets A_k to get a simple formula for f(x).
  - If we can reduce the choice of an element S ∈ A₀ ∪ A₁ ∪ A₂ ∪ ... to a sequence of independent simple choices, we get a product formula for f(x).
  - If we can find f(x) in terms of any known Taylor series (such as the geometric series), we can replace the series by its function.
- Step 2. Given f(x), use algebra and calculus to expand it as a power series, thereby evaluating the coefficients a_k.
  - Taylor's formula: a_k = f^(k)(0) / k! , where f^(k)(0) means the k^th derivative of f(x) evaluated at x = 0. This is valid for all functions, but is gives useful results only for especially simple ones.
  - Try to write f(x) in terms of functions with known Taylor series.
Fundamental Example: The Binomial Theorem
- Problem: Fix n, and let A_k be the collection of all k-element subsets of an n-element set. Then a_k = #A_k is called "n choose k", which I will denote on this webpage as (n | k).
  For example, if n = 3, the sets are: A₀ = {∅}, A₁ = {{1}, {2}, {3}}, A₂ = {{1,2}, {2,3}, {1,3}}, A₃ = { {1,2,3} }, so a₀ = (3 | 0) = 1 , a₁ = (3 | 1) = 3 , a₂ = (3 | 2) = 3 , a₃ = (3 | 3) = 1 .
- Step 1: Find a simple formula for f(x) = ∑ a_k x^k.
  - Choosing a subset S ⊂ {1,2,3} is equivalent to choosing or not choosing each of the three elements 1,2,3. We figure the possiblilities for S by considering the logical expression:
    (0E₁ or 1E₁) and (0E₂ or 1E₂) and (0E₃ or 1E₃),
    where 0E_j means "j is not in S" and 1E_j means "j is in S".We expand this expression using the logical distributive rule:
    (P or Q) and R = (P and R) or (Q and R).Here P,Q,R are simple statements, and the compound statements on the two sides of the equation are logically equivalent. We expand until we have the expression: (0E₁ and 0E₂ and 0E₃) or (0E₁ and 0E₂ and 1E₃) or ... or (1E₁ and 1E₂ and 1E₃) ,in which the 8 terms correspond to the subsets S = &empty, {3}, ... , {1,2,3} .
  - Now we rewrite the entire computation, replacing the statements 0E_j by the value x⁰ = 1; the statements 1E_j by the variable x¹ = x; the operation "or" by + ; and the operation "and" by ×. Notice that each successive logical equality becomes a valid algebraic equality. In the end we have shown that:(1+x)(1+x)(1+x) = 1.1.1 + 1.1.x + 1.x.1 + x.1.1 + ... + x.x.x ,(where . means multiply). The 8 terms again correspond to subsets S, which record the positions of the x's, and the power of x is precisely the number of elements in S. Now we collect x^k terms to get a polynomial c₀ + c₁ x + c₂ x² + c₃ x³ , where the coefficient c_k is the number of x^k terms, which is just the number of k-element subsets. That is, c_k = a_k = (3 | k), so we conclude that (1+x)³ = f(x) .
  - For a general n, we repeat this argument to get f(x) = (1+x)ⁿ.
  - Step 2: We apply Taylor's Formula to the derivatives of f(x) = (1+x)ⁿ, namely f '(x) = n(1+x)ⁿ⁻¹, f "(x) = n(n−1)(1+x)ⁿ⁻², ... , f ^(k)(x) = n(n−1)...(n−k+1)(1+x)^n−k .The result is:(n | k) = a_k = f^k(0) / k! = n(n−1)...(n−k+1) / k! = n! / k!(n−k)! , which is the familiar formula for the binomial coefficient (n choose k).
  - As a by-product, we get the theorem for the expansion of a binomial, (1+z)ⁿ = ∑_k=0ⁿ (n | k) z^k ,where z is any algebraic quantity. Using z = b/a and clearing denomiantors gives us the full Binomial Theorem:(a + b)ⁿ = ∑_k=0ⁿ (n | k) a^n−k b^k .
- Notes 3/12: Hands from a double deck.
  - Problem: How many distinguishable 5-card hands can be dealt from two identical 52-card decks (a double deck)?
  - Step 0: Generalize the problem into a sequence of numbers {a_k} = a₀ , a₁ ,..., a_n . Let a_k be the number of k-card hands dealt from a double deck, for k = 0, 1, 2,..., 104. That is, a_k = #A_k , where A_k is the collection of all k-card hands, so that A = A₀ ∪ A₁ ∪ ... is the collection of all possible hands, with any number of cards.
  - Step 1: Define the generating function : f(x) = a₀ + a₁ x + a₂ x² + ... + a₁₀₄ x¹⁰⁴ = ∑_k=0¹⁰⁴ a_k x^k . Find a simple formula for f(x) using the combinatorial properties of the set A. Now, a hand H ∈ A can be chosen according to the logical expression: choose H ⇔ (0C₁ or 1C₁ or 2C₁) and ... and (0C₅₂ or 1C₅₂ or 2C₅₂), where 0C_i means "exclude the i^th card of the deck", 1C_i means "include 1 of the i^th card of the deck", and 2C_i means "include 2 of the i^th card of the deck". We turn the logical equivalence into an algebraic equation by replacing as follows:
    
    logic choose H ⇔ 0C_i 1C_i 2C_i or and
    algebra f(x) = x⁰ x¹ x² + ×
    We obtain:
    f(x) = (x⁰ + x¹ + x²) × ... × (x⁰ + x¹ + x²) = (1 + x + x²)⁵² .
  - Step 2: Use algebra to expand f(x) and compute the coefficients a_k . Taylor's Formula gives a mess, so we try to use known Taylor series.We cannot directly apply the Binomial Theorem to powers of 1 + x + x² , so we apply it twice, the first time to 1 and x+x², the second time to x and x²:
    f(x) = [1 + (x+x²)]⁵² = ∑_j=0⁵² (52 | j) (x + x²)^j = ∑_j=0⁵² (52 | j)∑ _i=0^j (j | i) x^j-i (x²)ⁱ
    = ∑_j=0⁵² ∑_i=0 ⁵² (52 | j) (j | i) x^j+i = ∑_k=0¹⁰⁴ [ ∑_(i,j) (52 | j) (j | i) ] x^k .
    where the last summation runs over all (i,j) such that 0 ≤ i ≤ j and i + j = k . That is, (i,j) = (0,k), (1,k-1), (2,k-2), ... , (⌊k/2⌋, ⌈k/2⌉) where ⌊ ⌋ means round down and ⌈ ⌉ means round up. We conclude that:
    a_k = ∑_i=0^⌊k/2⌋ (52 | k-i) (k-i | i) .
    For example for k = 2, we have (i,j) = (0,2), (1,1) and a₂ = (52 | 2) (2 | 0) + (52 | 1) (1 | 1): this makes sense, since the terms correspond to choosing two distinct cards, or one double card.
    For k = 5, we have (i,j) = (0,5), (1,4), (3,2) and:
    a₅ = (52 | 5) (5 | 0) + (52 | 4) (4 | 1) + (52 | 3) (3 | 2) .
    Can you explain this directly?
- Notes 3/14: Multi-sets.
  - A multi-set is an unordered collection of objects with repeats allowed (doubles, triples, etc.). The multi-choose number (n multi-choose k) = ((n | k)) is the number of multi-sets containing k objects of n kinds. For example, ((2 | 4)) = 5 counts the mult-sets:{1,1,1,1} {1,1,1,2} {1,1,2,2} {1,2,2,2} {2,2,2,2} . We can compute ((n | k)) by arguments completely analogous to our computation of (n | k), which counts ordinary subsets (without repeats).
  - Step 1. Fix n, and let a_k = ((n | k)). The generating function is:f(x) = (1 + x + x² + x³ + ...)ⁿWe can simplify this using a known Taylor series: the geometric series 1 + x + x² + ... = 1/(1−x) : f(x) = ( 1/(1−x) )ⁿ = 1/(1−x)ⁿ.
  - Step 2. We expand by Taylor's Formula: f(x) = (1−x)⁻ⁿ , f ^(k) = n(n+1)(n+2)...(n+k−1)(1−x)^−n−k , so: a_k = ((n | k)) = n(n+1)(n+2)...(n+k−1) / k! .For example, ((2 | 4)) = 2×3×4×5 / 4! = 5.
  - As a by-product, we obtain the useful power series formula:1/(1 − z)ⁿ = ∑_k≥0 ((n | k)) z^k ,where z is any algebraic quantity.
- Notes 3/14 & 3/17: First recurrence for rooted trees.
  - A rooted tree is a tree in which one vertex has been labelled as the root. (This can be any vertex). Let r_n be the number of distinct rooted, unlabelled trees. For example, r₃ = 2 counts the rooted trees:®−−O−−O O−−®−−ONote that if the root is on the last vertex, this is symmetric to (and hence equal to) the first example. To compute r₄, consider that the linear tree can have its root on an end or an inner vertex, and the 3-branch star can have the root in the center or on a branch, so that r₄ = 2 + 2 = 4. No one has found an explicit formula for r_n . Our goal is to find a recursive formula.
  - Rooted trees satisfy a kind of combinatorial recurrence which will lead to a recursive formula for r_n. Given a rooted tree T, we mark each neighbor of the root as a new root, and remove the original root. This leaves a set of smaller rooted trees: {T', T'',...}. Some of these might be repeated, so it is really a multi-set. This mapping is reversible, so we get a one-to-one correspondence:
    rooted T with n+1 vertices &harr multi-sets {T', T'',...} with total n vertices.
  - Let h_n count the multi-sets H = {T',T'',...} with n vertices, as described. By the correspondence, we have r_n+1 = h_n . Let us compute h_n by the method of generating functions.
    Step 1: Let T_k⁽ⁱ⁾ be the i^th kind of rooted tree with k vertices, where i = 1, 2,..., r_k . Then a choice of multi-set H corresponds to choosing how many of each tree T_k⁽ⁱ⁾ :
    multi-set H = {T', T'',...}     ⇔
                                  (0T₁ or 1T₁ or 2T₁ or ....)and (0T₂ or 1T₂ or 2T₂ or ....) and
                                  (0T₃⁽¹⁾ or 1T₃⁽¹⁾ or 2T₃⁽¹⁾ or ....)and (0T₃⁽²⁾ or 1T₃⁽²⁾ or 2T₃⁽²⁾ or ....) and ...
    We convert this to algebra, replacing each jT_k⁽ⁱ⁾ by x^jk, since this choice adds jk vertices to H. The result is:
    h(x) = ∑_n≥0 h_n xⁿ = ∏_k≥1 (1 + x^k + x^2k + ...)^r[k] = ∏_k≥1 (1 − x)^−r[k] ,
    where we have written r[k] instead of r_k for legibility.
  - Step 2: We know from our computation of multi-choose numbers that (1 − x)^−r = ∑_k≥0 ((r | k)) x^k. Substituting this into the h(x) formula, multiplying out and collecting xⁿ terms, we conclude with the First Recurrence Formula:
    r_n+1 = h_n = ∑_||k||=n ((r₁ | k₁)) ((r₂ | k₂)) ((r₃ | k₃)) ...
    where the sum is over all sequences k = (k₁, k₂, k₃,...) such that ||k|| := k₁ + 2k₂ + 3k₃ + ... = n . In fact, only r₁,..., r_n occur in this formula, so it is a recurrence for r_n+1 .
  - Example: To compute r₅, we sum over k = (4), (2,2), (1,0,1), (0,0,0,1), so that:
    r₅ = ((r₁ | 4)) + ((r₁ | 2)) ((r₂ | 2)) + ((r₁ | 1)) ((r₃ | 1)) + ((r₄ | 1)) .
    Substituting r₁ = r₂ = 1 , r₃ = 2 , r₄ = 4 and computing multi-choose numbers gives r₅ = 1 + 1 + 1 + 2 + 4 = 9.
- Notes 3/19: Second recurrence for rooted trees.
  - Starting with the First Recurrence Formula for r_n, we derive a more useful formula. We start by writing the recurrence as an identity of generating functions. Letting r(x) = ∑_n≥1 r_n xⁿ (defining r₀ = 0), we have r(x)/x = ∑_n≥0 r_n+1 xⁿ , and:
    r(x)/x = h(x) = ∏_k≥1 (1 − x^k)^−r[k] ,
    where for legibility I have written r[k] instead of r_k .Now we use the dlog method to simplify this equation: that is, we apply the operation x d/dx log to both sides of the identity r(x)/x = h(x) .
  - Left side: Note that x d/dx log( f(x) ) = x f '(x) / f(x), so that:
    x d/dx log( r(x)/x ) = ∑_n≥1 n r_n+1 xⁿ / ∑_n≥0 r_n+1 xⁿ
  - Right side: We have log(uv) = log(u) + log(v), and thus log( ∏_k u_k ) = ∑_k log(u_k) . Also −log(1 − x) = &sum_i≥1 ¹/_i xⁱ . Hence:
    log h(x) = ∑_j≥1 −r_j log(1 − x^j) = ∑_j≥1 ∑_i≥1 r_j / i x^ij
    = ∑_k≥1 ∑_{j | k} (j / k) r_j x^k = ∑_k≥1 q_k x^k ,
    where in the third equality we substitute k = ij , and j | k means j evenly divides k. Also, we define q_k = ∑_{j | k} (j / k) r_j . Taking the derivative:
    x d/dx log(h(x)) = ∑_k≥1 k q_k x^k .
  - Now equating x d/dx log( r(x)/x ) = x d/dx log h(x) , clearing the denominator, and collecting xⁿ terms, we get:
    ∑_n≥1 n r_n+1 xⁿ = ∑_k≥1 k q_k x^k × ∑_m≥0 r_m+1 x^m = ∑_n≥1 ( ∑_k≤n k q_k r_n−k+1 ) xⁿ ,
    where in the second equality we substitute n = k + m , so that m+1 = n−k+1. We conclude:
    n r_n+1 = ∑_k≤n k q_k r_n−k+1
  - Substituting the definition of q_k and tidying, we obtain the Second Recurrence Formula:
    r_n+1 = ¹/_n ∑_k≤n ∑_{j | k} j r_j r_n−k+1 .
  - Example: To compute r₅ , we sum over k = 1,2,3,4 and j running over all divisors of k: that is, (j,k) = (1,1), (1,2), (2,2), (1,3), (3,3), (1,4), (2,4), (4,4),
    r₅ = ¹/₄ ( r₁r₄ + r₁r₃ + 2r₂r₃ + r₁r₂ + 3r₃r₂ + r₁r₁ + 2r₂r₁ + 4r₄r₁ )
    = ¹/₄ (4 + 2 + 4 + 1 + 6 + 1 + 2 + 16) = 9
    In this small example, we have to sum more terms than for the First Recurrence Formula, but when n is large there are much fewer terms, and each term is much simpler.
  - In class, I gave a variation on this computation, taking the derivative of log h(x) before collecting terms:x d/dx log h(x) = x d/dx ∑_j≥1 ∑_i≥1 r_j / i x^ij
    = ∑_j≥1 ∑_i≥1 j r_j x^ij = ∑_k≥1 p_k x^k ,
    where p_k = ∑_{j | k} j r_j .This leads to:
    r_n+1 = ¹/_n ∑_1≤k≤n p_k r_n−k+1 ,
    which then expands into the same recurrence formula as before.
  Notes 3/24: Analysis of tree symmetries.
  - Goal: Compute t_n = # unrooted unlabelled trees, from known values of r_n = # rooted unlabelled trees. For each unrooted tree T, there are n possible vertices to mark as a root, but vertices which are symmetric to each other give the same rooted tree. Thus, r_n is generally not a multiple of t_n , because the number of non-symmetric vertices is not the same for each unrooted T. Thus, the analysis of symmetries is crucial in relating unrooted and rooted trees.
  - The symmetry group of T = (V,E) is:
    Γ = Γ_T = Sym(T) = { one-to-one &pi : V→V s.t. uv ∈ E ⇒ π(u)π(v) ∈ E },
    i.e., those permutations of the vertices which take edges of T to edges of T.
    A symmetry class of vertices is a set v = { π(v) s.t. π ∈ Γ }, all the vertices symmetric to a vertex v.
  - Let T = ( V, E_NS ) be the quotient graph of T by Γ_T, having vertices: V := { v s.t. v ∈ V }, and edges: E_NS := { uv s.t. uv ∈ E but u ≠ v}. These correspond to the non-symmetry (NS) edges of T, omitting the symmetry edges e = uv with v = π(u) which would lead to loops uv = uu in T .
  - For example, the tree:
    T = 1 −− 2 −− 3 −− 4
    | |
    5 6
    has as symmetries: the transposition of vertices 1, 5; the transposition of vertices 4, 6; the reflection which flips the whole tree horizontally; and all compositions of these. There are |Γ| = 8 symmetries in all. The edge 23 is a symmetry edge since 2 = 3 = {2,3}, so this edge is excluded from the quotient graph.
    The quotient graph is: T = 1 −− 2 −− 5 .
  - Otter's Lemma: If T is a tree, then its quotient graph T is also a tree.
    Proof: To see that T is connected, note that a path P from u to v in T corresponds to a walk from u to v in T. Since T is connected, so is T.
    To see that T is acyclic, suppose instead that T has a cycle C = (u,v,w,...,z) . Then we could lift this to a walk (u,v,w,...,z) in T, and then continue as: (u,v,...,z,u',v',....) where u' ∈ π(u) is some vertex of T symmetric to u, and v' = π(v), etc. If this walk ever repeats a vertex, we get a cycle in T, which is impossible since T is acyclic. Otherwise, the walk can be continued to an infinite path, which is impossible since T is finite. The contradiction proves there can be no cycles in T.
  Notes 3/26: Otter's Formula for t_n .
  - We define an edge-rooted tree to be a tree with one edge e marked as the root edge. We require that e not be a symmetry edge of the tree. Let e_n be the number of unlabelled edge-rooted trees with n vertices.
  - Claim: t_n = r_n − e_n .Proof: Given any unrooted tree T, Otter's Lemma says T is a tree with p_T vertices and q_T edges, so q_T = p_T − 1. Thus:
    r_n − e_n = ∑_T p_T − ∑_T q_T = ∑_T (p_T − q_T) = ∑_T 1 = t_n .
  - Claim: e_n = ½[ ∑_1≤i≤n r_i r_n−i − r_n/2 ] .
    Proof: Given an edge-rooted T" with n vertices, we can remove the root-edge e (but keep the endpoints) and obtain a set {T₁' , T₂'} of rooted trees with a total of n vertices. Furthermore, since e was not a symmetry edge, T₁' and T₂' are distinct rooted trees (not the same T ' twice). The number of ordered pairs (T₁' , T₂') with i and j vertices respectively is r_i r_j ; the number of ordered pairs ( T ', T ' ) consisting of the same T ' twice is r_n/2 ; so the number of unordered sets of distinct trees is given by the desired formula.
  - Combining the two claims above, we obtain Otter's Formula:
    t_n = r_n − ½[ ∑_1≤i≤n r_i r_n−i − r_n/2 ] .
- Notes 4/2: Graph Coloring (HHM Ch 1.4). Subgraph formula for chromatic polymomial.
  - We will consider a graph G = (V,E) with n vertices, m edges.
  - A k-coloring of a graph G = (V,E) is a function c : V → {1,...,k} giving each vertex a color represented by a number 1,...,k. The coloring is proper if c(i) ≠ c(j) for neighboring vertices i,j (i.e., ij ∈ E).
  - Counting function (chromatic polynomial) P_G(k) = # proper colorings of G with k colors.
  - Proposition: The counting function is a polynomial P_G(k) = ∑_0≤i≤n a_i kⁱ where: a_n = 1 , a_n−1 = −m , a₀ = 0 . That is:
    P_G(k) = kⁿ − m kⁿ⁻¹ + a_n−2 kⁿ⁻² + ... + a₁ k .
    This follows from the Subgraph Formula:
    P_G(k) = ∑_{F ⊂ E} (−1)^|F| k^{comp G[F]} ,
    where F runs over all sets of edges, G[F] = (V,F) denotes the subgraph of G with only the edges in F, and compG[F] is the number of connected components of G[F].
  - Proof of Subgraph Formula: The Principle of Inclusion-Exclusion (PIE) says that for a big set A and bad subsets A₁ ,..., A_m , the size of the good set A_good = A − (∪_i A_i) is given by:
    |A_good| = ∑_S (−1)^|S| |A_S|
    where S runs over all subsets S ⊂ {1,...,m} and A_S = ∩_i∈S A_i , the intersection of all Ai with i ∈ S.
    We apply this to A = { all coloring functions c : V → {1,..,k} } with a bad set corresponding to each edge e = uv, namely A_e = { colorings with c(u) = c(v) }. Then clearly A_good is the set of proper colorings, and for F ⊂ E, the bad colorings in A_F = ∩_e∈F A_e are just those which have a single color on each component of the subgraph G[F]. PIE then gives the Subgraph Formula.
- Notes 4/4: Recursive computation of chromatic polynomials
  - For an edge e = uv of G, the deletion G−e results from removing e (but leaving its ends u,v). The contraction G/e results from shrinking e to a single vertex (or deleting e and gluing together u and v).
  - Deletion-Contraction Formula: The chromatic polynomials of G, G−e, G/e are related by:
    P_G(k) = P_G−e(k) − P_G/e(k) .
    The formula can be proved by splitting proper colorings of G−e into those with c(u) ≠ c(v), which are also proper colorings of G; and those with c(u) = c(v), which give proper colorings of G/e. Thus P_G−e(k) = P_G(k) + P_G/e(k) .
  - This formula can be used to recursively compute P_G(k), since G−e and G/e both have fewer edges than G.
- Notes 4/9: Stanley's Paper
  - Glossary: Equivalences between Stanley's notation and ours.
    vertices edges delete edge chrom poly coloring
    Stanley |V| = p X G \ e χ(G;λ) σ compatible (O,σ)
    482 Lect |V| = n E G−e P_G(k) c weakly compatible (O,c)
  - Let G = (V,E) be a graph with n vertices, m edges. An acyclic orientation O is a way of orienting each edge uv ∈ E as u→v ∈ O or u←v ∈ O, so that there are no oriented cycles x₁→⋅⋅⋅→x_r→x₁ ⊂ O.A k-coloring is a function c:V → {1,...,k}.
    - A weakly compatible pair (O,c) on G consists of an acyclic orientation and a coloring such that c(u) ≥ c(v) for every edge u→v ∈ O.
    - A strongly compatible pair has the same definition, except with the strict inequality c(u) > c(v) .
  - Theorem 1.1: In a strongly compatible pair, the orientation adds no data since it can be deduced from c. Therefore the chromatic polynomial P_G(k) can be taken to count strongly compatible pairs (O,c), instead of just proper colorings c.
    In a weakly compatible pair, the orientation does add data. For example, if k = 1, then the coloring c(v) = 1 is constant and any orientation O is weakly compatible: here c adds no data.
  - Define P_G(k) to be the number of weakly compatible pairs (O,c) on G.
  - Theorem 1.2: P_G(k) = (−1)ⁿ P_G(−k) , where P_G(k) is usual chromatic polynomial and n is the number of vertices.
    This is a very surprising result. There is no obvious reason that |P_G(−k)| should count any kind of object.
- Notes 4/11: Proof of Stanley's Theorem 1.2
  - Strategy: Show that the right- and left-hand sides of the equation are functions which can be computed recursively by the same rules (basically the Deletion-Contraction Rule). Then, since the process of computing the two sides is exactly the same, the answers are also the same.
  - Denote the right-hand side as P'_G(k) = (−1)ⁿ P_G(−k). Then we can be compute P' by the rules:
    1. P'_K₁(k) = k , where K₁ is the one-vertex graph.
    2. P'_G∪H(k) = P'_G(k) P'_H(k) , where G ∪ H means disconnected union.
    3. P'_G(k) = P'_G−e(k) + P'_G/e(k) for any edge e.
  - We must show that the left-hand side function P_G(k) also satisfies rules i, ii, iii above. The first two are basically a matter of definition. For example, a weakly compatible pair (O,c) on G = K₁ is just a function c : {v} → {1,..,k}, and there are k of these. The bulk of the proof is showing (iii).
  - Let G be a graph and e = uv be an edge.
    - For an orientation O on G−e, let O_uv be the orientation on G consisting of O with the added edge u→v. Similarly O_vu adds the opposite edge v→u.
    - In the contraction G/e, let w = u = v be the contracted vertex. Define the orientation O/e on G/e to consist of all edges of O. If c(u) = c(v), we may consider c as a coloring of G/e by setting c(w) = c(u) = c(v).
  - Lemma: Let O be an acyclic orientation on G−e. Then:
    1. At least one of O_uv and O_vu is acyclic on G.
    2. Both O_uv and O_vu are acyclic on G ⇔ O/e is acyclic on G/e.
    Proof:
    1. If we had cycles:
      u→v→x₁→⋅⋅⋅→x_r→u ⊂ O_uv
      v→u→y₁→⋅⋅⋅→y_s→v ⊂O_vu ,
      one could piece them together to get a cycle:
      u→v→y₁→⋅⋅⋅→y_s→v→x₁→⋅⋅⋅→x_r→u ⊂ O .
      This contradicts the assumption that O is acyclic.
    2. We show the equivalent assertion: O_uv or O_vu has a cycle ⇔ O/e has a cycle.
      (⇒): If C is a cycle of O_uv or O_vu , then C/e is a cycle of O/e.
      (⇐): Suppose O/e has a cycle C'. If C' does not pass through the contracted vertex w ∈ G/e, then C' is immediately a cycle in O_uv and O_vu . If C' passes through w along a path x→w→y, where xu, vy are edges of G−e, then clearly C' ∪ (u→v) is a cycle in O_uv. Similarly, if xv, uy are edges of G−e, then C' ∪ (v→u) is a cycle in O_vu .
  - Lemma: Let (O,c) be a weakly compatible pair on G−e. Then:
    1. At least one of (O_uv,c) and (O_vu,c) is acyclic on G.
    2. Both (O_uv,c) and (O_vu,c) are acyclic on G ⇔ (O/e,c) is acyclic on G/e.
    Proof:
    1. If both O_uv and O_vu are acyclic, then clearly one of (O_uv,c) and (O_vu,c) is weakly compatible on G. On the other hand, if u → v → x₁ → ⋅⋅⋅ → x_r → u ⊂ O_uv is a cycle, then by the previous Lemma O_vu is acyclic. Since all but the first edge of the cycle lies in O and c is weakly compatible, we get c(v) ≥ c(x₁) ≥ ⋅⋅⋅ ≥ c(x_r) ≥ c(u). Hence c(v) ≥ c(u) and (O_vu, c) is a weakly compatible pair.
    2. (⇒): If both (O_uv,c) and (O_vu,c) are weakly compatible on G, then c(u) ≥ c(v) and c(u) ≤ c(v), so that c(u) = c(v). Also, by the previous Lemma O/e is acyclic. Thus (O/e,c) is weakly compatible.
      (⇐): If (O/e,c) is weakly compatible, by definition c(u) = c(v). Also, by the previous Lemma both O_uv and O_vu are acyclic. Hence both (O_uv,c) and (O_vu,c) are weakly compatible.
  - Now, given an acyclic orientation O₊ on G, we can remove e to get an acyclic orientation O of G−e. By the first Lemma, this correspondence is onto. It is one-to-one if only one of O_uv and O_vu is acyclic, but two-to-one if both are acyclic. By the second Lemma, the same is true of weakly compatible pairs (O₊,c). Thus we can compute:
             P_G(k) = #{(O₊,c) weakly compatible on G}
                        = #{(O,c) w.c. on G−e, only one of (O_uv,c) & (O_vu,c) is w.c.}
                              + 2 #{(O,c) w.c. on G−e, both of (O_uv,c) & (O_vu,c) are w.c.}
                        = #{(O,c) w.c. on G−e} + #{(O,c) w.c. on G/e}
                        = P_G−e(k) + P_G/e(k)
    The third equality uses Lemma (b). This proves rule (iii), and so Theorem 1.2.
References
- HHM Harris, Hirst Mossinghoff, Combinatorics and Graph Theory, Ch 1 (basic graph theory review)
- FCM Bollobas, Basic Graph Theory, Ch III: Flows, Connectivity, and Matching
- KUR R. Diestel, Graph Theory, Ch 3 & 4 on Kuratowski Theorem.

logic	choose H	⇔	0C_i	1C_i	2C_i	or	and
algebra	f(x)	=	x⁰	x¹	x²	+	×

	vertices	edges	delete edge	chrom poly	coloring
Stanley	\|V\| = p	X	G \ e	χ(G;λ)	σ	compatible (O,σ)
482 Lect	\|V\| = n	E	G−e	P_G(k)	c	weakly compatible (O,c)

T =	®−−	®	−−®	−−O
		\|
		®

T =	1 −−	2	−− 3	−− 4
		\|	\|
		5	6

MSU MATHEMATICS

MTH 482 Old Homework

MTH 482
Old Homework