1. (a). State and prove (any proof) Hall's Theorem on the existence of an SDR.
   
   (b). Show that every Latin Rectangle (k < n) can be extended to an Latin Square.
   
   (c). Show that for any n>1, there are at most n-1 mutually orthogonal Latin squares of order n.
   
   (d). Show that if n is a prime power, then there exists a set of n - 1 mutually orthogonal Latin squares.

2. For fixed n, let , denote the maximum size of an intersecting family F of k-subsets of [n] (which means that |A|=k for all A F and that for all A,B F. )
   Determine f(k) with proof. What famous theorem is this?

3. . Define the Ramsey numbers r(n,m) and prove that they exist.
   
   (b). Let X be a set with n elements, and k a positive integer. Suppose that we arbitrarily k-color all of the non-empty subsets of X. Show that if n is large enough, then there must exist two disjoint, non-empty subsets A, B of X such that all of A, B, and have the same color.
   
   (c). Let n > 2 be an integer. Show that there exists an integer T(n), such that every tournament on T(n) vertices has a transitive subtournament on n vertices.

4. (a). State the Kruskal-Katona Theorem.
   (b). Construct a family F of 4-subsets, (i.e. A  F |A| = 4.) such that |F| = 21, and the number of 3-subsets in the shadow of F is as small as possible.
   (c). Prove that the k-cascade representation of an integer m,
   
         
   
      is unique for all m.

5. Suppose that two sequences {a_n} and {b_n} are related by:
                  .
   
   Then the Binomial Inversion theorem allows you to express in terms of the . Give this expression and prove it is correct. State any other inversion theorems that you use in the process.
   
   

6. For the array below, how many different ways are there to color the squares using the colors red, blue and green? Two colorings are considered distinct if neither can be obtained from the other by a rotation of the square or any flip about either diagonal or the center row or column (Hint: there are eight such symmetries).
   
            
   
   
   (a). Determine the permutation group of rotations and the corresponding cycle index.
   
   (b). Answer the question above using Burnside's Theorem. Show enough detail to make it clear that it is Burnside's result that you are using.
   
   (c). Using Polya's Theorem, determine the number of such colorings that use the color red exactly twice.
   

Send Email to sumner@math.sc.edu