Sink-independence conjecture for recurrent-configuration class sums

Let G=(V,E)G=(V,E)) be a strongly connected digraph and let ss be a vertex of GG. Write G\s+G_{\backslash s^{+}} for the digraph obtained by removing all outgoing arcs of ss, so that ss is a global sink. Fix an order v1v2vn1v_1\prec v_2\prec\cdots\prec v_{n-1} on the vertices distinct from ss, where n=Vn=|V|, and define riZn1r_i\in\mathbb{Z}^{n-1} by ri,j=degG(vi,vj)r_{i,j}=\deg_G(v_i,v_j) for iji\ne j and ri,i=degG+(vi)r_{i,i}=\deg_G^+(v_i). Set βi=degG(s,vi)\beta_i=\deg_G(s,v_i), let C\mathcal{C} be the recurrent configurations of G\s+G_{\backslash s^{+}}, and define c1c2c_1\sim c_2 when c1c2c_1-c_2 lies in the subgroup r1,r2,,rn1,β\langle r_1,r_2,\ldots,r_{n-1},\beta\rangle of (Zn1,+)(\mathbb{Z}^{n-1},+). For BC/ ⁣B\in\mathcal{C}/\!\sim, let

\textbf{\texttt{\sum}}\,_{G,s}(B)=\max\left\{\deg_G^+(s)+\sum_{v\ne s}c(v):c\in B\right\}.

Sink-independence conjecture. The sequence \left(\textbf{\texttt{\sum}}\,_{G,s}(B)\right)_{B\in\mathcal{C}/\sim} is independent of the choice of ss, up to a permutation of its entries. If GG is Eulerian, then βr1,,rn1\beta\in\langle r_1,\ldots,r_{n-1}\rangle, so the equivalence relation simplifies accordingly. If true, this would generalize the specialization TG(1,y)T_G(1,y) of the Tutte polynomial from undirected graphs to strongly connected digraphs.

Sources & referencesView supporting material

Primary source

Kévin Perrot and Trung Van Pham, “Chip-firing game and partial Tutte polynomial for Eulerian digraphs”, arXiv:1306.0294 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.