# Formal Group Laws and Chromatic Symmetric Functions of Hypergraphs

Jair Taylor

► To cite this version:

Jair Taylor. Formal Group Laws and Chromatic Symmetric Functions of Hypergraphs. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.655-666, 10.46298/dmtcs.2499 . hal-01337785

HAL Id: hal-01337785

https://hal.science/hal-01337785

Submitted on 27 Jun 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Formal Group Laws and Chromatic Symmetric Functions of Hypergraphs

Jair Taylor†

University of Washington

**Abstract.** If $f(x)$ is an invertible power series we may form the symmetric function

$$f(f^{-1}(x_1) + f^{-1}(x_2) + \dots),$$

which is called a *formal group law*. We give a number of examples of power series $f(x)$ that are ordinary generating functions for combinatorial objects with a recursive structure, each of which is associated with a certain hypergraph. In each case, we show that the corresponding formal group law is the sum of the chromatic symmetric functions of these hypergraphs by finding a combinatorial interpretation for $f^{-1}(x)$. We conjecture that the chromatic symmetric functions arising in this way are Schur-positive.

**Résumé.** Si $f(x)$ est une série entière inversible, nous pouvons former la fonction symétrique

$$f(f^{-1}(x_1) + f^{-1}(x_2) + \dots),$$

que nous appelons une *loi de groupe formel*. Nous donnons plusieurs exemples de séries entières $f(x)$ qui sont séries génératrices ordinaires pour des objets combinatoires avec une structure récursive, chacune desquelles est associée à un certain hypergraphe. Dans chaque cas, nous donnons une interprétation combinatoire à $f^{-1}(x)$, ce qui nous permet de montrer que la loi de groupe formel correspondante est la somme des fonctions symétriques chromatiques de ces hypergraphes. Nous conjecturons que les fonctions symétriques chromatiques apparaissant de cette manière sont Schur-positives.

**Keywords:** Formal group laws, hypergraph colorings, chromatic symmetric functions

## 1 Introduction

*Formal group laws* were first defined by S. Bochner in 1946 [2], who called them *formal Lie groups*. Specifically, a one-dimensional formal group law over a ring $R$ is a formal power series $F(x, y) \in R[[x, y]]$ so that

$$\bullet F(x, 0) = x, F(0, y) = y$$

$$\bullet F(F(x, y), z) = F(x, F(y, z)).$$

<footnote>†Supported in part by grant DMS-1101017 from the National Science Foundation.</footnote>
We will always take formal group laws to be one-dimensional and commutative, so that $F(x, y) = F(y, x)$, and we will take $R = \mathbb{Z}$. In this case, it is well known [9, IV.5] that formal group laws are exactly the formal power series of the form

$$F(x, y) = f(f^{-1}(x) + f^{-1}(y))$$

for some $f(x) \in \mathbb{Z}[[x]]$ with $f(0) = 0$ and $f'(0) = 1$, where $f^{-1}(x)$ is the compositional inverse of $f(x)$. More generally, we consider the power series $F$ in infinitely many variables $x_1, x_2, \dots$ given by

$$F(x_1, x_2, \dots) = f(f^{-1}(x_1) + f^{-1}(x_2) + \dots) \quad (1)$$

and from this point on we define formal group laws to be power series of the form (1).

The purpose of this paper is to develop a technique for showing that the formal group law $F$ has nonnegative coefficients when $f(x)$ is an ordinary generating function for certain combinatorial objects. In each case we will use the language of hypergraphs colorings to give a combinatorial interpretation for the associated formal group law. A hypergraph (sometimes called a set system) is a pair $H = (V, E)$ where $E$ is a family of subsets of $V$ which we call the *edges* of $H$. We do not require that every edge $e$ has the same number of elements, but we will always assume that $V$ is finite and that no edge of $H$ contains another edge. In the case that each edge of $V$ has two elements, we say that $H$ is an (ordinary) graph. We say that $H$ is *connected* if $V$ is not a disjoint union $V = V_1 \cup V_2$ of nonempty sets $V_1, V_2$ so that each edge $e \in E$ is contained in either $V_1$ or $V_2$. Every hypergraph $H$ is the disjoint union of connected hypergraphs called the *connected components* of $H$.

We say that $H$ is *linear* if $|e_1 \cap e_2| \le 1$ for every $e_1, e_2 \in E$. If there is a labeling of $V$ by the integers $[n] = \{1, 2, \dots, n\}$ so that each $e \in E$ is an interval $I = \{a, a+1, \dots, b-1, b\}$, we will say that $H$ is an *interval hypergraph*. For example, if $V = [9]$ and $E$ is the set of edges $\{1, 2, 3\}, \{3, 4\}, \{5, 6\}, \{6, 7, 8, 9\}$ then $H = (V, E)$ is a linear interval hypergraph. All of the hypergraphs $H$ appearing in our examples will be linear interval hypergraphs.

