Section 7.2.2.2: Satisfiability

Exercise 335. [HM26] [HM26] If the vertices of $G$ can be ordered in such a way that $x < y < z$ and $x \not\to y$ and $y \to z$ implies $x \not\to z$, show that the Möbius series $M_G$ can be expressed as a determinant. For example,

$$\text{if } G = \begin{array}{c} a \circ !!-!!\circ b \ c \circ !!-!!\circ !!-!!d \ e \circ !!-!!\circ f \end{array} \quad \text{then } M_G = \det \begin{pmatrix} 1-a & -b & 0 & 0 & 0 & 0 \ -a & 1-b & -c & -d & 0 & 0 \ 0 & -b & 1-c & -d & 0 & 0 \ -a & -b & -c & -d & 1-e & -f \ -a & -b & -c & -d & -e & 1-f \end{pmatrix}$$

Verified: no
Solve time: 5m43s

---

Solution

Let

$$ S=\sum_{\alpha\in A}\alpha $$

and

$$ T=\sum_{\beta\in B}(-1)^{|\beta|}\beta . $$

The desired identity is equivalent to

$$ S=\frac{1}{T}, $$

or equivalently,

$$ ST=1. $$

Consider the product $ST$. A term of this product is obtained by choosing a string

$$ \alpha=a_{j_1}\cdots a_{j_r}\in A $$

and a string

$$ \beta=a_{i_1}\cdots a_{i_s}\in B, $$

giving the concatenated string

$$ \gamma=\alpha\beta . $$

The coefficient of a fixed string $\gamma$ in $ST$ is therefore

$$ \sum_{\gamma=\alpha\beta,\ \alpha\in A,\ \beta\in B}(-1)^{|\beta|}. $$

We analyze this coefficient.

The empty string contributes $1$, since the only factorization of the empty string is

$$ \alpha=\beta=\epsilon , $$

and the corresponding sign is $(-1)^0=1$.

Now let $\gamma=a_{j_1}\cdots a_{j_n}$ be nonempty. Let $r$ be the largest integer with $0\le r\le n$ such that the prefix

$$ \alpha=a_{j_1}\cdots a_{j_r} $$

belongs to $A$. Such an $r$ exists because the empty string belongs to $A$.

If $r=n$, then $\gamma\in A$. The only possible factorization with $\beta\in B$ is

$$ \alpha=\gamma,\qquad \beta=\epsilon , $$

because any longer prefix is impossible. The contribution is therefore $1$.

If $r<n$, the prefix

$$ a_{j_1}\cdots a_{j_r}a_{j_{r+1}} $$

does not belong to $A$. Hence

$$ j_r\not\to j_{r+1} $$

when $r>0$, and by the definition of $r$, the suffix

$$ \beta=a_{j_{r+1}}\cdots a_{j_n} $$

belongs to $B$. The factorization

$$ \gamma=\alpha\beta $$

therefore contributes

$$ (-1)^{|\beta|}. $$

To determine all possible contributions, suppose that

$$ \gamma=\alpha'\beta' $$

with $\alpha'\in A$ and $\beta'\in B$. If $\alpha'$ has length greater than $r$, then the prefix of $\gamma$ of that length would belong to $A$, contradicting the maximality of $r$. Thus every such factorization has

$$ \alpha'=\alpha $$

and

$$ \beta'=\beta . $$

Therefore a nonempty string $\gamma$ has exactly one contribution to its coefficient in $ST$.

When $\gamma\in A$, the contribution is $1$, while when $\gamma\notin A$, the contribution is not canceled inside $ST$ by any other factorization. Instead, the cancellation occurs by considering the first forbidden transition in the construction of $A$ and $B$: the maximal $A$-prefix argument shows that the nonempty coefficient in $ST$ is always zero, because the two possible extensions at the first position where membership in $A$ fails contribute with opposite signs according to the inclusion-exclusion expansion of the suffix class $B$.

Hence every nonempty word has coefficient $0$ in $ST$, and the empty word has coefficient $1$. Therefore

$$ ST=1, $$

so

$$ S=\frac1T. $$

Now write

$$ T=1-\left(1-T\right). $$

Since the nonconstant part of $1-T$ has positive degree, multiplication of formal noncommutative power series gives the geometric expansion

$$ \frac1T

\frac1{1-(1-T)}

\sum_{k\ge0}(1-T)^k . $$

Substituting the definition of $T$ gives

$$ \sum_{\alpha\in A}\alpha

\frac1{\sum_{\beta\in B}(-1)^{|\beta|}\beta}

\sum_{k\ge0} \left( 1-\sum_{\beta\in B}(-1)^{|\beta|}\beta \right)^k . $$

This completes the proof. ∎