Math 511: Introduction to Combinatorics
Spring 2009

Supplementary Text and Additional Problems

All references are to

• J.H. van Lint and Richard M. Wilson, A Course in Combinatorics, second edition, Cambridge University Press, 2001.

C(n, k) denotes the binomial coefficient. (This is a bit of an abuse; normally C(n, k) should mean the number of k-combinations of an n-element set.)

1. König's Theorem 5.4' (Expansion of Theorem 5.4). Both the following equivalent statements are true.
   1. In a bipartite graph G, the maximum size of a matching equals the minimum number of vertices that cover all edges.
   2. In a matrix A, the maximum number of nonzero elements such that no two are in a line together equals the minimum number of lines that cover all nonzero elements.
   
   
2. Corollary 5.4". The rank of a matrix A is not more than the minimum number of lines that cover all its nonzero elements. (A useful concept is that of a transversal of A, which means a set of positions, no two in a row or column, whose contents are all nonzero. Theorem 5.4'(2) concerns the maximum size of a transversal.)
   
   
3. Theorem 6.3+. The only antichains of maximum size are P_floor(n/2) and P_ceil(n/2) (which are the same if n is even).
   
   
4. Theorem 10.1' (= Remark on p. 90). In Theorem 10.1, let Σ_k := N − N₁ + N₂ + ... + (−1)^k N_k and Σ := Σ_r = (10.4). Then
   FALSE:     Σ₀ ≥ Σ₂ ≥ Σ₄ ≥ ... ≥ Σ ≥ ... ≥ Σ₃ ≥ Σ₁ .
   TRUE, corrected formula:     Σ_2k ≥ Σ ≥ Σ_2k+1 for each k ≥ 0.
   
   
5. A more precise name, though less well known, for the "Euler function" is the Euler totient function.
   
   
6. Theorem 10.a. See the top of p. 91. Define the forward difference operator D by DP(x) := P(x+1) − P(x). (The usual symbol is Del, the upside-down Δ.) Then
       D^kP(x) = Σ_i=0^k (−1)ⁱ C(k,k−i) P(x+k−i).
   (Setting x = 0, you get the equation of p. 91, line 12.)
   
   
7. A sequence of polynomials, { p_n(x) : n = 0, 1, 2, ... }, is said to have binomial type if deg p_n(x) = n and
       p_n(x+y) = Σ_k=0ⁿ C(n,k) p_k(x) p_n-k(y) .
   Such a sequence has many of the nice properties of the monomial basis { xⁿ }.
   
   
8. Problem 14L. The walks should not "contain" a point on x + y = 2, they should start at (0,0) and end on the line.
   
   
9. The levelling operation at the beginning of Chapter 16 must preserve the partition property of the sequence; i.e., you can only apply the operation to a partition of N if the result is a partition of N. There are several reasons for this, for example, that levelling is related to covering in the poset of partitions of integers.
   
   
10. Theorem 17.9. The term "χ(L)-colorable" conflicts with established usage and the definition on page 194; it should be "χ(L)-list-colorable".
    
    
11. The chromatic number of the line graph L(G) is usually called the chromatic index of G, written χ'(G). There are an extensive literature and major open questions.
    
    
12. Figure 18.3 is the transpose of the correct figure.
    
    
13. In the proof of Theorem 18.6 the notation d(x,c) has not been defined. It means the number of places in which x and c differ. (Hamming distance; see Ch. 20.)
    
    
14. The notation in Problem 18F is confusing. The dot in v_i · v_j is the wrong symbol; it's not the dot product, it's the Hadamard product. The Hadamard product of two matrices (of the same size) is their component-wise product and is indicated by a circle:
        A ο B := (a_ij b_ij)_i,j .
    In this case the matrices are row matrices; their Hadamard product is v_i ο v_j := (v_ikv_jk)_{k=0,...,n−1}.
    
    
