Monthly Archives: January 2011

Algebraic combinatorics lecture 6: RS(K), Dual RSK, and analytic definition of Schur functions

First we have an easy result Proposition 1 where is the number of SSYT of shape and type . Proof: We know that Equating coefficient of both sides, we get on LHS and on RHS. Thus we also have . … Continue reading

Posted in algebraic combinatorics, Uncategorized | Leave a comment

Algebraic combinatorics lecture 5: RSK algorithm

First we describe the Schensted algorithm, which associates to each permutation two Young tableaux of the same shape but possibly different types; it consists of bumping numbers into a greedy patience sorting procedure. In the first step we write down. … Continue reading

Posted in algebraic combinatorics, Uncategorized | Tagged , , , | Leave a comment

Algebraic combinatorics Lecture 4: patience sorting, symmetry of schur functions and Kostka numbers

Recall the definition of skew Young tableaux and their Schur functions and . When , we get the usual Schur functions .The reason we consider skew tableaux is they are related to skew characters of to be discussed later. the … Continue reading

Posted in algebraic combinatorics, Uncategorized | Tagged , , | Leave a comment

Graphical inference model: lecture 4. Max product algorithm and group testing

Max product is algorithm is closely related to the sum product algorithm, in that it uses partial marginals to compute the total marginal. But the objective is to find the mode of a distribution, i.e., . It does that by … Continue reading

Posted in Uncategorized | Tagged , , | Leave a comment

Gurvits’ inequality and proof of Van der Waerden’s conjecture

Today I went to Don Knuth’s talk on some recent spectacular progress made in the problem of computing permanents. The talk is motivated and mainly based on a recent article in the American Math Monthly called “On Leonid Gurvits’s proof … Continue reading

Posted in Uncategorized | Tagged , , , | 4 Comments

Algebraic combinatorics Lecture 3

First it is useful to have the Hall inner product on , the space of all symmetric functions in infinitely many variables. It is defined by To show it’s symmetric, we check it on the basis . Then it follows … Continue reading

Posted in algebraic combinatorics, Uncategorized | Tagged , , | Leave a comment

Graphical inference model lecture 2

The indexing and bookkeeping of notations in this class have always been a nightmare to me. I try my best to state things correctly. Whenever possible I copy directly from Andrea’s notes. The moral of today’s lesson is that trees … Continue reading

Posted in Uncategorized | Tagged , , | Leave a comment