A *coloring* of $H$ is a map $\chi : V \to \mathbb{P} = \{1, 2, 3, \dots\}$. If $e$ is an edge of $H$ and $\chi$ is a coloring of $H$ so that every element of $e$ is given the same color, we say that $e$ is *monochromatic*, and we say that $\chi$ is *proper* if no edge $e \in E$ of $H$ is monochromatic. (One might expect that we would define proper colorings so that each vertex in an edge must colored differently. But as Stanley notes in [12], in that case we could replace each edge by a complete ordinary graph and nothing new would be gained by considering hypergraphs.)

Let $x_1, x_2, \dots$ be an infinite set of indeterminates. A *symmetric function* is a power series in $x_1, x_2, \dots$ that is invariant under any permutation of the variables. For example,

$$p_n = x_1^n + x_2^n + \dots$$

is a symmetric function known as the $n$-th *power sum* symmetric function.

The *chromatic symmetric function* $X_H$ of a hypergraph $H$ with vertex set $V$ is the power series

$$X_H(x_1, x_2, \dots) = \sum_{\chi} \prod_{v \in V} x_{\chi(v)}$$

with the sum taken over all proper colorings $\chi$ of $H$. Thus $X_H$ is indeed a symmetric function, since permuting the colors of a proper coloring gives another proper coloring. The chromatic symmetric function $X_G$ of an ordinary graph $G$ was introduced by Stanley [11], who later generalized the notion to hypergraphs [12].
It will be useful in what follows to write the chromatic symmetric function $X_H$ in terms of the power sum symmetric functions. The following theorem is a straightforward application of the inclusion-exclusion principle. A proof was for ordinary graphs given by Stanley [11, Theorem 2.5], who later extended it to hypergraphs [12, Theorem 3.2].

**Theorem 1.** Let $H = (V, E)$ be a hypergraph. Then

$$X_H = \sum_{S \subseteq E} (-1)^{|S|} p_{k_1} p_{k_2} \cdots p_{k_n}$$

where $k_1, \dots, k_n$ are the sizes of the connected components of the hypergraph $H_S = (V, S)$ that has only the edges $e \in S$.

In Section 2, we will give a number of examples of power series $f(x)$ so that the associated formal group law $F$ is a sum of chromatic symmetric functions, and hence has nonnegative coefficients. Specifically, we will describe sequences $(A_n)$ of sets $A_n$ of combinatorial objects $T$ on the $n$ nodes $1, 2, \dots, n$ that have a recursive structure in the sense that one object may be inserted into any vertex of another object in a nice fashion, and certain “sub-objects” can be contracted to a point. Letting $a_n = |A_n|$, we form the generating function $f(x) = \sum_{n=1}^{\infty} a_n x^n$ and show that the corresponding formal group law has nonnegative coefficients. For example, we may let $a_n$ be the sequence of Catalan numbers, Motzkin numbers, or the factorial numbers, corresponding to the sets $A_n$ of binary trees, Motzkin paths and permutations, respectively. In each case, we will show that

$$f(f^{-1}(x_1) + f^{-1}(x_2) + \cdots) = \sum_{n=1}^{\infty} \sum_{T \in A_n} X_{H_T} \qquad (2)$$

where $H_T = (V, E_T)$ is a particular hypergraph determined by the structure of the object $T \in A_n$, where $V = [n]$. The edges of $T$ will be made up of the “sub-objects” of $T$ that are minimal in the sense that they do not contain any other sub-objects except for singletons, and these edges will always be intervals in $[n]$. Furthermore, each $H_T$ will be linear, so that $H_T$ is a linear interval hypergraph.

While it is possible to give an axiomatic framework for proving equations of the form (2), we feel that for this extended abstract it is more useful to give individual examples. In each case, we will prove (2) by first giving a combinatorial interpretation for $f^{-1}(x)$. Letting $C_n$ be the set of $T \in A_n$ so that the hypergraph $H_T$ is connected, we will find that

$$f^{-1}(x) = \sum_{n=1}^{\infty} \sum_{T \in C_n} (-1)^{|E_T|} x^n. \qquad (3)$$

Then we use (3) to prove (2) using the combinatorial interpretation of a composition of generating functions along with Theorem 1.

# 2 Examples

## 2.1 Lattice paths

Let $L$ be a finite subset of $\mathbb{Z}$. Define a $L$-admissible path to be a map $P : [n] \to \mathbb{N}$ so that $P(1) = P(n) = 0$ and $P(i+1) - P(i) \in L$ for $i = 1, \dots, n-1$. Let $A_{n,L}$ be the set of $L$-admissible paths $P : [n] \to \mathbb{N}$,
let $a_{n,L} = |A_{n,L}|$ and define the generating function $f_L(x) = \sum_{n=1}^{\infty} a_{n,L} x^n$. If $L = \{-1, 1\}$ then an $L$-admissible path is called a *Dyck path*. Then $a_{n,L} = 0$ if $n$ is even while $a_{2n+1} = C_n$, the $n$-th Catalan number, and

