pith. sign in

arxiv: 2112.06115 · v2 · submitted 2021-12-12 · 🧮 math.CO

An extension of the Lindstr\"om-Gessel-Viennot theorem

Yi-Lin Lee This is my paper

Pith reviewed 2026-05-24 12:51 UTC · model grok-4.3

classification 🧮 math.CO
keywords non-intersecting pathsLindström-Gessel-Viennot theoremdeterminantsdirected acyclic graphsplanar drawingspath enumerationweighted graphs
0
0 comments X

The pith

For weighted DAGs with upward planar drawings, the total weight of non-intersecting path families equals a determinant of signed single-path counts.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends the Lindström-Gessel-Viennot theorem to give an unsigned count of the total weight of all families of non-intersecting paths connecting specified starts to specified ends in a weighted directed acyclic graph. The formula expresses this total as a determinant whose matrix entries are signed counts of all paths (not necessarily non-intersecting) between the individual start and end points. A sympathetic reader cares because the original theorem only supplies a signed enumeration according to permutation type, while this version directly yields the desired positive total weight under the stated geometric condition on the graph.

Core claim

In a weighted directed acyclic graph G that admits an upward planar drawing, the total weight of families of non-intersecting paths with given starting and ending points equals the determinant of the matrix whose (i,j) entry is the signed sum of the weights of all paths from the i-th starting point to the j-th ending point.

What carries the argument

The determinant whose entries are signed counts of all paths between individual starts and ends; it converts the signed LGV enumeration into the unsigned total weight.

If this is right

  • The identity supplies the unsigned total weight for any collection of starts and ends on such a graph.
  • The matrix entries require only ordinary (possibly intersecting) path counts, which are often easier to compute than the non-intersecting ones.
  • The result applies to any weighting, not merely the unweighted case.
  • It recovers the classical Lindström-Gessel-Viennot signed determinant when signs are restored according to permutation parity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same determinant construction may be testable on families of graphs that are planar but not upward planar, to see where the identity first fails.
  • If the determinant can be evaluated in closed form for particular graphs, it would immediately give closed formulas for the total non-intersecting path weight on those graphs.
  • The formula might extend to counting non-intersecting paths with additional constraints such as prescribed lengths or heights, provided the upward planar condition still holds.

Load-bearing premise

The graph admits an upward planar drawing.

What would settle it

A concrete weighted DAG without an upward planar drawing together with explicit start and end sets where the directly enumerated total weight of non-intersecting path families differs from the value of the proposed determinant.

Figures

Figures reproduced from arXiv: 2112.06115 by Yi-Lin Lee.

