Combinatorics
Comprehensive Exam
August 20, 1990

Directions: You may take up to 4 hours on this exam.
Please return the exam along with your solutions.

  1. (a). Define the Möbius function m(x,y) on a poset (X,£).
    (b). Consider the poset of all subsets of a finite set X ordered by inclusion. Show that the Möbius Function for this poset is m(A,B)=(-1)|B|-|A|.
    (c). A string of 0's and 1's of length n is primitive if it is not the concatenation of several smaller identical strings. Let f(n) denote the number of primitive strings of order n.

    For example 001001001 and 1001100110011001 are not primitive while 110011 and 10110 are primitive. If n is prime, then f(n) = 2n-2.
    Express f(n) as a summation involving the number-theoretic Möbius function m(n).

  2. (a). State and Prove Hall's Theorem on Sets of Distinct Representatives.
    (b). State the König-Egeváry Theorem on 0-1 Matrices.
    (c). Derive the König-Egeváry Theorem from Hall's Theorem.
    (d). State Dilworth's Theorem.
    (e). State the Erdös-Szekeres Theorem.
    (f). Derive the Erdös-Szekeres Theorem from Dilworth's Theorem.

  3. Consider a coloring of the six faces of a cube using a set of six distinct colors.
    (a). Suppose that each of the colors is used exactly once. Use Burnside's Theorem to determine how many distinct (with respect to all symmetries of the cube) colorings there are.
    (b). Suppose that the color red is used exactly 3 times, and there are no restrictions on the use of the other five colors. How many such colorings are there?

  4. (a). Show that the Ramsey number rk(3,3,3...3) £ [ek!]+1.
    (b). If n>[ek!], then show that every coloring of {1,2,...,n} with k colors contains three integers x, y, and z all having the same color and such that x+ y = z.

  5. (a). Find the ordinary generating function for the Harmonic numbers .
    (b). Show that the Bell Numbers Bn satisfy the recurrence .

    (c). Show that the exponential generating function of the Bn's is .

  6. (a). Prove that LYM posets are strongly Sperner.
    (b). Prove that symmetric chain orders are strongly Sperner.
    (c). Let P denote some projective plane of finite order n. Let S denote the set of points of P. Form a poset PP on certain subsets of S by: Rank 0 is just the null set itself, rank 1 has elements {x} where x ranges over all the points in P, rank 2 has elements L where L ranges over all the lines in P, and rank 3 is just S itself. The ordering in PP is just inclusion, e.g. if x is a point and L is a line, then {x} £ L iff L contains x.
    Prove PP is LYM.
    Is it a symmetric chain order?

    (d). It can be shown that a finite "modular geometric lattice" L is a poset which can be expressed as a direct product L = L1xL2xL3...xLr. where each Li is a chain of size 2 or a lattice of subspaces Ln(q) or a poset PP as above. Use this fact to prove that such L is LYM.
    Is such L in general a symmetric chain order?


Send Email to sumner@math.sc.edu