Combinatorics

From MGSA
Jump to: navigation, search
  • State and prove Ramsey's Theorem, Hall's Theorem, Speiner's Theorem, Erdős-Ko-Rado Theorem, and the Erdős lower bound on Ramsey. (Karp)
  • State Lovas local theorem and Alan's Theorem. (Karp)
  • What is R1(n)? (Karp)
  • When is the Speiner bound tight? (Karp)
  • What is the net work flow problem? (Sinclair)
  • What is an algorithm to solve the problem? How do we know it terminates and what is a bound on the running time? (Sinclair)
  • What is an algorithm with a better bound? (Sinclair)
  • How can we use the algorithm to find a minimum cut? (Sinclair)
  • What is a randomized algorithm for finding a minimal cut? (Sinclair)
  • What is a bound on the error probability? (Sinclair)
  • What does this tell us about how many minimal cuts there can be in a 1-graph? (Sinclair)
  • What is an Eulerian poset? What is graded? What is a rank funciton? What is the length of a chain? What is μ of an interval? Why is it called Eulerian? (Sinclair)
  • Consider monotonic paths from (0,0) to (n,n) consisting of unit steps either + (1,0) or + (0,1). \alpha\ge\gamma if α is never below γ. Define a hill to be a + (0,1) step followed by a + (1,0) step. Define a valley to be a + (1,0) step followed by a + (0,1) step. Given \alpha\ge\beta, define hills of α and valleys of β as good points. Define valleys of α and hills of β as bad points. Show the number of good points is always greater than the number of bad points. (Sinclair)
  • Talk about the Incidence Algebra on a poset. (Klass)
    • If we are to implement the Mobius inversion on the poset, do we need the functions in the Incidence Algebra to take values in a field? Does a ring suffice? (Bergman)
    • When is a function in the Incidence Algebra invertible? Prove it. (Bergman)
  • Talk about the Mobius function for the product of two posets. Use it to describe the Mobius function on Bn, the Boolean poset of size n. (Klass)
  • Prove that a finite meet-semilattice with 1 is a lattice. (Bergman)
  • Is an infinite meet-semilattice with 1 necessarily a lattice? If not, find a counterexample. (Bergman)
  • Prove that in a finite poset with a unique maximal element, that element is 1; find a counterexample in the infinite case. (Bergman)
  • Consider the matroid of the hyperplane arrangement of the root system Bn. Draw this for n = 2, and compute the characteristic polynomial. Is this a graphical matroid? Derive the characteristic polynomial for general n. How many regions does the hyperplane arrangement have? (Ardila (SFSU))
  • State the finite field method for the characteristic polynomial of a hyperplane arrangement. Sketch a proof. (Ardila)
  • Define Cohen-Macaulay posets. Show that the lattice of flats of a matroid is Cohen-Macaulay. What is the relationship between Cohen-Macaulay posets and Cohen-Macaulay rings? (Sturmfels)
  • What is the Lagrange inversion formula? (Serganova)
    • How do you use this formula? (Serganova)
    • What is the proof? (Sturmfels)
  • What is a Schur polynomial? (Serganova)
    • How do you show that it is symmetric? (Serganova)
    • What is the definition of the Schur polynomial using determinants? (Serganova)
    • Why is the Schur polynomial important? Ans: inner products. (Serganova)
    • Can you use Schur polynomials in computational biology? (Sturmfels)

This page was originally derived from this TeX file.

Retrieved from "http://www.ocf.berkeley.edu/~mgsa/wiki/Combinatorics"
Personal tools