Intuitive explanations of the Carlitz-Scoville-Vaughan theorem

Question

Crossposted from MSE:

I recently came across Ira Gessel's slides on a theorem he says should "be considered one of the fundamental theorems of enumerative combinatorics."

The Carlitz-Scoville-Vaughan Theorem: Let $A$ be an alphabet, and let $R$ be a relation on $A$, that is, a subset of $A × A = A^2 $. Let $A^{(R)}$ be the set of words $a_1 · · · a_n$ in $A^∗$ such that $a_1 R a_2 R · · · R a_n$ . Note that the empty word 1 and all words of length one are in $A^{(R)}$ . Let $\bar{R} = A^2 − R.$ Then $$\sum_{w\in A^{(\bar{R})}}w = \left(\sum_{w\in A^{({R})}}(-1)^{l(w)}w \right)^{-1}$$ Here $l(w)$ is the length of $w,$ and we are working in the ring of formal power series in noncommuting variables.

This does look like a pretty powerful theorem; it seems to yield combinatorial interpretations to several important sequences and yet I can't find anything like this in the standard enumerative combinatorics books, which suggests I'm not looking in the right places. So I have the following questions:

1. What is this theorem saying, intuitively? How could one have been led naturally to this? How would I recognize when it makes sense to apply it?
2. Where can I find other reasonably elementary expositions of this or similar results? Other than these slides and some references in a couple of PhD theses I can't seem to find it. Does it usually go by another name? What other techniques are used to prove the results that can be proved by this theorem?

Answer 1

This is more of an extended comment than an answer, but maybe you will find it helpful. I agree with Sam Hopkins that it is fruitful to think of the Carlitz–Scoville–Vaughan (CSV) theorem as a combinatorial reciprocity theorem; it is called that in Jair Taylor's 2014 Electronic Journal of Combinatorics paper, Counting Words with Laguerre Series, for example. Curiously, though, it does not seem to be mentioned in Matthias Beck and Raman Sanyal's book, Combinatorial Reciprocity Theorems, so I think there is room for someone to explain more thoroughly the connection between CSV and other combinatorial reciprocity theorems.

I first encountered CSV when working on my Ph.D. thesis. One of my main results was a combinatorial reciprocity theorem relating the directed paths in a directed graph $D$ with the directed paths in its complement $\overline D$. A corollary was a simple formula (which I called the rook reciprocity theorem) relating the rook numbers of complementary boards; decades ago, Riordan had written down an equivalent formula, but the reciprocity point of view led to a much nicer formulation. Ira Gessel was on my thesis committee, and quickly recognized that directed graphs are equivalent to relations, and he came up with a different proof—using CSV—of (a special case of) my reciprocity result. You can find Gessel's proof starting on page 35 of my Ph.D. thesis, Symmetric function generalizations of graph polynomials.

Marcelo Aguiar and his collaborators have suggested approaching combinatorial reciprocity theorems by way of Hopf algebras. The reciprocity theorem in my thesis, like many other reciprocity theorems, lives in the world of symmetric functions. It takes a combinatorially significant symmetric function, applies the involution $\omega$, and interprets the result combinatorially. The involution $\omega$ is essentially the antipode of the Hopf algebra of symmetric functions. In their paper Hopf monoids and generalized permutahedra, Marcelo Aguiar and Federico Ardila show how to derive various combinatorial reciprocity theorems using the Hopf algebra point of view. If you are not familiar with Hopf algebras, they may seem very abstract, but a lowbrow way of phrasing the main idea is that if you have some combinatorial structures that compose (the product) and decompose (the coproduct) in a "compatible" way, then chances are there will be a combinatorial reciprocity theorem (the antipode) available. But again, Aguiar and Ardila don't mention CSV. I'd be interested in seeing whether CSV can be interpreted in terms of the antipode of some Hopf algebra.