Homework for Week 3

Part 1

  1. Don't forget the problems from Week 2, Part 2!
  2. (An expansion of the third problem from Week 2, Part 2)
    1. Define a group action of the Weyl group of each type A, B, C, D on binary strings of length N with exactly k ones. (What should N be for each type?) Use our discussion in class on Friday as a model.
    2. Consider the cases when N=4 (type A), N=5 (type B), N=4 (type C), N=6 (type D). How many different orbits are there for each possible k? (Explain.) What is the size of the stabilizer for each distinct orbit?
    3. What can you say about general N?
  3. Suppose you have an even number 2n. Let Xn be the set of all ways to partition the numbers {1,2,...,2n} into half. For instance X4 consists of the three partitions {1,2}{3,4}, {1,3}{2,4}, {1,4}{2,3}.
    1. Define a group action of S2n on Xn. What are the distinct orbits? What is the size of the stabilizer of each distinct orbit?
    2. Define a group action of the Weyl group of type C on Xn. What are the distinct orbits? What is the size of the stabilizer of each distinct orbit?

Part 2

    Note: you can find proofs of all of these statements online or in combinatorics textbooks. If you use other resources to identify conditions or start the proof, try to prove the rest by yourself.
  1. Recall that an Euler circuit (or path) is a cycle (or path) that uses every edge in a graph exactly once. Can you give a test for whether a graph G has an Euler circuit? or an Euler path? Can you prove this test? (Note: the free app Glow Puzzle lets you find Euler paths in all sorts of graphs; it might be useful in generating conjectures.)
  2. Recall that a tree is a connected graph with no cycles. Prove that a tree with n vertices has exactly n-1 edges. Bonus: prove that a connected graph with n vertices and n-1 edges is a tree. (In other words, this condition is an equivalent definition of a tree!)
  3. Prove that every tree has at least two leaves. (A leaf is a vertex with just one edge attached to it.) What kind of graph has exactly two leaves? What is the maximum number of leaves, and can you find a graph with that many leaves?