$$f_L(x) = \frac{1 - \sqrt{1 - 4x^2}}{2x}.$$

If $L = \{-1, 0, 1\}$ then $L$-admissible paths are called *Motzkin paths* and $a_{n,L} = M_{n+1}$ where $M_n$ is the $n$-th Motzkin number, with

$$f_L(x) = \frac{1 - x - \sqrt{1 - 2x - 3x^2}}{2x}.$$

There is an obvious way to insert one path into the vertex of another path. Formally, if $P$ is an $L$-admissible path on $[n]$, $j \in [n]$, and $P'$ is an $L$-admissible path on $[m]$, define $P(j \leftarrow P')$ to be the path on $[n+m-1]$ given by

$$P(j \leftarrow P')(i) = \begin{cases} P(i) & \text{if } i < j \\ P'(i - j + 1) + P(j) & \text{if } j \le i < j + m \\ P(i - m + 1) & \text{if } i \ge j + m. \end{cases}$$

It is clear that $P(j \leftarrow P')$ is an $L$-admissible path.

For any path $P : [n] \to \mathbb{N}$, define an *excursion* of $P$ to be an interval $I = \{a, a+1, \dots, b\} \subseteq [n]$ so that $P(a) = P(b)$ and $P(i) \ge P(a)$ for $i \in I$. Thus restricting an $L$-admissible path $P$ to an excursion $I$ and translating produces another $L$-admissible path $Q \in A_{m,L}$ where $m = |I|$, so that excursions can be thought of as sub-objects of $P$. If $P \in A_{n,L}$ and $P' \in A_{m,l}$ then we see that $\{j, j+1, \dots, j+m-1\}$ is an excursion of $P(j \leftarrow P')$.

We call a excursion $I$ of $P$ minimal if $|I| > 1$ and the only excursions of $P$ properly contained in $I$ are singletons. For each path $P$ on $[n]$ we associate the hypergraph $H_P = (V, E_P)$ where $V = [n]$ and $E_P$ is the set of minimal excursions of $P$. Fig. 1 gives an example of a path $P$ and its associated hypergraph. Note that if $I_1, I_2$ are excursions of $P$ with $I_1 \cap I_2 \neq \emptyset$, then $I_1 \cap I_2$ and $I_1 \cup I_2$ are also excursions. In particular, if $I_1, I_2$ are minimal excursions and $I_1 \cap I_2 \neq \emptyset$, then $I_1 \cap I_2$ must be a singleton. It follows that $H_P$ is a linear interval hypergraph.

Now we can give a combinatorial interpretation of the formal group law associated with $f_L(x)$: it is the sum of the chromatic symmetric functions $X_{H_P}$ for $L$-admissible paths $P$.

**Theorem 2.** Let $L \subseteq \mathbb{Z}$ be finite. Then

$$f_L(f_L^{-1}(x_1) + f_L^{-1}(x_2) + \dots) = \sum_{n=1}^{\infty} \sum_{P \in A_{n,L}} X_{H_P}.$$

Note that in the case $L = \{0\}$, the only allowed path on $[n]$ is the constant path $P = 0$, so

$$f_L(x) = \frac{1}{1-x} - 1, f_L^{-1}(x) = \frac{x}{1+x}.$$

The minimal excursions of the constant path on $[n]$ are the intervals $\{i, i+1\}$, and so

$$f_L(f_L^{-1}(x_1) + f_L^{-1}(x_2) + \dots) = \frac{1}{1 - \frac{x_1}{1+x_1} - \frac{x_2}{1+x_2} - \dots} - 1 = \sum_{n=1}^{\infty} X_{G_n} \quad (4)$$
where $G_n$ is the ordinary graph with vertices $1, 2, \dots, n$ and edges $\{i, i+1\}$ for $i = 1, \dots, n-1$, sometimes called the $n$-vertex path (not to be confused with an $L$-admissible path $P$). A proper coloring of $G_n$ is equivalent to a word $c_1 \cdots c_n$ with $c_i \in \mathbb{P}$ and $c_i \neq c_{i+1}$ for $i = 1, \dots, n-1$. Such words are called *Smirnov* or *Carlitz* words, and if we assign a weight $x_{c_1} \cdots x_{c_n}$ to the word $c_1 \cdots c_n$ we see that (4) is the sum of the weights of all nonempty Smirnov words. This result can be found in Goulden and Jackson [5, 2.4.16], and was first found by MacMahon [7].

To prove Theorem 2, we will first find a combinatorial interpretation for $f^{-1}(x)$.

**Lemma 3.** Let $L \subseteq \mathbb{Z}$ be finite and let $C_{n,L}$ be the set of $L$-admissible paths $P \in A_{n,L}$ so that $H_P$ is a connected hypergraph. Let

$$g_L(x) = \sum_{n=1}^{\infty} \sum_{P \in C_{n,L}} (-1)^{|E_P|} x^n.$$

Then $g_L(x) = f_L^{-1}(x)$.

*Proof.* Recall the usual combinatorial interpretation of the composition of ordinary generating functions. If $f(x) = \sum_{n=1}^{\infty} a_n x^n$ and $g(x) = \sum_{n=1}^{\infty} b_n x^n$ then

$$ \begin{aligned} f(g(x)) &= \sum_{k=1}^{\infty} a_k \left( \sum_{n=1}^{\infty} b_n x^n \right)^k \\ &= \sum_{n=1}^{\infty} x^n \sum_{n_1 + \cdots + n_k = n} a_k b_{n_1} \cdots b_{n_k} \end{aligned} \qquad (5) $$

where the inner sum is taken over all compositions of $n$, that is, $k$-tuples $(n_1, \dots, n_k)$ of positive integers with $n_1 + \cdots + n_k = n$, with any positive number of parts $k$.

Now suppose that $a_n = |A_n|$ where $A_n$ is the number of combinatorial structures of some type on $n$ vertices. Then we interpret (5) as saying that the coefficient of $x^n$ in $f(g(x))$ is given by taking a weighted sum indexed by partitions of $[n]$ into $k$ disjoint subintervals for some $k$, where the summand $a_k b_{n_1} \cdots b_{n_k}$ represents the weight the set of all choices of a structure $T \in A_k$ to give the interval $[k]$ where each subinterval of size $i$ in the partition is given the weight $b_i$.

Let $\Gamma_{n,L}$ be the set of tuples $(Q, Q_1, \dots, Q_k)$ for some $k \ge 1$, where $Q \in A_{k,L}$ and each $Q_i \in C_{n_i,L}$ for some $n_i \in \mathbb{P}$, with $n_1 + \dots + n_k = n$. Then the coefficient of $x^n$ in $f_L(g_L(x))$ is

$$ \sum_{(Q, Q_1, \dots, Q_k) \in \Gamma_{n,L}} (-1)^{|E_{Q_1}| + \dots + |E_{Q_k}|}. \qquad (6) $$

We will show that $f_L(g_L(x)) = x$ by showing that (6) is 1 if $n=1$ and 0 otherwise.

Given $(Q, Q_1, \dots, Q_k) \in \Gamma_{n,L}$ with $Q_i \in C_{n_i,L}$ we can form an $L$-admissible path $P \in A_{n,L}$ by inserting $Q_1$ into the first vertex of $Q$, inserting $Q_2$ into the second vertex of $Q$ (which is the $k_1+1$-th vertex of $Q(1 \leftarrow Q_1)$), etc. That is, we let

$$P = Q(1 \leftarrow Q_1)(n_1 + 1 \leftarrow Q_2) \cdots (n_1 + \dots + n_{k-1} + 1 \leftarrow Q_k).$$

Furthermore, we get a set $S \subseteq E_P$ by collecting all of the minimal edges of each $Q_i$ as they appear within $P$, so that $S$ consists of the translates $I + n_1 + \dots + n_{i-1} := \{j + n_1 + \dots + n_{i-1} : j \in I\}$ for the edges
<figure><img src="image_2.png" /><figcaption>**Fig. 1:** An L-admissible path $P \in A_{n,L}$ with its minimal excursions $I \in E_P$ circled underneath it, where $L = \{-2, -1, 0, 1, 2\}$ and $n = 20$. Below that, the edges of an arbitrary subset $S \subseteq E_P$ are circled.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>**Fig. 2:** A tuple $(Q, Q_1, \dots, Q_k) \in \Delta_{n,L}$, with $n = 20$ and $k = 8$, that is the result of applying the bijection $\rho^{-1}$ to the pair $(P, S) \in \Delta_{n,L}$ from Fig. 1. Above is the path $Q$ given by contracting each of the components of the hypergraph $H_S = ([n], S)$ to a point; below are the paths $Q_1, \dots, Q_k$ given by the individual components, with the minimal excursions $I \in E_{Q_i}$ circled.</figcaption></figure>

$I \in E_{Q_i}$, for each $i$. This gives a map $\rho : \Gamma_{n,L} \to \Delta_{n,L}$ where $\Delta_{n,L}$ is the set of pairs $(P, S)$ where $P \in A_{n,L}$ and $S \subseteq E_P$.

In fact, we can show that $\rho$ is a bijection. Given an arbitrary $P \in A_{n,L}$ and $S \subseteq E_P$, let $I_1, I_2, \dots, I_k$ be the components of the hypergraph $H_S = ([n], S)$ with edge set $S \subseteq E_P$. Since the set of excursions is closed under non-disjoint unions, each $I_i$ is an excursion of $P$, so restricting $P$ to $I_i$ and translating gives a path $Q_i \in A_{n_i,L}$ where $n_i = |I_i|$. The hypergraph $H_{Q_i}$ is connected since $I_i$ was a connected component of $P$, so $Q_i \in C_{n_i,L}$. Finally, we define $Q$ by contracting each of the excursions $I_i$ to a point. This defines the map $\rho^{-1}$; an example of its use is given in Fig. 2.

Applying the bijection $\rho$, (6) becomes

$$ \sum_{P \in A_{n,L}} \sum_{S \subseteq E_P} (-1)^{|S|}. $$

The inner sum

$$ \sum_{S \subseteq E_P} (-1)^{|S|} \qquad (7) $$

is 0 unless $E_P$ is empty, which only occurs if $P$ is the path with one vertex, in which case (7) is 1. Thus $f_L(g_L(x)) = x$. $\square$

*Proof of Theorem 2.* Again we use the combinatorial interpretation of a composition of ordinary generating functions. Let $f(x) = \sum_{n=1}^{\infty} a_n x^n$ and $g(x) = \sum_{n=1}^{\infty} b_n x^n$, and let $p_n = x_1^n + x_2^n + \dots$ be the nth
power sum symmetric function. Then

$$ 
\begin{aligned}
f(g(x_1) + g(x_2) + \dots) &= \sum_{k=1}^{\infty} a_k \left( \sum_{n=1}^{\infty} b_n x_1^n + \sum_{n=1}^{\infty} b_n x_2^n + \dots \right)^k \\
&= \sum_{k=1}^{\infty} a_k \left( \sum_{n=1}^{\infty} b_n p_n \right)^k \\
&= \sum_{k=1}^{\infty} \sum_{n_1+\dots+n_k=n} a_k b_{n_1} \dots b_{n_k} p_{n_1} \dots p_{n_k}.
\end{aligned} 
\quad (8) $$

In the case $f(x) = f_L(x)$ and $g(x) = f_L^{-1}(x)$, we can use Lemma 3 to rewrite (8) as

$$ \sum_{n=1}^{\infty} \sum_{(Q, Q_1, \dots, Q_k) \in \Gamma_{n,L}} (-1)^{|E_{Q_1}| + \dots + |E_{Q_k}|} p_{n_1} \dots p_{n_k} \quad (9) $$

where $n_i$ is the number of vertices in the $i$th path $Q_i$. Applying the bijection $\rho$ defined in the proof of 3, we see that (9) is

$$ \sum_{n=1}^{\infty} \sum_{P \in A_n} \sum_{S \subseteq E_P} (-1)^{|S|} p_{n_1} \cdots p_{n_k} \quad (10) $$

where $n_1, \dots, n_k$ are the sizes of the connected components of the hypergraph $H_S = (V, S)$. Using Theorem 1, (10) becomes

$$ \sum_{n=1}^{\infty} \sum_{P \in A_n} X_{H_P}. $$

□

The fundamental tool in the proof of Theorem 2 is the ability to insert one path into any vertex of another path while preserving the edges, as well as the ability to contract edges (and connected unions of edges) to a point. This leads to the bijection $\rho$ defined in the proof of 3, which allows us to use inclusion-exclusion to find a combinatorial interpretation for the compositional inverse $f_L^{-1}(x)$, which in turn allows us to find a combinatorial interpretation for the formal group law using the expansion of chromatic symmetric functions into power sums (Theorem 1). In what follows we will give more examples of this technique, but the details will be similar and the proofs will generally be omitted.

## 2.2 Plane trees with a fixed number of leaves

A *plane tree* (also called *embedded tree* is a rooted tree so that each node is equipped with an ordering of its children. A *leaf* of a tree $T$ is a node that has no children. Let $A_n$ be the set of plane trees with $n$ leaves labeled 1, 2, ..., $n$ left-to-right, with all other nodes unlabeled and with no node having exactly one child. (If nodes were allowed to have a single child, then each $A_n$ would be infinite.)

There is an obvious way to insert one tree into any leaf of another that will allow us to replicate the proof of Theorem 2. If $T \in A_n$, $i$ is a leaf of $T$, and $T' \in A_m$, we form the tree $T(i \leftarrow T')$ by replacing $i$
<figure><img src="image_4.png" /><figcaption>Fig. 3: A plane tree T with the edges $I \in E_T$ circled below.</figcaption></figure>

with the root of $T'$. We let a subtree of $T$ be a set of nodes $T'$ so that $T'$ is itself a tree that is a “down set”, meaning that if $v$ is a node of $T'$ and $u$ is descended from $v$ in $T$, then $u \in T'$. Then let $H_T = (V, E_T)$ where $E_T$ is the set of subsets $I$ of leaves that form a complete set of siblings — all elements of $I$ are children of a single node $v$, and every child of $v$ is a leaf and is in $I$. Fig. 3 is an example of a tree $T$ with its edge set $E_T$. Note that $H_T$ has a very simple structure as a hypergraph, since the edges of $H_T$ are always disjoint. In particular, $H_T$ is a linear interval hypergraph.

Let $t_2, t_3, \dots$ be indeterminates. Define the weight $w(T)$ of a plane tree to be $t_2^{k_2} t_3^{k_3} \dots$ where $k_i$ is the number of nodes in $T$ that have exactly $i$ children; thus if $T$ is the tree in Fig. 3 then $w(T) = t_2 t_3^2$. Then let $f(x)$ be the generating function

$$f(x) = \sum_{n=1}^{\infty} x^n \sum_{T \in A_n} w(T).$$

If we set $t_2 = 1$ and $t_i = 0$ for $i > 2$ in the coefficient of $x^n$ in $f(x)$ we get the number of binary trees with $n$ leaves, the Catalan number $C_{n-1}$.

We have the following facts, whose proofs are similar to the proofs of Lemma 3 and Theorem 2.

**Theorem 4 ([6, 8]).** Let $C_n$ be the set of trees $T \in A_n$ so that the associated hypergraph $H_T$ is connected. Then

$$f^{-1}(x) = \sum_{n=1}^{\infty} x^n \sum_{T \in C_n} w(T)(-1)^{|E_T|}. \qquad (11)$$

Furthermore,

$$f(f^{-1}(x_1) + f^{-1}(x_2) + \dots) = \sum_{n=1}^{\infty} \sum_{T \in A_n} w(T) X_{H_T}. \qquad (12)$$

Note that $H_T$ is connected only when all the leaves of $T$ are children of the root. In this case $E_T$ consists of only one edge, which is the entire set of leaves. So $C_n$ consists of this single tree $T$ with weight $w(T) = t_n$ for each $n$, and by (11) we see

$$f^{-1}(x) = x - t_2 x^2 - t_3 x^3 - \dots. \qquad (13)$$

Equation (13) can also be seen as a corollary of a more general theorem due to Parker [8] giving a combinatorial interpretation of the compositional inverses of generating functions that count plane trees with
certain restrictions. Equation (12) is due to Lenart [6, Theorem 3.2], although there it is given in a signed form.

We can also prove (12) directly, if we first define $f(x)$ so that $f^{-1}(x) = x - t_2x^2 - t_3x^3 - \dots$ and let

$$F = \sum_{n=1}^{\infty} \sum_{T \in A_n} w(T) X_{H_T}.$$

Then we see that $F$ obeys the functional equation

$$F = x_1 + x_2 + \dots + t_2(F^2 - x_1^2 - x_2^2 - \dots) + t_3(F^3 - x_1^3 - x_2^3 - \dots) + \dots \quad (14)$$

since a properly colored tree $T$ consists either of a single vertex of any color, or a root whose descendants consist of some number $k \ge 2$ of subtrees $T_1, \dots, T_k$ which are properly colored, where we do not allow the case where $T_1, \dots, T_k$ are single vertices all colored the same. Then rearranging (12), we see

$$F - t_2 F^2 - t_3 F^3 - \dots = (x_1 - t_2 x_1^2 - t_3 x_1^3 - \dots) + (x_2 - t_2 x_2^2 - t_3 x_2^3 - \dots) + \dots \\ f^{-1}(F) = f^{-1}(x_1) + f^{-1}(x_2) + \dots$$

as desired.

## 2.3 Permutations

Let $S_n$ be the set of permutations $\sigma : [n] \to [n]$, and let

$$f(x) = \sum_{n=1}^{\infty} |S_n| x^n = \sum_{n=1}^{\infty} n! x^n.$$

The power series $f(x)$ is nowhere convergent, but as a formal power series it still has a well-defined inverse $f^{-1}(x)$. As in our previous examples, there is a simple way to insert one permutation into another. In this case, it is most easily described in terms of permutation matrices. Let $M_\sigma$ be the permutation matrix of $\sigma \in S_n$, given by the entries $a_{ij} = 1$ if $\sigma(j) = i$, with $a_{ij} = 0$ otherwise. Then if $\sigma \in S_m$, $j \in [m]$, and $\sigma' \in S_k$, we define the permutation $\sigma(j \leftarrow \sigma')$ by letting $M_{\sigma(j \leftarrow \sigma')}$ be the matrix given by inserting $M_{\sigma'}$ as a $k \times k$ block into the entry $(j, \sigma(j))$ of $M_\sigma$. For example, if $\sigma = 41523$, $j = 4$, and $\sigma' = 213$ then

$$M_{\sigma} = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & \boxed{1} & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix}, \quad M_{\sigma'} = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad M_{\sigma(4 \leftarrow \sigma')} = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \boxed{0} & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & \boxed{0} & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{bmatrix}$$

