1
$\begingroup$

Gessel-Viennot's simple but powerful lemma has many striking applications, such as counting noninsecting paths , proving the Jacob-Trudi's identities, and solving the aztec diamond problem. So I wonder wether it can also be used to prove the Dodgson's condensation and Newton's indentities. Also, if you know other theorems or identities that can be solved by this lemma, please let me konw...

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

I think that Viewing determinants as nonintersecting lattice paths yields classical determinantal identities bijectively by Markus Fulmek is your friend.

Improve this answer
$\endgroup$
1
  • $\begingroup$ "Submitted on 19 Oct 2010"; that's pretty good timing! ;) $\endgroup$
    – Hans Lundmark
    Commented Nov 7, 2010 at 21:21
0
$\begingroup$

A little off-topic: Gessel-Viennot's lemma was also discovered by Karlin and McGregor (1959, "Coincidence Probabilities") and was used to construct dynamics of noncolliding systems of particles: take N identical particles evolving independently (e.g., under a one-dimensional diffusion) and impose the condition that their trajectories do not intersect. Under some conditions you will get new interesting Markov particle dynamics with determinantal formulas for the semigroup and for the dynamical correlation functions, see also Koenig arXiv:math/0403090.

Concerning the original question: Gessel-Viennot's lemma provides a powerful combinatorial formalism to produce totally positive matrices, and in the case of Toeplitz matrices any such totally positive matrix can be obtained this way. So this could possibly lead to the proof of the facts that you need.

Improve this answer
$\endgroup$
3
  • $\begingroup$ are there any online resouces on this topic? (excluding Stanley's and Sagan's books) $\endgroup$
    – zhaoliang
    Commented Nov 7, 2010 at 8:34
  • 1
    $\begingroup$ More on the history on the footnote on page 9 and 10: mat.univie.ac.at/~kratt/artikel/viciousk.html $\endgroup$
    – Martin Rubey
    Commented Nov 7, 2010 at 9:48
  • 1
    $\begingroup$ Gessel & Viennot give credit to the earlier results in their paper: "Arguments similar to the one of Lemma 5 have been used by Chaundy [3], Karlin and MacGregor [14], and Lindström [18]". The paper by Chaundy that they refer to is "The unrestricted plane partition" from 1932. $\endgroup$
    – Hans Lundmark
    Commented Nov 7, 2010 at 21:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .