Jump to content

Talk:Lindström–Gessel–Viennot lemma

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Proof corrected

[edit]

When editing the proof of the LGV lemma, please keep the following two subtleties in mind:

  • The trick is not available over an arbitrary commutative ring. Cancelling addends is the way to go here (I wouldn't go into further details on the Wikipedia, but if necessary this can be deduced from first principles -- e.g., introduce a total order on and split the sum into the addends with and those with ).
  • I don't know a correct way of constructing the involution by picking the lexicographically smallest pair such that the paths and intersect. The solution to Exercise 13 in Mark Wildon's lecture notes on symmetric functions ( http://www.ma.rhul.ac.uk/~uvah099/Maths/Sym/SymFuncs2020.pdf ) shows how this gives a non-involution for `n` = 3 (independently of which intersection of and we choose).

The proof requires carefulness indeed, and both of the errors above appear in multiple textbooks. Let's make the Wikipedia better than that. -- Darij (talk) 11:28, 7 June 2021 (UTC)[reply]