and so $\sigma(4 \leftarrow \sigma') = 6173245$. From here we see how to define the associated hypergraph $H_\sigma$ for a permutation $\sigma \in S_n$. We let $\hat{E}_\sigma$ be the set of intervals $I \subseteq [n]$ so that $\sigma$ maps $I$ to another interval
$J \subseteq [n]$; thus $\{(j, \sigma(j)) : j \in I\}$ is the set of entries with 1's in an $|I| \times |I|$ block within $M_\sigma$ which is a permutation matrix in itself. Then we define $E_\sigma$ to be the minimal non-singleton elements of $\tilde{E}_\sigma$. For example, if $\sigma = 659421387$ then $E_\sigma$ consists of the intervals $\{1, 2\}, \{4, 5, 6, 7\}, \{8, 9\}$ since these map to the intervals $\{5, 6\}, \{1, 2, 3, 4\}$, and $\{7, 8\}$ respectively and they are minimal with respect to this property.

We then have the following facts, whose proofs are similar to the previous examples.

**Theorem 5.** Let $C_n$ be the set of permutations $\sigma$ of $S_n$ so that $H_\sigma$ is connected. We have

$$f^{-1}(x) = \sum_{n=1}^{\infty} \sum_{\sigma \in C_n} (-1)^{|E_\sigma|} x^n \qquad (15)$$

and

$$f(f^{-1}(x_1) + f^{-1}(x_2) + \cdots) = \sum_{n=1}^{\infty} \sum_{\sigma \in S_n} X_{H_\sigma}.$$

A permutation $\sigma \in S_n$ is called simple if $E_\sigma = \{[n]\}$, so that $\sigma$ does not map any proper non-singleton subinterval of $[n]$ to another subinterval of $[n]$. For example, the permutations 12 and 24153 are simple, but 253641 is not simple because it maps the interval $\{2, 3, 4, 5\}$ to the interval $\{3, 4, 5, 6\}$. We can also state this in terms of the permutation matrix $M_\sigma$: if $\sigma$ is simple then $M_\sigma$ has no $k \times k$ block that is itself a permutation matrix, unless $k = 1$ or $n$.

Clearly if $\sigma \in S_n$ is simple then $H_\sigma$ is connected and so $\sigma \in C_n$. In fact, we will show that all but two of the permutations in $C_n$ are simple for $n > 2$. It is not hard to show that if $I_1, I_2$ are distinct elements of $E_\sigma$ with $I_1 \cap I_2 \neq \emptyset$ then $|I_1| = |I_2| = 2$. It follows that if $H_\sigma$ is a connected hypergraph that is not simple then $\sigma$ is either the identity $123 \cdots n$ or the reverse permutation $n \cdots 321$. In the latter two cases we have $E_\sigma = \{\{1, 2\}, \{2, 3\}, \dots, \{n-1, n\}\}$, so $|E_\sigma| = n-1$. Then using (15) we find that

$$f^{-1}(x) = x - 2x^2 + \sum_{n=3}^{\infty} (2(-1)^{n-1} - s_n) x^n \qquad (16)$$

where $s_n$ is the number of simple permutations in $S_n$, which is the sequence $1, 2, 0, 2, 6, 46, 338, \dots$ (Sequence A059372 in [10].) Equation (16) was found by Albert and Atkinson [1].

## 2.4 Other examples

There are a number of other power series $f(x)$ for which

$$f(f^{-1}(x_1) + f^{-1}(x_2) + \cdots)$$

can be shown to have nonnegative coefficients using these methods. For example, instead of taking $A_n$ to be plane trees with any number of nodes but with leaves labeled 1, 2, ..., $n$, we can take plane trees with each of its nodes labeled 1, 2, ..., $n$. Let

$$f(x) = \sum_{n=1}^{\infty} \sum_{T \in A_n} w(T) x^n$$
where $w(T) = t_1^{k_1} t_2^{k_2} \cdots$ where $k_i$ is the number of nodes of $T$ with exactly $i$ children. It is shown within the proof of the Lagrange inversion formula in [13, Theorem 5.4.2] that

$$ \frac{x}{f^{-1}(x)} = 1 + t_1 x + t_2 x^2 + \cdots \qquad (17) $$

and (17) can also be used to define $f(x)$. It is possible to prove that the corresponding formal group law has nonnegative coefficients using the technique we have described.

For simplicity of exposition we have only discussed the case where $f(x)$ is an ordinary generating function, but it is also possible to extend the methods to exponential generating functions. For example, we may take $f(x)$ to be the exponential generating function for labeled trees or labeled graphs. However, the hypergraphs that arise in the exponential case are not necessarily linear interval hypergraphs.

## 3 A conjecture

This section will assume a basic knowledge of symmetric functions as found in, e.g., [13, Chapter 7], and in particular knowledge of the Schur functions $s_\lambda$ which form an important basis of the ring of symmetric functions $\Lambda$ in infinity many variables $x_1, x_2, \dots$. If a symmetric function has positive coefficients in a basis $\{b_\lambda\}$ of $\Lambda$ we will say that it is b-positive; we will say that a hypergraph $H$ is b-positive if $X_H$ is. Based on numerical evidence, we make the following conjecture.

**Conjecture 6.** *Linear interval hypergraphs are Schur-positive.*

In particular, this conjecture would imply that all of the formal group laws discussed in 2.1, 2.2, 2.3 are Schur-positive.

In some cases we can prove Schur-positivity directly. For example, let $f(x) = x/(1-x)$. Stanley has shown [13, Exercise 7.47(k)] that (4) can be rewritten

$$ f(f^{-1}(x_1) + f^{-1}(x_2) + \cdots) = \sum_{n=1}^{\infty} X_{G_n} = \frac{\sum_{i=1}^{\infty} e_i}{1 - \sum_{i=1}^{\infty} (i-1)e_i} - 1 \qquad (18) $$

where $e_i$ is the $i$th elementary symmetric function. It follows that the formal group law $F$ corresponding to $f(x) = x/(1-x)$ is $e$-positive and hence Schur-positive, and all the paths $G_n$ are $e$-positive as well. A linear interval hypergraph that is actually an ordinary graph is a disjoint union of paths, and so must also be $e$-positive. The Schur positivity of a disjoint union of paths also follows from results of Gessel [4] and Gasharov [3], where a combinatorial interpretation of the coefficients of $X_G$ in the Schur basis is given when $G$ is the incomparability graph of a $(3+1)$-free poset.

If $H$ is the hypergraph with vertex set $[n]$ whose only edge is the whole set $[n]$ then $X_H = p_1^n - p_n$ since the only colorings of $H$ that are not proper are the ones that assign all of $H$ to a single color. It is not hard to see that $X_H$ is Schur-positive in this case, and it follows that any hypergraph with all edges disjoint is Schur-positive. Recall from Example 2.2 that if

$$ f^{-1}(x) = x - t_2 x^2 - t_3 x^3 - \cdots $$

then

$$ f(f^{-1}(x_1) + f^{-1}(x_2) + \cdots) = \sum_{T} w(T) X_{H_T} $$
with the sum taken over plane trees $T$ where $w(T)$ is a monomial in $t_2, t_3, \ldots$ and $H_T$ is a hypergraph
with all of its edges disjoint. It follows we may set $t_2, t_3, \ldots$ to be any sequence of nonnegative real
numbers and the resulting formal group law will be Schur-positive, giving the following.

**Theorem 7.** If $f(x) \in \mathbb{R}[[x]]$ so that $f^{-1}(x) = x - t_2x^2 - t_3x^3 - \cdots$, with each $t_i \ge 0$, then the corresponding formal group law is Schur-positive.

Acknowledgements

The author would like to thank Sara Billey, Ira Gessel, Yannick Van Huele, Connor Alhbach, Josh Swan-
son and the anonymous referee for their useful feedback and assistance in the creation of this paper.

References

[1] M. H. Albert, M. D. Atkinson, and M. Klazar. The enumeration of simple permutations. *J. Integer Seq.*, 6(4):Article 03.4.4, 18, 2003.

[2] S. Bochner. Formal Lie groups. *Ann. of Math*. (2), 47:192–201, 1946.

[3] Vesselin Gasharov. Incomparability graphs of (3 + 1)-free posets are s-positive. In *Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics (New Brunswick, NJ, 1994)*, volume 157, pages 193–197, 1996.

[4] Ira M. Gessel and X. G. Viennot. Determinants, paths, and plane partitions, 1989. Preprint, http://people.brandeis.edu/~gessel/homepage/papers/pp.pdf.

[5] I. Goulden and D.M. Jackson. *Combinatorial Enumeration*. John Wiley, New York, 1983.

[6] Cristian Lenart and Nigel Ray. Some applications of incidence hopf algebras to formal group theory and algebraic topology. Technical report, 1995.

[7] Percy A. MacMahon. *Combinatory analysis*. Cambridge [Eng.]: The University Press, 1915-1916.

[8] Susan Parker. *The combinatorics of functional composition and inversion*. Dissertation, Brandeis University, 1993.

[9] Joseph H. Silverman. *The arithmetic of elliptic curves*, volume 106 of *Graduate Texts in Mathematics*. Springer, Dordrecht, second edition, 2009.

[10] N. J. A. Sloane. The Online Encyclopedia of Integer Sequences, 2003.

[11] Richard P. Stanley. A symmetric function generalization of the chromatic polynomial of a graph. *Adv. Math.*, 111(1):166–194, 1995.

[12] Richard P. Stanley. Graph colorings and related symmetric functions: ideas and applications: a description of results, interesting applications, & notable open problems. *Discrete Math.*, 193(1-3):267–286, 1998. Selected papers in honor of Adriano Garsia (Taormina, 1994).

[13] Richard P. Stanley. *Enumerative combinatorics. Vol. 2*, volume 62 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge, 1999.