6
$\begingroup$

This is a continuation of some questions asked by Johann Cigler: Number of bounded Dyck paths with "negative length" and Number of bounded Dyck paths with negative length as Hankel determinants.

Let $\mathcal{D}(k,n)$ denote the following planar directed graph: enter image description here It has $k+1$ vertices in the leftmost column and $n+1$ vertices in the bottom row. It always has an odd number of columns, and even number of rows. Also, all edges are directed from left to right.

For $0\leq i \leq k+1$, let $C(k,i;n)$ denote the number of $i$-tuples of nonintersecting lattice paths in $\mathcal{D}(k,n)$ which connect the bottom $i$ vertices of the leftmost column to the bottom $i$ vertices of the rightmost column.

Note that these tuples of nonintersecting lattice paths could also be called $i$-fans of $(2k+1-2(i-1))$-bounded Dyck paths of semilength $n$.

There is of course a Lindström-Gessel-Viennot determinantal expression for $C(k,i;n)$.

Conjecture/Proposition: As a function of $n$, $C(k,i;n)$ satisfies a linear recurrence with constant coefficients.

The reason this should be true is via a "transfer matrix"-style argument. We can make $\mathcal{D}(k,n+1)$ from $\mathcal{D}(k,n)$ by adding two columns on the right; and if we consider $i$-tuples of nonintersecting lattice paths in $\mathcal{D}(k,n)$ that start at the bottom $i$ vertices of the leftmost column, there are finitely many patterns of sinks at which they could terminate at; and in turn there are a fixed number of ways to continue these patterns for the two additional columns.

If that is indeed so, then we can define $C(k,i;-n)$ at negative values via the recurrence.

Question: Do we have the "reciprocity" result that $C(k,i;-n)=C(k,k+1-i;n+1)$?

The resolution of the previous questions implies that this is true for $i=1$ (and it is trivially true for $i=0$).

$\endgroup$
  • $\begingroup$ You can safely drop the word "conjecture" from "Conjecture/Proposition" - its argument is valid. Furthermore, the reciprocity in question would follow from the relationship between the transfer matrices for $(k,i)$ and $(k,k+1-i)$ -- their characteristic polynomials appear to be negated reciprocals of each other. I've tested this for many small values of $k,i$. $\endgroup$ – Max Alekseyev Oct 1 at 4:53
  • $\begingroup$ I wonder what this might mean in terms of semistandard tableaux! (I can only look into it later today) $\endgroup$ – Martin Rubey Oct 1 at 6:10
  • $\begingroup$ The sequence $n \mapsto |SSYT(n\lambda,m)|$ is a polynomial in n, and thus satisfies a linear recursion. Perhaps its something like this? $\endgroup$ – Per Alexandersson Oct 1 at 6:54
  • $\begingroup$ What I meant to ask is: what does the reciprocity mean in terms of semistandard tableaux. $\endgroup$ – Martin Rubey Oct 1 at 7:01
  • 2
    $\begingroup$ If you're a fan of bounded Dyck paths, have I got some reciprocity for you! $\endgroup$ – LSpice Oct 1 at 13:46
6
$\begingroup$

Let's say we have $n+1$ sets of vertices $V_t$, and for each $0\le t\le n$ we have $|V_t|=k+1$. The subsets of $V_t$ will often be identified with subsets of $\{1,2,\dots,k+1\}$.

Given some directed graph $G$ with $k+1$ sources and $k+1$ sinks satisfying the conditions of Lindström–Gessel–Viennot, we can form a graph $\widehat{G}_n$ by gluing together $n$ copies of $G$ as follows: for all $t$, the $t$-th copy has its sources identified with $V_{t-1}$ and its sinks identified with $V_t$.

Let $A$ be the $(k+1)\times (k+1)$ matrix whose $(i,j)$ entry counts the number of paths from source $i$ to sink $j$ in $G$. Let's denote by $A_s$ the matrix of $s\times s$-minors of $A$. The Lindström–Gessel–Viennot lemma tells us that the number of non-intersecting paths connecting $s$ sinks to $s$ sources in $G$ is the appropriate entry in $A_s$. Therefore the generating function for non-intersecting s-tuples of paths in graphs $\widehat{G}_n$ is given by $$\sum_{n\geq 0} C(k,s,n)x^n=(I-xA_s)^{-1}$$ where $C(k,s,n)$ denotes the $\binom{k+1}{s}\times\binom{k+1}{s}$ matrix where each entry counts the number of nonintersecting paths connecting the appropriate subsets of sinks and sources. This is just a rephrasing of the transfer matrix argument, and we see that each entry of $C(k,s,n)$ satisfies a linear recurrence. For the negative extension we obtain the generating function $$\sum_{n\geq 1} C(k,s,-n)x^n=-(I-x^{-1}A_s)^{-1}=xA_s^{-1}(I-xA_s^{-1})^{-1}$$ therefore $\sum_{n\geq 0} C(k,s,-n)=(I-xA_s^{-1})^{-1}$. Now up to a factor of $\det A$ (which for your original graph is 1) the inverse of the s-compound matrix is the s-adjugate matrix. When you unpack what this means for our situation it says that $$C(k,s,-n)_{I,J}=(-1)^{\sigma(I)+\sigma(J)}C(k,k+1-s,n)_{J^{c}, I^{c}}$$ where $I,J$ are subsets of size $s$ that index the sources/sinks and $\sigma(I)$ is the sum of the elements in $I$. This reciprocity is true for all graphs $G$ that have $\det A=1$.

Now returning to your graph, we have another symmetry at our disposal. Choosing $I$ to be be the lowest $s$ vertices we obtain from the argument above that $C_{I,I}(k,s,-n)=C_{I^c,I^c}(k,k+1-s,n)$. We observe that there is a very easy bijection between the non-intersecting family of paths joining the lowermost $k+1-s$ sources/sinks in $\mathcal D(k,n+1)$ and the non-intersecting family of paths joining the uppermost $k+1-s$ sources/sinks in $\mathcal D(k,n)$ (erase the first and last column and flip everything upside down). This proves the statement in your question.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is very, very nice, especially the "general" growing graph case- I have certainly not seen these LGV-type reciprocity results before (although as I mentioned in a previous answer they are somewhat reminiscent of dimer covering reciprocity). $\endgroup$ – Sam Hopkins Oct 1 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.