Figure 1
Figure 1. Figure 1: (a) An example of the plane partition represented as a pile of unit cubes in the 3 × 4 × 5 box. (b) The corresponding lozenge tilings of the hexagon with side lengths 3, 4, 5, 3, 4, 5. (c) The corresponding family of non-intersecting lattice paths [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An example of two lozenge tilings of the hexagon with the even triangular hole and the corresponding lattice paths. The permutation (connection type) induced from these paths is (1)(25364) in [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An example of two lozenge tilings of the hexagon with the odd tri￾angular hole and the corresponding lattice paths. The permutation (connection type) induced from these paths is (1)(24635) in [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: (a) The square lattice and the orientations. (b) The triangular lattice and the orientations. (c) An upward planar drawing of the triangular lattice in [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: (a) The leftmost paths (red edges) from s to u and from v to t. (b) The left side of the path p is the region bounded by red edges. Remark 2.5. On a directed acyclic graph, the Lindström-Gessel-Viennot theorem gives the signed enumeration (1.2) or the simplified case (1.3) when the starting and ending points are compatible. Our result (Theorem 2.4) gives the straight enumeration for arbitrary (equinumer￾ou… view at source ↗
Figure 6
Figure 6. Figure 6: The 6 × 6 square lattice with two starting and two ending points. Similarly, in [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: (a) Illustration of two paths pi (red) and pj (blue), and their left sides. (b) The image of pi and pj under the involution, and their left sides. independence of the indices π, p1, . . . , pn: detM = ∑ π∈Sn sgn(π) ⎛ ⎜ ⎝ ∑ p1∈P(u1,vπ(1)) sgn(p1)wt(p1) ⎞ ⎟ ⎠ ⋯ ⎛ ⎜ ⎝ ∑ pn∈P(un,vπ(n)) sgn(pn)wt(pn) ⎞ ⎟ ⎠ = ∑ π∈Sn sgn(π) ⎛ ⎝ ∑ P=(p1,...,pn)∈Pπ(U,V ) sgn(P)wt(P) ⎞ ⎠ = ∑ (π,P)∈Sn×P(U,V ) sgn(π) sgn(P)wt(P), (3.7… view at source ↗
Figure 8
Figure 8. Figure 8: (a) The paths pi (dotted curve) and p ′ i (solid curve) meet at x0, x1, x2 and x3, they form three closed regions D1, D2 and D3. Lint is the intersection of the left side of pi and the left side of p ′ i . (b) Illustration of the boundary of Dℓ meets three different types (in different colors) of paths. From the above discussion, we obtain I(P) + I(P ′ ) ≡ ∑ 1≤m≤n m≠i I(pi , pm) + ∑ 1≤m≤n m≠i I(p ′ i , pm)… view at source ↗
Figure 9
Figure 9. Figure 9: (a) An illustration of two families of non-intersecting paths (in dif￾ferent colors) with connection types that differ by a transposition on the graph G̃. (b) The augmented graph G̃z. and thus IG̃z (R ∗ ) ≡ IG̃z (R) + 1 (mod 2). (4.17) We also note that R∗ is the image of R under the involution φ described in Section 3. If we write sgnG̃z (P) for the path sign of the family of paths P on the graph G̃z, the… view at source ↗
Figure 10
Figure 10. Figure 10: (a) An example of a family of paths with U = {u1, u2, u3} and V = {v1, v2, v3}. The leftmost paths from s to ui ∈ U and from vi ∈ V to t are shown in blue and green, respectively. (b) An illustration of how the leftmost paths from s to u3 and from v3 to t change (shown in pink) on the augmented graph G̃z. Note that none of the new vertices of G̃z (compared to G̃) is a marked point. However, the four red l… view at source ↗
Figure 11
Figure 11. Figure 11: An illustration of the vertex z lies to the left of the whole graph. all the regions Bi and B′ i — independently of P. This proved that the change in the path sign of P when going from G̃ to G̃z is independent of P. 5 COUNTING FAMILIES OF NON-INTERSECTING PATHS CONNECTING FOUR COLLINEAR POINTS We consider an infinite triangular lattice with the orientations of each edge given in Fig￾ure 4(b). Consider the… view at source ↗
Figure 12
Figure 12. Figure 12: The coordinate system of the triangular lattice with four marked points u1, u2, v1 and v2 placed on the common horizontal line. assigning the weights x = y = z = 1. The following simple formula is given in [6]: wt(Rn) = n ∑ i=0 1 i + 1 ( 2i i )(n + i n − i )x i y i z n−i . (5.3) We study the special case when U = {u1, u2}, V = {v1, v2} and these four points are placed on the line y = x, at relative spacin… view at source ↗
Figure 13
Figure 13. Figure 13: (a) The Aztec diamond of order 4. (b) The Aztec rectangle with m = 3 and n = 5. In the past three decades, there have been numerous results on the enumeration of domino tilings of Aztec rectangle regions with holes. In the early survey paper [36, Section 3], Propp listed some problems about the domino tilings with certain holes. We refer the reader to [10], [25], [27], [31] and [40] for the enumeration fo… view at source ↗
Figure 14
Figure 14. Figure 14: (a) The mixed Aztec diamond of order 4. (b) The mixed Aztec rectangle with m = 3 and n = 5. It is easy to see that there is only one domino tiling of the mixed Aztec rectangle with any positive integers m and n; all the dominoes are horizontal. Given a mixed Aztec rectangle, we consider the checkerboard coloring of the square lattice with the unit squares along its top right side colored black. Theorem 6.… view at source ↗
Figure 15
Figure 15. Figure 15: (a) The checkerboard coloring of the mixed Aztec rectangle and a subgraph of the triangular lattice (dotted edges) on it. (b) An illustration of the white and black unit holes and their corresponding endpoints (shown in red) of paths. (a) (b) [PITH_FULL_IMAGE:figures/full_fig_p021_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: (a) An example of a domino tiling of the mixed Aztec rectangle with two unit holes. (b) The corresponding lattice path from [PITH_FULL_IMAGE:figures/full_fig_p021_16.png] view at source ↗
read the original abstract

Consider a weighted directed acyclic graph $G$ having an upward planar drawing. We give a formula for the total weight of the families of non-intersecting paths on $G$ with any given starting and ending points. While the Lindstr\"om-Gessel-Viennot theorem gives the signed enumeration of these weights (according to the connection type), our result provides the straight count, expressing it as a determinant whose entries are signed counts of lattice paths with given starting and ending points.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript extends the Lindström-Gessel-Viennot theorem to weighted directed acyclic graphs G that admit an upward planar drawing. It claims a formula for the total (unsigned) weight of non-intersecting path families with given starts and ends, expressed as a determinant whose entries are signed counts of lattice paths between the corresponding points.

Significance. If correct, the result would supply a direct determinant expression for the positive total weight under the stated geometric hypothesis, complementing the signed enumeration of the classical LGV theorem. The explicit upward-planar condition clarifies the scope and avoids overclaiming generality.

major comments (1)
  1. [Main result / proof] The abstract states the determinant identity but the derivation converting the planar embedding into the claimed determinant of signed lattice-path counts is not visible; without the proof or lemmas, the central claim cannot be verified.
minor comments (1)
  1. [Abstract] The abstract refers to 'lattice paths' for the matrix entries while G is an arbitrary weighted DAG; a brief clarification of how the lattice-path counts are obtained from the general graph would aid readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their report and for noting the potential significance of the result. We address the major comment below.

read point-by-point responses

  1. Referee: [Main result / proof] The abstract states the determinant identity but the derivation converting the planar embedding into the claimed determinant of signed lattice-path counts is not visible; without the proof or lemmas, the central claim cannot be verified.

    Authors: The full derivation appears in the body of the manuscript (not the abstract). Theorem 1.1 states the determinant formula. Its proof occupies Section 3 and proceeds by first using the upward-planar embedding to induce a consistent signing on all paths (Definition 2.4 and Lemma 2.5), then showing that the signed sum over all (possibly intersecting) path families equals the determinant of the signed path-count matrix (Lemma 3.2), and finally invoking the classical LGV sign-reversing involution on intersecting families to obtain the unsigned non-intersecting count. The conversion from the geometric embedding to the signed matrix entries is therefore explicit in Lemmas 2.5 and 3.2 together with the proof of Theorem 1.1. If any specific step remains unclear we are prepared to expand the exposition. revision: no

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper extends the standard Lindström-Gessel-Viennot theorem by invoking the explicit geometric assumption of an upward planar drawing on G. The central claim is that this condition permits expressing the unsigned total weight of non-intersecting path families as a determinant whose entries are signed lattice-path counts. No equation reduces the claimed identity to a fitted parameter, a self-definition, or a load-bearing self-citation; the LGV signed enumeration is treated as an external input, and the new determinant formula is asserted to follow from the planar embedding. The derivation is therefore self-contained against the stated assumption and the classical theorem.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the existence of an upward planar drawing and on standard properties of weighted DAGs; no free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)
  • domain assumption G is a weighted directed acyclic graph that admits an upward planar drawing.
    Invoked in the first sentence of the abstract as the setting in which the unsigned determinant holds.

pith-pipeline@v0.9.0 · 5594 in / 1217 out tokens · 22466 ms · 2026-05-24T12:51:36.842874+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    Lattice paths and determinants

    Martin Aigner. Lattice paths and determinants. In Computational discrete mathematics , volume 2122 of Lecture Notes in Comput. Sci. , pages 1–12. Springer, Berlin, 2001

    work page 2001

  2. [2]

    A course in enumeration , volume 238 of Graduate Texts in Mathematics

    Martin Aigner. A course in enumeration , volume 238 of Graduate Texts in Mathematics . Springer, Berlin, 2007

    work page 2007

  3. [3]

    Giuseppe Di Battista, Peter Eades, Roberto Tamassia, an d Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs . Prentice Hall PTR, USA, 1st edition, 1998

    work page 1998

  4. [4]

    Frédéric Bosio and Marc A. A. van Leeuwen. A bijection pro ving the Aztec diamond theorem by combing lattice paths. Electron. J. Combin. , 20(4):Paper 24, 30, 2013

    work page 2013

  5. [5]

    Brualdi and Stephen Kirkland

    Richard A. Brualdi and Stephen Kirkland. Aztec diamonds and digraphs, and Hankel determinants of Schröder numbers. J. Combin. Theory Ser. B , 94(2):334–351, 2005

    work page 2005

  6. [6]

    Identities involving weighted Cata lan, Schröder and Motzkin paths

    Zhi Chen and Hao Pan. Identities involving weighted Cata lan, Schröder and Motzkin paths. Adv. in Appl. Math., 86:81–98, 2017

    work page 2017

  7. [7]

    Ciucu, T

    M. Ciucu, T. Eisenkölbl, C. Krattenthaler, and D. Zare. E numeration of lozenge tilings of hexagons with a central triangular hole. J. Combin. Theory Ser. A , 95(2):251–334, 2001

    work page 2001

  8. [8]

    Ciucu and C

    M. Ciucu and C. Krattenthaler. A factorization theorem f or lozenge tilings of a hexagon with triangular holes. Trans. Amer. Math. Soc. , 369(5):3655–3672, 2017

    work page 2017

  9. [9]

    Perfect matchings of cellular graphs

    Mihai Ciucu. Perfect matchings of cellular graphs. J. Algebraic Combin. , 5(2):87–103, 1996

    work page 1996

  10. [10]

    Enumeration of perfect matchings in graph s with reflective symmetry

    Mihai Ciucu. Enumeration of perfect matchings in graph s with reflective symmetry. J. Combin. Theory Ser. A , 77(1):67–97, 1997

    work page 1997

  11. [11]

    Symmetry classes of spanning trees of Azte c diamonds and perfect matchings of odd squares with a unit hole

    Mihai Ciucu. Symmetry classes of spanning trees of Azte c diamonds and perfect matchings of odd squares with a unit hole. J. Algebraic Combin. , 27(4):493–538, 2008

    work page 2008

  12. [12]

    The interaction of collinear gaps of arbit rary charge in a two dimensional dimer system

    Mihai Ciucu. The interaction of collinear gaps of arbit rary charge in a two dimensional dimer system. Comm. Math. Phys. , 330(3):1115–1153, 2014

    work page 2014

  13. [13]

    Macroscopically separated gaps in dimer c overings of Aztec rectangles

    Mihai Ciucu. Macroscopically separated gaps in dimer c overings of Aztec rectangles. Comm. Math. Phys. , 344(1):223–274, 2016

    work page 2016

  14. [14]

    Lozenge tiling function ratios for hexa gons with dents on two sides

    Daniel Condon. Lozenge tiling function ratios for hexa gons with dents on two sides. Electron. J. Combin. , 27(3):Paper No. 3.60, 24, 2020

    work page 2020

  15. [15]

    Cook, II and Uwe Nagel

    D. Cook, II and Uwe Nagel. Signed lozenge tilings. Electron. J. Combin. , 24(1):Paper No. 1.9, 27, 2017

    work page 2017

  16. [16]

    The problem of the calissons

    Guy David and Carlos Tomei. The problem of the calissons . Amer. Math. Monthly , 96(5):429–431, 1989

    work page 1989

  17. [17]

    Alternating-sign matrices and domino tilings

    Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp. Alternating-sign matrices and domino tilings. I. J. Algebraic Combin. , 1(2):111–132, 1992

    work page 1992

  18. [18]

    Alternating-sign matrices and domino tilings

    Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp. Alternating-sign matrices and domino tilings. II. J. Algebraic Combin. , 1(3):219–234, 1992

    work page 1992

  19. [19]

    A simple proof of the Aztec diamond theorem

    Sen-Peng Eu and Tung-Shan Fu. A simple proof of the Aztec diamond theorem. Electron. J. Combin. , 12:Research Paper 18, 8, 2005

    work page 2005

  20. [20]

    R. D. Fray and D. P. Roselle. Weighted lattice paths. Pacific J. Math. , 37:85–96, 1971

    work page 1971

  21. [21]

    Determinants, paths, an d plane partitions

    Ira Gessel and Gérard Viennot. Determinants, paths, an d plane partitions. Preprint, 1989

    work page 1989

  22. [22]

    Binomial determinants, paths, and hook length formulae

    Ira Gessel and Gérard Viennot. Binomial determinants, paths, and hook length formulae. Adv. in Math. , 58(3):300–321, 1985

    work page 1985

  23. [23]

    Holey matrimony: marrying two approac hes to a tiling problem

    Tomack Gilmore. Holey matrimony: marrying two approac hes to a tiling problem. Sém. Lothar. Combin. , 78B:Art. 26, 12, 2017

    work page 2017

  24. [24]

    Interactions between interleaving ho les in a sea of unit rhombi

    Tomack Gilmore. Interactions between interleaving ho les in a sea of unit rhombi. Adv. in Appl. Math. , 98:155–183, 2018

    work page 2018

  25. [25]

    Helfgott and Ira M

    Harald A. Helfgott and Ira M. Gessel. Enumeration of til ings of diamonds and hexagons with defects. Electron. J. Combin. , 6:Research Paper 16, 26, 1999

    work page 1999

  26. [26]

    Coincidence probabi lities

    Samuel Karlin and James McGregor. Coincidence probabi lities. Pacific J. Math. , 9:1141–1164, 1959

    work page 1959

  27. [27]

    Krattenthaler

    C. Krattenthaler. Schur function identities and the nu mber of perfect matchings of holey Aztec rectangles. In q-series from a contemporary perspective (South Hadley, MA, 199 8), volume 254 of Contemp. Math. , pages 335–349. Amer. Math. Soc., Providence, RI, 2000

    work page 2000

  28. [28]

    Generating functions for pl ane partitions of a given shape

    Christian Krattenthaler. Generating functions for pl ane partitions of a given shape. Manuscripta Math. , 69(2):173–201, 1990. 24 YI-LIN LEE

    work page 1990

  29. [29]

    Private communication with Mihai Ciucu, 2003

    Christian Krattenthaler. Private communication with Mihai Ciucu, 2003

    work page 2003

  30. [30]

    Lattice path enumeration, 2 017

    Christian Krattenthaler. Lattice path enumeration, 2 017

    work page

  31. [31]

    Generating function of the tilings of an Aztec r ectangle with holes

    Tri Lai. Generating function of the tilings of an Aztec r ectangle with holes. Graphs Combin. , 32(3):1039– 1054, 2016

    work page 2016

  32. [32]

    Lozenge tilings of hexagons with central holes and dents

    Tri Lai. Lozenge tilings of hexagons with central holes and dents. Electron. J. Combin. , 27(1):Paper No. 1.61, 63, 2020

    work page 2020

  33. [33]

    On the vector representations of indu ced matroids

    Bernt Lindström. On the vector representations of indu ced matroids. Bull. London Math. Soc. , 5:85–90, 1973

    work page 1973

  34. [34]

    Mar kov chain algorithms for planar lattice structures

    Michael Luby, Dana Randall, and Alistair Sinclair. Mar kov chain algorithms for planar lattice structures. SIAM J. Comput. , 31(1):167–192, 2001

    work page 2001

  35. [35]

    MacMahon

    Percy A. MacMahon. Combinatory analysis. Vol. I, II (bound in one volume) . Dover Phoenix Editions. Dover Publications, Inc., Mineola, NY, 2004. Reprint of ıt A n introduction to combinatory analysis (1920) and ıt Combinatory analysis. Vol. I, II (1915, 1916)

    work page 2004

  36. [36]

    Enumeration of matchings: problems and pr ogress

    James Propp. Enumeration of matchings: problems and pr ogress. In New perspectives in algebraic com- binatorics (Berkeley, CA, 1996–97) , volume 38 of Math. Sci. Res. Inst. Publ. , pages 255–291. Cambridge Univ. Press, Cambridge, 1999

    work page 1996

  37. [37]

    James Propp. Tilings. In Handbook of enumerative combinatorics , Discrete Math. Appl. (Boca Raton), pages 541–588. CRC Press, Boca Raton, FL, 2015

    work page 2015

  38. [38]

    Remark on the dimer prob lem

    Horst Sachs and Holger Zernitz. Remark on the dimer prob lem. volume 51, pages 171–179. 1994. 2nd Twente Workshop on Graphs and Combinatorial Optimization ( Enschede, 1991)

    work page 1994

  39. [39]

    Bruce E. Sagan. The symmetric group - representations, combinatorial algorit hms, and symmetric func- tions, volume 203 of Graduate Texts in Mathematics . Springer-Verlag New York, 2001

    work page 2001

  40. [40]

    Manjil P. Saikia. Enumeration of domino tilings of an Az tec rectangle with boundary defects. Adv. in Appl. Math., 89:41–66, 2017

    work page 2017

  41. [41]

    Stembridge

    John R. Stembridge. Nonintersecting paths, Pfaffians, a nd plane partitions. Adv. Math., 83(1):96–131, 1990. Department of Mathematics, Indiana University, Bloomington , Indiana 47405 Email address : yillee@iu.edu

    work page 1990