18 312 Algebraic Combinatorics Lionel Levine Practice Problems for the Final The questions on the exam on Thursday May 5 will be similar to these but there will be fewer of them Explain your reasoning to receive full credit even for computational questions If a result was proved in lecture or on the problem sets you may use it without reproducing the proof PF1 Consider the poset P b 0 x1 xn y1 yn z1 zn b 1 with covering relations b 0 xi yj zk b 1 for all i j k n Find for each 1 the number of chains of length from b 0 to b 1 b b and use this information to determine P 0 1 PF2 Suppose P is a poset with b 0 and b 1 having 3 2 3 2 multichains b 0 x0 x1 x b 1 for each 1 a What is the rank of P b What is P b 0 b 1 PF3 Consider the 3 dimensional hyperplane arrangement A x y x y y z y z a Draw the Hasse diagram of the intersection lattice L of A b Find X b 1 for all X L c How many points x y z F35 belong to the union of the hyperplanes in A 1 PF4 Let L be the lattice of linear subspaces of F32 ordered by inclusion a Draw the Hasse diagram of L b Find L 0 1 c Find the number of linear maps A F32 F32 such that Av 6 v for all v F32 PF5 Let A1 An B1 Bn be sets of size 2 with A1 An B1 Bn 2n Prove that there is a permutation Sn such that A i Bi 6 for all i n PF6 Let G be a finite directed graph and let G v be the number of oriented spanning trees of G rooted at v Prove that if G is balanced indeg v outdeg v for all vertices v then G v G w for all vertices v and w PF7 Let n 1 Find the number of closed paths of length in the complete graph Kn PF8 Let G be a 3 regular undirected graph on 10 vertices whose adjacency matrix has eigenvalues 2 2 2 2 1 1 1 1 1 3 a Find the number of closed paths in G of length b How many spanning trees does G have c How many bi Eulerian tours does G have up to cyclic equivalence A biEulerian tour is a closed path using every edge twice once in each direction 2 PF9 How many sequences x1 x91 with each xk 10 have the property that x1 x91 and for every pair of distinct integers i j 10 there is exactly one k 90 such that xk xk 1 i j PF10 Let Y be the set of 3 3 matrices with entries in n For A B Y define an equivalence relation A B if B can be obtained by permuting the rows and columns of A Find the number of equivalence classes 3
View Full Document
Unlocking...