The multipartite orientation conjecture for the multiplicity of $-1$

Proof for every orientation, with the exact 2-adic valuation of the first nonzero coefficient.

Let $G=K_{s_1,\ldots,s_h}$, let $D$ be an arbitrary orientation, and put

$$n=\sum_i s_i,\qquad m=\lfloor n/2\rfloor,\qquad r=\#\{i:s_i\text{ is odd}\},\qquad k=\lfloor r/2\rfloor.$$

Write

$$A_D(t)=\sum_{\pi\in\mathfrak S(V)} t^{\operatorname{des}_D(\pi)}.$$

Partition each ordering into $m$ consecutive unordered two-vertex blocks, followed by a final singleton when $n$ is odd. For an ordered block configuration $P$, let $e(P)$ count blocks whose vertices lie in different multipartite parts, and let $b_D(P)$ count descents on edges between distinct blocks. Summing over the two internal orders of every block gives the exact identity

$$A_D(t) =\sum_P t^{b_D(P)}2^{m-e(P)}(1+t)^{e(P)}. \tag{1}$$

Indeed, an internal nonedge contributes $2$, while an internal edge contributes $1+t$.

Every odd-sized part must provide an unpaired vertex unless it contains the final singleton. Consequently $e(P)\ge k$, and hence $(1+t)^k\mid A_D(t)$. Equality $e(P)=k$ holds precisely when every even part is paired internally and every odd part contributes one mixed-block vertex, except that for odd $n$ one odd part instead contributes the final singleton.

Set $c_k=[z^k]A_D(-1+z)$. Formula (1) gives

$$c_k =2^{m-k} \sum_{e(P)=k}(-1)^{b_D(P)}. \tag{2}$$

In a minimal configuration, two distinct mixed blocks use disjoint multipartite parts. For any two blocks $B,C$, their number of connecting edges is

$$e_G(B,C) =4-\sum_i|B\cap V_i|\,|C\cap V_i|,$$

which is even: if either block is homogeneous, every nonzero summand is even; if both are mixed, their parts are disjoint. Exchanging adjacent blocks therefore changes $b_D(P)$ by an even integer. Thus all $m!$ orderings of a fixed unordered minimal pairing $M$ have the same sign, and

$$c_k =2^{m-k}m! \sum_{M\in\mathcal M_{\min}}\epsilon_D(M), \qquad \epsilon_D(M)\in\{-1,1\}. \tag{3}$$

The number of unordered minimal pairings is

$$|\mathcal M_{\min}| = \begin{cases} (r-1)!! \displaystyle\prod_{s_i\ {\rm even}}(s_i-1)!! \displaystyle\prod_{s_i\ {\rm odd}}s_i!!, & n\ {\rm even},\\[2mm] r!! \displaystyle\prod_{s_i\ {\rm even}}(s_i-1)!! \displaystyle\prod_{s_i\ {\rm odd}}s_i!!, & n\ {\rm odd}, \end{cases}$$

with $(-1)!!=1$. Every factor is odd. Therefore

$$\sum_{M\in\mathcal M_{\min}}\epsilon_D(M) \equiv|\mathcal M_{\min}| \equiv1\pmod2.$$

In particular $c_k\ne0$, and (3) proves the stronger conclusions

$$\boxed{ \operatorname{ord}_{t=-1}A_D(t) =\left\lfloor\frac r2\right\rfloor, \qquad v_2\!\left([z^k]A_D(-1+z)\right) =m-k+v_2(m!). }$$

Both hold for every orientation, all part sizes, and all boundary cases $r=0,1$. The first equality is precisely the conjecture.

Source: Celano, Sieger, and Spiro, Eulerian polynomials for digraphs, Combinatorial Theory 5 (2025), article 15, Conjecture 6.4, https://doi.org/10.5070/C65165026 ; https://arxiv.org/abs/2309.07240 .