15. There seems to be a definition of μ missing in the last corollary on p. 220.
    
    
16. The definition of a projective plane as a symmetric design with λ = 1, in Chapter 19, is not the normal definition. (It's only normal for design theorists.) The usual definition is by geometrical axioms. We have a set P of "points" and a set B of subsets of P, called "lines" (or "blocks"), such that (a) every pair of points lies in a unique line, (b) every pair of lines has a common point, (c) every line has at least 3 points.
    
    

• Problem 5H. Prove that the two statements in König's Theorem 5.4' really are equivalent.
• Problem 5I. Deduce one of the forms of the Marriage Theorem from one of the forms of König's Theorem 5.4'. For instance, deduce the graphical Marriage Theorem 5.1 from Theorem 5.4'(a). Or, deduce the set-theoretic Marriage Theorem from Theorem 5.4'(b).
• Problem 5J. Prove Corollary 5.4".
  
  
• Problem 6F. Use symmetric chain decompositions to prove that a maximum antichain A in B_n must be either P_floor(n/2) or P_ceil(n/2). (Don't use any of the information we gained from the Lubbell-Meshalkin proof.) Hint: Look at "short" chains (size 1 or 2) and how they're related to A. Think about using different decompositions.
• Problem 6G. In Theorem 6.4, can you describe all largest families A? Hint: Find an "obvious" example A that has C(n−1, k−1) members, and decide whether there can be any others.
  
  
• Problem 10I. Prove Theorem 10.1'.
• Problem 10J. Prove Theorem 10.a.
• Problem 10K. Express (10.7) in terms of the Möbius function μ.
• Problem 10L. Define the convolution product of functions N —> N by (f*g)(n) := Σ_{d | n} f(d) g(n/d). Show that (1/μ)(n) = 1 for all n > 0 with this product.
• Problem 10M. Let r be an integer ≥ 0.
  1. Show that C(x, r) = (−1)^r C( −[x−r+1], r ). (Remember, I'm abusing notation by writing C(x, r) for the binomial coefficient.)
  2. Give a combinatorial proof of the Vandermonde convolution identity Σ_i≥0 C(x, i) C(y, r−i) = C(x+y, r).
  3. Combine parts (a) and (b) to prove (10.5) by manipulating binomial coefficients.
  
  
  
• Problem 13C'. In Problem 13C, how many unordered pairs are there?
• Problem 13L. Follow through the remark on the top of p. 125 by providing a combinatorial proof of (13.7), or of (13.8), or both. (Which is easier to do this way, the formula without minus signs, or the one with them?)
• Problem 13M. I give you a basis of polynomials of the form { p_n(x) : n = 0, 1, 2, ... } where deg p_n(x) = n. Check it for having binomial type.
  1. The rising factorials.
  2. The binomial-coefficient polynomials C(x, n).
  3. The Hermite polynomials (look them up).
  What effect does the leading term have on the property of binomial type? Does it help if you normalize so the polynomials are all monic?
  
  
• Problem 14P. Complete the generating function derivations for loose cacti and loose cactus forests, and extract a formula for the number with n vertices (if possible).
• Problem 14Q. A coloring of a set in k colors is an assignment to each point of one element of [k]. A colored graph is a graph whose vertex set is colored (with no restrictions; this is not proper graph coloring).
  1. Find the exponential generating function L(x) for colorings of a single point.
  2. (Advanced.) Use the method of compound generating functions to get a generating function for the number of k-colored n-element sets. (Hint: How many indeterminates should your generating function have?) Compare with the obvious combinatorial answer.
• Problem 14R. Find the exponential generating function for caterpillars by the method of composition, using those for paths and for rooted trees.
  
  
• Problem 16D'. Improve the result of Corollary 16.4 for every k, not only k = n/2, by inspecting the proof closely.
• Problem 16J. In the proof of Theorem 16.2 we actually prove that M(r,s) > M(r',s'). How does this let you strengthen the conclusion of the theorem?
• Problem 16K. There is a gap in the proof of Theorem 16.4. It's the part they call "an easy exercise". Fill in the gap. (How easy is it?)
• Problem 16L. Assume d_n, n ≥ 0, are nonzero numbers. For a sequence { a_n : n ≥ 1 }, define
      GF(a; x) := Σ_n≥1 a_n xⁿ / d_n .
  Decide whether it's always true, independent of the exact d sequence, that
      exp[ GF(a; x) ] = Σ_k≥0 [1/d_k] [ Σ_{n1,...,nk≥0} Π_i=1,...,k a_ni x^n_i / d_ni ] .
  If this is not generally true, (a) does it help if d₀ = 1? (b) under what conditions on the d's is it true? Use your results to show that the formula is true if d_n = n! and also if d_n = (n!)² .
• Problem 16M. (Continuation of 16L.) We found an exponential formula when d_n = n! and also d_n = (n!)² . Is there a more general exponential formula? This is an open-ended problem with no evident answer, since the exponential formula involves an exponential connection between two combinatorially significant sequences, and I don't know what that would mean for d_n ≠ n!. Probably there are theorems about this; you might look them up if you're interested.
• Problem 16N. Do the calculations to prove that the correct asymptotic value in Theorem 16.4 is as stated. I believe this entails multiplying out the series in e^-x/2 · (1-x)^-1/2 to find the n-th term and cleverly watching what happens as n —> infinity. It's an interesting experience.
  
  
• Problem 17D'. Use 17D to show many examples of Latin squares that are not even isotopic to group multiplication tables. (Note that in 17D, the order-m subsquare is not prescribed in advance.)
• Problem 17K. Let T(n) be the lower bound on L(n) from Theorem 17.2, and let R(n) be the lower bound in the Remark, p. 187.
  1. Show that T(n) and R(n) are increasing.
  2. Show that T(n)/R(n) is increasing.
  3. Find a meaningful asymptotic estimate for T(n)/R(n). (An asymptotic estimate should make it easy to see how big the quantity is. That's the hard part.)
• Problem 17L. Show that if L is a Latin square that is isotopic to a group multiplication table, then every conjugate of L is also isotopic to a group table.
  
  
• Problem 18J. Why is the formula of Theorem 18.3 just what it is? Think why it is limited to one conference matrix C that must be symmetric. (a) Is there a reason one can't use an antisymmetric conference matrix? (b) Four different conference matrices (symmetric or antisymmetric)? (c) Something else? (d) If you do find a way to do any of these variations, does it give Hadamard matrices that we don't get by the constructions studied up to that point in the chapter?
• Problem 18K. As on page 202, q is an odd prime power.
  1. Prove the character χ on page 202 is multiplicative.
  2. Prove that F_q has equally many squares and nonsquares (excluding 0).
  3. Prove that −1 is a square in F_q if and only if q = 1 mod 4. Deduce that Q is symmetric if q = 1 mod 4 and antisymmetric if q = 3 mod 4.
  4. Prove that (18.5) is really a conference matrix; that includes proving all the claims made in the previous few lines.
• Problem 18L. What does Williamson's construction amount to if all A_i = A?
• Problem 18M. Find all sign patterns in the matrix of (18.6) that give the conclusion (18.7).
• Problem 18N. In order to get a Hadamard matrix by the construction in (18.6), how necessary is it to assume (a) the A_i's are symmetric, or (b) they commute? E.g., does each assumption simplify the problem slightly, or enormously, or is it essential? Exactly what is necessary to make (18.6) a Hadamard matrix, and what is not?
  
  
• Problem 19W. Prove Theorem 19.3.
• Problem 19X. Prove that in a symmetric 2-design with λ = 1, every pair of blocks ("lines") intersects in exactly one point. (This means that such a design really is a projective plane in the ordinary sense.)
• Problem 19Y. Prove that a (finite) projective plane in the axiomatic geometrical definition (see above) really is a block design.
• Problem 19Z. Prove or disprove: An incidence structure is a 2-design if and only if its incidence matrix satisfies Equation (19.7). If it's not true, is there a simple additional condition that makes it true?
  
  

To the main course page | schedule and homework page | student presentations | syllabus.

To my home page.