Enumeration of Graded (3 + 1)-Avoiding Posets (extended abstract)

Joel Brewster Lewis and Yan X Zhang

Massachusetts Institute of Technology

**Abstract.** The notion of (3 + 1)-avoidance appears in many places in enumerative combinatorics, but the natural goal of enumerating all (3 + 1)-avoiding posets remains open. In this paper, we enumerate graded (3 + 1)-avoiding posets. Our proof consists of a number of structural theorems followed by some generating function magic.

**Résumé.** L'idée de l'évritement de (3 + 1) apparaît dans beaucoup d'endroits dans le combinatoire énumérative, mais l'objectif naturel de le dénombrement des tous les ordres qui évitent (3 + 1) demure ouvert. Dans cet article, nous énumérons les ordres *étagés* qui évitent (3 + 1). Notre preuve est constitué de quelques théorèmes de structure, et après un peu de la magie des fonctions génératrices.

**Keywords:** posets, (3 + 1)-avoiding, generating functions

# 1 Introduction

The notion of (3 + 1)-avoiding posets pops up in different different areas of combinatorics, such as in the Stanley-Stembridge conjecture about the *e*-positivity of certain chromatic polynomials [8] and the characterization of interval semiorders [2]. They have also earned some direct scrutiny: Skandera [5] has given a characterization of (3 + 1)-avoiding posets involving the square of the antiadjacency matrix. Despite these connections, the enumeration of (3 + 1)-avoiding posets has remained elusive. This is particularly bothersome because the enumeration of posets that are both (2+2)- and (3+1)-avoiding, the interval semiorders, is well-understood: the number of unlabeled *n*-element interval semiorders is exactly the Catalan number $C_n$ [2]. Moreover, (2 + 2)-avoiding posets have been recently enumerated, as well [1].

In this paper, we consider a closely related problem and enumerate graded (3 + 1)-avoiding posets via structural theorems and generating function magic. The property of gradedness is very natural and captures a lot of the complexity of the general case while making the problem much more tractable. In the rest of this introduction, we summarize our strategy and results.

In Section 2, we offer some definitions and notation that we will use throughout the paper. Then in Section 3, we give a useful local condition that is equivalent to (3 + 1)-avoidance for graded posets.

The meat of the paper is in Section 4, where we introduce several operations that allow us to decompose strongly graded (3+1)-avoiding posets into simpler objects. First, in Section 4.1 we reduce our problem of obtaining the generating function for all graded (3 + 1)-avoiding posets to studying certain posets we will
<figure><img src="image_1.png" /><figcaption>**Fig. 1:** Three posets: the first is strongly graded, the second is weakly graded but not strongly graded, and the third is not weakly graded.</figcaption></figure>

call *trimmed* which are slightly simpler but which capture most of the information of the original posets. Then, in Section 4.2, we show that trimmed (3 + 1)-avoiding posets arise from taking the *ordinal sum* of several *layers*, each of which is a *sum-indecomposable* (3 + 1)-avoiding poset. Finally, in Section 4.3 we introduce two more operations, *gluing* and *sticking*. We show that sum-indecomposable (3 + 1)-avoiding posets arise from gluing and sticking together basic units called *quarks*, which we enumerate in Section 5.

This line of argument culminates in Section 6, in which we use the results of the preceding sections and the transfer-matrix method to enumerate all strongly graded (3 + 1)-avoiding posets. In Section 7, we mention without details a few related results, most notably the enumeration of weakly graded (3 + 1)-avoiding posets. For details, please see the complete version [4] of this paper.

## 2 Preliminaries

We assume familiarity with standard definitions and terminology associated with partially ordered sets; see, e.g., [6, Chapter 3]. We say that four elements $w, x, y, z$ in a poset $P$ are an *instance of* (3 + 1) if we have that $x < y < z$ and $w$ is incomparable to all of $x, y, z$. If $P$ contains no instance of (3 + 1), we say that $P$ *avoids* (3 + 1).

Call a poset $P$ *weakly graded* if there exists a rank function rk : $P \to \mathbb{N}$ such that if $a < b$ then rk($b$) - rk($a$) = 1 and such that the minimal occurring rank in each connected component is 0. Call a weakly graded poset *strongly graded* if all minimal elements are on the same rank and all maximal elements are on the same rank.⁽¹⁾ (Equivalently, a poset is strongly graded if all maximal chains in the poset have the same length; in this case the rank function rk may be recovered by setting rk($v$) to be the length of the longest chain whose maximal element is $v$.) Figure 1 gives examples of posets with these properties. The *height* of a weakly graded poset $P$ is the number of vertices in the longest chain in $P$.

A weakly graded poset $P$ of height $k+1$ has *vertex levels* $P(0), P(1), \dots, P(k)$, where $P(i) = \{v \in P \mid \mathrm{rk}(v) = i\}$. If $P$ is strongly graded, all the minimal elements are in $P(0)$ and all the maximal ones are in $P(k)$.

In this extended abstract, we restrict our discussion primarily to strongly graded posets.

## 3 Local Conditions

In this section, we give a concise local condition that is equivalent to (3 + 1)-avoidance for weakly graded posets.

<footnote>⁽¹⁾ We avoid the use of the unmodified word “graded” in the statement of theorems and results because of an ambiguity in the literature: some sources (e.g., [7]) use the word “graded” to mean “strongly graded,” while many others (e.g., [3]) use “graded” to mean “weakly graded.” Such is life; we hope the reader does not feel overburdened by the multiplication of adverbs.</footnote>
<figure><img src="image_2.png" /><figcaption>**Fig. 2:** The Hasse diagram for the vigilant poset at left will be displayed as the image at right: all-seeing vertices are represented as squares, other vertices as triangles.</figcaption></figure>

Given a weakly graded poset $P$, call a vertex $v \in P(i)$ *up-seeing* if every vertex in $P(i+1)$ covers $v$, and call $v$ *down-seeing* if $v$ covers every vertex in $P(i-1)$. Let $V(i)$ be the set of up-seeing vertices of rank $i$ and let $\Lambda(i)$ be the set of all down-seeing vertices of rank $i$.

**Theorem 3.1** A weakly graded poset $P$ is (3 + 1)-avoiding if and only if every vertex of $P$ is up-seeing, down-seeing, or both, and every two vertices $v, w$ such that $\mathrm{rk}(w) - \mathrm{rk}(v) \ge 2$ are comparable.

**Proof idea:** We show that any weakly graded poset with the two given properties avoids (3 + 1). The converse is slightly longer (but not more difficult) and we omit it here.

Suppose $P$ is a weakly graded poset such that every vertex is up-seeing or down-seeing and every two vertices $v, w$ such that $\mathrm{rk}(w) - \mathrm{rk}(v) \ge 2$ are comparable; we will show $P$ avoids (3 + 1). Consider any 3-chain $x < y < z$ in $P$ and any other vertex $w \in P$; we show that $w$ is comparable to at least one of $x$, $y$, $z$. By the defining properties of $P$, if $\mathrm{rk}(w) < \mathrm{rk}(z) - 1$ then $w < z$ while if $\mathrm{rk}(w) > \mathrm{rk}(x) + 1$ then $w > x$, and in either case we have our result. The only remaining case is $\mathrm{rk}(z) - 1 = \mathrm{rk}(w) = \mathrm{rk}(x) + 1$. In this case, since $w$ is either up- or down-seeing, we conclude that $w$ is comparable to at least one of $x$ and $z$. Thus, $P$ avoids (3 + 1), as desired. $\square$

One consequence of Theorem 3.1 is that in our study of graded (3 + 1)-avoiding posets we need only consider posets in which every vertex is up-seeing or down-seeing. We make heavy use of this property in the following sections, so we give it a name: we say that a weakly graded poset $P$ is *vigilant* if every vertex of $P$ is up-seeing, down-seeing, or both. For similar reasons, we refer to vertices that are both up- and down-seeing as *all-seeing*.

We introduce the following convention for representing vigilant posets: vertices that are all-seeing are represented by squares, vertices that are up-seeing are represented by downwards-pointing triangles, and vertices that are down-seeing are represented by upwards-pointing triangles. (Thus, each vertex has horizontal edges on the sides on which it is connected to all vertices.) This convention is illustrated in Figure 2.

# 4 Simplifications

In this section, we introduce four operations that allow us to count vigilant posets by working instead with simpler objects. We show that (3 + 1)-avoidance will be mostly compatible with these simplifications, reducing the problem of enumerating graded (3 + 1)-avoiding posets basically to studying vigilant posets of height 2.

## 4.1 Trimming

We call a vigilant poset $P$ *trimmed* if every rank has at most one all-seeing vertex, the all-seeing vertices are unlabeled, and the other $m$ vertices are labeled with $[m]$.
<figure><img src="image_3.png" /><figcaption>Fig. 3: A strongly graded (3 + 1)-avoiding poset and the associated trimmed poset.</figcaption></figure>

Given a strongly graded poset $P$, there is a naturally associated trimmed poset, denoted $\text{trim}(P)$, that we get by removing the all-seeing vertices from $P$, adding a single unlabeled all-seeing vertex to any vertex level from which we removed all-seeing vertices, and relabeling the other vertices so as to preserve the relative order of labels. Figure 3 provides one illustration of this operation.

**Proposition 4.1** *The strongly graded vigilant poset $P$ avoids (3 + 1) if and only if $\text{trim}(P)$ does.*

Since we lose very little information when we replace the poset $P$ by the trimmed poset $\text{trim}(P)$, Proposition 4.1 suggests that we can reduce the enumeration of labeled graded (3 + 1)-avoiding posets to the enumeration of trimmed (3 + 1)-avoiding posets. The following proposition makes this intuition precise.

**Proposition 4.2** Let $g_n$ be the number of strongly graded (3 + 1)-avoiding posets on $n$ vertices and let

$$G(x) = \sum_{n} g_n \frac{x^n}{n!}$$

be the exponential generating function for labeled strongly graded (3 + 1)-avoiding posets. Let $a_{n,r}$ be the number of trimmed (3 + 1)-avoiding posets with $r$ all-seeing vertices and $n$ other vertices and let

$$G_T(x, z) = \sum_{n,r} a_{n,r} \frac{x^n}{n!} z^r$$

be the generating function for trimmed (3 + 1)-avoiding posets, exponential in $x$ and ordinary in $z$. Then

$$G(x) = G_T(x, e^x - 1).$$

## 4.2 Ordinal Sums

Suppose we have two trimmed strongly graded posets $P_1$ and $P_2$ of heights $a$ and $b$, respectively. We can form the ordinal sum of $P_1$ and $P_2$ by letting the lowest-ranked elements in $P_2$ cover all highest-ranked elements in $P_1$ and relabeling in a way consistent with the labelings of $P_1$ and $P_2$. (Thus, there are many ways to take the ordinal sum $P_1$ and $P_2$; all the resulting posets are isomorphic up to vertex relabeling.) We call the posets $P_1$ and $P_2$ the *layers* and we denote any poset that results from this process by $P_1 \oplus_L P_2$. Observe that $P_1 \oplus_L P_2$ has height $a + b$. See for example Figure 4. In the context of vigilant posets, it is an especially nice operation because a vertex in $P_1$ or $P_2$ which is up-seeing and/or down-seeing retains that property in $P_1 \oplus_L P_2$.

Call a nonempty strongly graded trimmed poset $P$ with height $k \ge 1$ *sum-indecomposable* if $P$ there is no $i < k - 1$ for which every vertex in $P(i)$ is up-seeing (equivalently, there is no $i > 0$ for which
<figure><img src="image_4.png" /><figcaption>Fig. 4: The ordinal sum of two sum-indecomposable layers forms a new poset. (Labels are suppressed for readability.)</figcaption></figure>

every vertex in $P(i)$ is down-seeing). This word choice is motivated by the existence of a decomposition of trimmed posets into sum-indecomposables.

**Proposition 4.3** A trimmed strongly graded poset $P$ can be written uniquely as

$$P = P_1 \oplus_L P_2 \oplus_L \cdots \oplus_L P_k,$$

for a sequence $(P_1, P_2, \dots, P_k)$ of sum-indecomposable posets.

**Proposition 4.4** If a trimmed strongly graded poset $P$ decomposes into sum-indecomposables as $P = P_1 \oplus_L \cdots \oplus_L P_k$, then $P$ avoids $(3+1)$ if and only if all of the $P_i$ avoid $(3+1)$.

**Proof idea:** One direction is trivial: if any of the $P_i$ contains an instance of $(3+1)$ then certainly $P$ does as well. For the other direction, suppose that all the $P_i$ avoid $(3+1)$; we will show that $P$ also avoids $(3+1)$. It suffices to check that $P$ satisfies the local conditions in Theorem 3.1. The first condition, that every vertex is up-seeing or down-seeing or both, is satisfied by construction and by the fact that the $P_i$ have this property. Thus, we are left to check the second condition, that every vertex is comparable to all vertices two ranks above it. This requires a small amount of straightforward casework depending on whether and how the chosen vertices straddle two of the $P_i$. □

Propositions 4.3 and 4.4 simplify the problem of counting strongly graded (3 + 1)-avoiding posets: it now suffices to count sum-indecomposable posets and then take their ordinal sums. As we will see in Theorem 6.4, this is a simple task with generating functions. Thus, we now turn our attention to enumerating sum-indecomposable (3 + 1)-avoiding posets.

## 4.3 Sticking and Gluing

In order to enumerate sum-indecomposable posets, we break them down into more manageable pieces. (ii) In particular, we introduce two associative operations that can be used to build every sum-indecomposable poset. Suppose that we have sum-indecomposable posets $P_1$ and $P_2$ of height $a$ and $b$, respectively. If $P_1$ has no all-seeing vertex of top rank and $P_2$ has no all-seeing vertex of bottom rank, then we allow the following two constructions.

* We can stick $P_1$ and $P_2$ to form a new poset $P = P_1 \oplus_S P_2$ of height $a+b-1$, as follows:

- The vertex set of $P$ is the disjoint union of the vertex sets of $P_1$ and $P_2$.

- For $i=1,2$, if $v, w \in P_i$, then $v < w$ in $P$ if and only if $v < w$ in $P_i$.

<footnote>(ii) In defense of what seems like a bad joke, the original meaning of the word “atom” was “indecomposable,” but subatomic particles stubbornly exist.</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 5: An example of sticking two sum-indecomposable posets. (Labels are suppressed for readability.)</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 6: An example of gluing two sum-indecomposable posets. (Labels are suppressed for readability.)</figcaption></figure>

- If $v \in P_1$ and $w \in P_2$ then $v < w$ in $P$ unless rk($v$) = $a-1$ and rk($w$) = 0. In this case, $v$ and $w$ are incomparable.

- We distribute labels to vertices of $P$ consistent with the labelings of $P_1$ and $P_2$.

* We can glue $P_1$ and $P_2$ to form a new poset $P = P_1 \oplus_G P_2$ of height $a+b-1$, as follows:

- The vertex set of $P$ is the disjoint union of the following three sets: the vertex set of $P_1$, the vertex set of $P_2$, and a singleton set $\{\Xi\}$.

- For $i = 1, 2$, if $v, w \in P_i$ then $v < w$ in $P$ if and only if $v < w$ in $P_i$.

- If $v \in P_1$ and $w \in P_2$ then $v < w$ in $P$ unless rk($v$) = $a-1$ and rk($w$) = 0. In this case, we set $v$ and $w$ to be incomparable.

- If $v \in P_1$ is not of top rank then $v < \Xi$ in $P$. If instead rk($v$) = $a-1$ then $v$ and $\Xi$ are incomparable.

- If $w \in P_2$ is not of bottom rank then $\Xi < w$ in $P$. If instead rk($w$) = 0 then $w$ and $\Xi$ are incomparable.

- We distribute labels to vertices of $P$ consistent with the labelings of $P_1$ and $P_2$.

Note that gluing is basically sticking, except we add an all-seeing vertex to the boundary rank. Furthermore, as in the case of an ordinal sum of two layers, a vertex in $P_1$ or $P_2$ that it up-seeing or down-seeing keeps this status after either gluing or sticking. Figure 5 shows an example of sticking two posets; Figure 6 shows a gluing of two posets.

In the context of sum-indecomposable posets, these are good operations since they preserve sum-indecomposability, as the next result shows.

**Proposition 4.5** Suppose $P_1$ and $P_2$ are sum-indecomposable posets such that $P_1$ has no all-seeing vertices of top rank and $P_2$ has no all-seeing vertices of bottom rank. The posets $P_1 \oplus_S P_2$ and $P_1 \oplus_G P_2$ are sum-indecomposable.

**Proof:** We show that $P = P_1 \oplus_S P_2$ is sum-indecomposable; the proof for gluing is essentially identical. Let $P_1$ have height $a+1$ and let $P_2$ have height $b+1$. For any $i$ such that $0 < i < a$ we have $P(i) = P_1(i)$.
Since $P_1$ is sum-indecomposable, $P_1(i)$ contains both vertices that are not down-seeing and vertices that are not up-seeing. Similarly, for $a < i < a+b$ we have $P(i) = P_2(i-a)$ contains both types of vertices. So it remains to check that $P(a) = P_1(a) \cup P_2(0)$ contains both types of vertices. Indeed, since $P_1$ is sum-indecomposable we have that $P_1(a)$ contains some vertices that are not up-seeing, and since $P_2$ is sum-indecomposable we have that $P_2(0)$ contains some vertices that are not down-seeing. Thus, no vertex level of $P = P_1 \oplus_S P_2$ has all up-seeing nor all down-seeing vertices and so $P$ is sum-indecomposable, as desired. $\square$

The key observation of this section is that any sum-indecomposable poset can be decomposed at any rank by exactly one of the two operations we have just defined.

**Proposition 4.6** Let $P$ be a sum-indecomposable poset of height $k$, $k \ge 3$. For any rank $i$, $0 < i < k-1$, exactly one of the following is true:

* there exist posets $P_1$ of height $i+1$ and $P_2$ of height $k-i$ such that $P = P_1 \oplus_S P_2$, or

* there exist posets $P_1$ of height $i+1$ and $P_2$ of height $k-i$ such that $P = P_1 \oplus_G P_2$.

Furthermore, $P_1$ and $P_2$ are uniquely determined by $i$.

**Proof idea:** To decide whether smaller posets are stuck or glued together to form our larger poset, we check for the presence of an all-seeing vertex. $\square$

**Corollary 4.7** For $k \ge 1$, every sum-indecomposable poset $P$ of height $k+1$ can be written uniquely in the form

$$P = P_1 \oplus_{\alpha_1} P_2 \oplus_{\alpha_2} \cdots \oplus_{\alpha_{k-1}} P_k,$$

where each $\alpha_i$ is one of $S$ and $G$, each $P_i$ is a sum-indecomposable poset of height exactly 2 plus possibly some isolated vertices assigned to each rank, and no elements in any $P_i$ are all-seeing, except possibly a single vertex in each of $P_1(0) = P(0)$ and $P_k(1) = P(k)$.

Moreover, if $P_1, \dots, P_k$ satisfy the conditions above then the poset

$$P_1 \oplus_{\alpha_1} P_2 \oplus_{\alpha_2} \cdots \oplus_{\alpha_{k-1}} P_k$$

is sum-indecomposable.

We call $P_1, \dots, P_k$ the *quarks of $P$*. We will frequently refer to $P_1$ and $P_k$ as the *bottom quark* and *top quark* of $P$, respectively. Thus quarks are essentially height-2 sum-indecomposable posets with no all-seeing vertices, except possibly the top and bottom quarks, which may have one all-seeing vertex. Corollary 4.7 tells us that a sum-indecomposable poset $P$ of height $k+1$ has exactly $k$ quarks $P_1, \dots, P_k$, where $P_i$ is exactly the subposet induced by the vertices in $V(i+1) \cup \Lambda(i)$ that are not all-seeing.

Now we can connect our characterization of sum-indecomposable posets as quarks that have been glued or stuck together to our ultimate goal of studying (3 + 1)-avoiding posets.

**Proposition 4.8** For two sum-indecomposable posets $P_1$ and $P_2$ such that $P_1$ has no all-seeing vertex of top rank and $P_2$ has no all-seeing vertex of bottom rank,

1. $P_1 \oplus_G P_2$ is (3 + 1)-avoiding if and only if both $P_1$ and $P_2$ are, and

2. $P_1 \oplus_S P_2$ is (3 + 1)-avoiding if and only if the following hold:

* both $P_1$ and $P_2$ are (3 + 1)-avoiding, and

* if $Q_1$ is the top quark of $P_1$ and $Q_2$ is the bottom quark of $P_2$ then $Q_1$ has no isolated vertices on its bottom rank or $Q_2$ has no isolated vertices on the top rank (or both).
**Proof idea:** We show the result only for gluing; the proof for sticking is similar but involves a bit more work. Let $P = P_1 \oplus_G P_2$. One direction is clear: since $P$ contains $P_1$ and $P_2$ as induced subposets, if $P$ avoids $(3+1)$ then $P_1$ and $P_2$ do as well. We now show that the other direction also holds, except in the mentioned special case.

Assume $P_1$ and $P_2$ avoid $(3+1)$. As before, Theorem 3.1 tells us that $P$ avoids $(3+1)$ if and only if every pair of vertices $v, w \in P$ such that $rk(w) - rk(v) = 2$ also satisfies $v < w$. Since $P_1$ and $P_2$ are $(3+1)$-avoiding, it suffices to check only the case $v \in P_1$ and $w \in P_2$. Let $P_1$ have height $a+1$, so the boundary rank in $P$ is $P(a)$. There are three possible cases: $rk(v) = a-2$, $rk(v) = a-1$ and $rk(v) = a$. If $rk(v) = a-2$, then $w$, being comparable to every vertex in $P(a-1)$, must be comparable to $v$ as well, as desired. A similar argument takes care of the case $rk(v) = a$. The only remaining case is $rk(v) = a-1$ and $rk(w) = a+1$. But $P$ has an all-seeing vertex on rank $a$ – if we call this vertex $u$, we have $v < u < w$ and so $P$ avoids $(3+1)$, as desired. $\square$

The punchline of this section is that we now have a complete characterization of sum-indecomposable $(3+1)$-avoiding posets.

**Corollary 4.9** A sum-indecomposable poset $P$ is $(3+1)$-avoiding if and only if the decomposition $P = P_1 \oplus_{\alpha_1} P_2 \oplus_{\alpha_2} \cdots \oplus_{\alpha_{k-1}} P_k$ into quarks satisfies the following condition: for every occurrence of $P_i \oplus_S P_{i+1}$ in the decomposition, either $P_i$ has no isolated vertices on its bottom level or $P_{i+1}$ has no isolated vertices on its top level or both.

# 5 Quarks

Corollary 4.9 implies that studying sum-indecomposable $(3+1)$-avoiding posets reduces to studying quarks, which (except for possibly the top and bottom quarks) are height-2 labeled posets with no all-seeing vertices, plus possibly some isolated vertices of each rank. A small but useful observation is that such a height-2 labeled poset $P$ with $m$ vertices in $P(0)$ and $n$ vertices in $P(1)$ is, up to differences in the labeling scheme, just a bipartite graph on the disjoint union $[m] \uplus [n]$. In this section, we set out to enumerate quarks by enumerating such graphs, keeping track of some simple structural information about them.

We define a family of sets $A_{\mu}^{\nu}(m, n)$, where $\mu$ and $\nu$ are subsets (possibly empty) of $\{\square, \circ, \boxtimes, \otimes\}$, as follows:

* $A_{\mu}^{\nu}(m, n)$ is the set of bipartite graphs on $[m] \uplus [n]$ with some restrictions. The elements of $\nu$ correspond to restrictions on the vertices in $[n]$ and the elements of $\mu$ correspond to restrictions on the vertices of $[m]$. (Here the placement of indices is meant to suggest that vertices in $[m]$ form a bottom level and the vertices in $[n]$ a top level.) An empty set of symbols corresponds to no restrictions on the corresponding set.

* A $\square$ corresponds to the requirement that there be at least one all-seeing vertex; a $\boxtimes$ corresponds to the requirement that there be no all-seeing vertex.

* A $\circ$ corresponds to the requirement that there be an isolated vertex; a $\otimes$ corresponds to the requirement that there be no isolated vertex.

For example, $A(m, n)$ is the set of all bipartite graphs on $[m] \uplus [n]$ and $A^{\square}(m, n)$ is the subset of $A(m, n)$ containing those graphs with at least one all-seeing vertex in $[n]$ but no all-seeing vertices in $[m]$. Note that some collections of these restrictions allow no legal graphs: we have $A^{\circ}(m, n) = \emptyset$ for
all $m$ and $n$ because we cannot have both an isolated vertex in $[m]$ and an all-seeing vertex in $[n]$, while $A^{\otimes}(m, n) = \emptyset$ because we cannot both enforce and prohibit an isolated vertex in $[n]$.

We are particularly interested in quarks, which, roughly speaking, are those graphs with no all-seeing vertices; thus, for $\nu, \mu \subset \{\circ, \otimes\}$ we define $B_{\mu}^{\nu}(m, n) = A_{\{\boxtimes\} \cup \mu}^{\nu}(m, n)$. For example, $B_{\circ}^{\otimes}(m, n)$ is the set of bipartite graphs on $[m] \uplus [n]$ with no all-seeing vertices, no isolated vertices in $[n]$, and at least one isolated vertex in $[m]$. For each $B_{\mu}^{\nu}$, let

$$F_{\mu}^{\nu}(x) = \sum_{m,n \ge 1} |B_{\mu}^{\nu}(m,n)| \frac{x^{m+n}}{m!n!} \quad (1)$$

be the corresponding generating function. Finally, let $B_{\mu}^{\nu}$ be the union over $m$ and $n$ of all $B_{\mu}^{\nu}(m, n)$. Note that we have a disjoint union

$$B = B_{\circ}^{\circ} \cup B_{\otimes}^{\circ} \cup B_{\circ}^{\otimes} \cup B_{\otimes}^{\otimes},$$

which manifests as a sum of formal power series

$$F = F_{\circ}^{\circ} + F_{\otimes}^{\circ} + F_{\circ}^{\otimes} + F_{\otimes}^{\otimes}.$$

**Proposition 5.1** Let

$$\Psi(x) = \sum_{m,n \ge 0} \frac{2^{mn} x^{m+n}}{m!n!}$$

and let $F_{\mu}^{\nu}$ be defined as in Equation (1). We have

$$F_{\circ}^{\circ}(x) = (1 - e^{-x})^2 \Psi(x),$$

$$F_{\otimes}^{\circ}(x) = F_{\circ}^{\otimes}(x) = (1 - e^{-x})((2e^{-x} - 1)\Psi(x) - 1),$$

and

$$F_{\otimes}^{\otimes}(x) = (2e^{-x} - 1)((2e^{-x} - 1)\Psi(x) - 1).$$

**Proof idea:** The result essentially follows from careful applications of inclusion-exclusion. $\square$

# 6 Strongly Graded Posets

In this section, we use the $F_{\mu}^{\nu}$ as building blocks to obtain the generating function for sum-indecomposable (3 + 1)-avoiding posets, and then proceed to enumerate all strongly graded (3 + 1)-avoiding posets. We begin by encoding a sum-indecomposable poset in terms of a *word* that keeps track of its quarks and how they are combined (i.e., gluing and sticking). Then we use the transfer-matrix method to enumerate words while keeping track of the restrictions imposed by Corollary 4.9.

For a quark with no all-seeing vertices (i.e., a quark in $B$), we define its *type* to be the symbol $B_{\mu}^{\nu}$, corresponding to the unique subset among the four $B_{\mu}^{\nu}$ to which it belongs. (This is a slight abuse of notation that will always be unambiguous in context.) Now, define a *word* to be any monomial in the noncommutative algebra $R\langle\langle S, G, B_{\circ}^{\circ}, B_{\circ}^{\otimes}, B_{\circ}^{\otimes}, B_{\otimes}^{\otimes}\rangle\rangle$. We now encode the properties of being sum-indecomposable and (3 + 1)-avoiding into conditions on words.
**Definition 6.1** We say that a word $L$ is legal if for some $k \ge 1$ there are $\alpha_i \in \{S, G\}$ and $B_i \in \{B_0^\circ, B_0^{\otimes}, B_1^\circ, B_1^{\otimes}\}$ such that $L = \alpha_0 B_1 \alpha_1 B_2 \alpha_2 \cdots B_{k-1} \alpha_{k-1} B_k \alpha_k$, and none of the following occur:

1. $\alpha_0 = S$ and $B_1$ has a $\circ$ in the superscript;

2. $\alpha_k = S$ and $B_k$ has a $\circ$ in the subscript;

3. there is some $i$, $1 \le i \le k-1$, such that $B_i$ has a $\circ$ in the subscript, $\alpha_i = S$, and $B_{i+1}$ has a $\circ$ in the superscript.

We define a weight function $\mathrm{wt} : \mathbf{R}\langle\langle S, G, B_0^\circ, B_0^{\otimes}, B_1^\circ, B_1^{\otimes} \rangle\rangle \to \mathbf{R}\llbracket x, z \rrbracket$ as follows: we set $\mathrm{wt}(S) = 1$, $\mathrm{wt}(G) = z$, and $\mathrm{wt}(B_\mu^\nu) = F_\mu^\nu$ and we extend by linearity and multiplication.

**Proposition 6.2** Let $I(x, z)$ be the generating function for nonempty sum-indecomposable (3+1)-avoiding posets, where the variable $z$ counts all-seeing vertices, the variable $x$ counts other vertices, and $I(x, z)$ is exponential in $x$ and ordinary in $z$. Then

$$I(x, z) = z + \sum_{L} \mathrm{wt}(L),$$

where the sum is over all legal words $L$.

**Proof idea:** Given a legal word $L = \alpha_0 B_1 \alpha_1 B_2 \alpha_2 \cdots B_{k-1} \alpha_{k-1} B_k \alpha_k$ such that for all $i$, $B_i$ is a quark type and $\alpha_i \in \{S, G\}$, one checks that the generating function $\mathrm{wt}(L)$ counts posets $P$ that decompose into quarks as $P = P_1 \oplus \alpha_1 \cdots \oplus \alpha_{k-1} P_k$, where $P_i$ is of type $B_i$. Legality of the word corresponds precisely to (3 + 1)-avoidance of the poset. $\square$

This result establishes that to enumerate posets we may focus our energies on enumerating words. We accomplish this task with the transfer-matrix method.

**Theorem 6.3** Let $M_W$ be the matrix

$$M_W = G \cdot \begin{bmatrix} B_0^\circ & B_0^{\otimes} & B_0^{\otimes} & B_0^{\otimes} \\ B_0^\circ & B_0^{\otimes} & B_0^{\otimes} & B_0^{\otimes} \\ B_0^\circ & B_0^{\otimes} & B_0^{\otimes} & B_0^{\otimes} \\ B_0^\circ & B_0^{\otimes} & B_0^{\otimes} & B_0^{\otimes} \end{bmatrix} + S \cdot \begin{bmatrix} 0 & B_0^\circ & 0 & B_0^{\otimes} \\ 0 & B_0^\circ & 0 & B_0^{\otimes} \\ B_0^\circ & B_0^\circ & B_0^{\otimes} & B_0^{\otimes} \\ B_0^\circ & B_0^\circ & B_0^{\otimes} & B_0^{\otimes} \end{bmatrix}$$

with entries in the noncommutative algebra $\mathbf{R}\langle\langle S, G, B_0^\circ, B_0^{\otimes}, B_1^\circ, B_1^{\otimes} \rangle\rangle$ of words. The sum of the legal words of length $2k+1$ is

$$[G \cdot B_0^\circ \quad (S+G)B_0^\circ \quad G \cdot B_0^{\otimes} \quad (S+G)B_0^{\otimes}] \cdot (M_W)^{k-1} \cdot \begin{bmatrix} G \\ G \\ S+G \\ S+G \end{bmatrix}$$

and the generating function for all sum-indecomposable (3 + 1)-avoiding posets of height at least 2 is

$$I_{\ge 2}(x, z) = [z F_0^\circ \quad (1+z) F_0^{\otimes} \quad z F_0^{\otimes} \quad (1+z) F_0^{\otimes}] \cdot (\mathbb{I} - \mathrm{wt}(M_W))^{-1} \cdot \begin{bmatrix} z \\ z \\ 1+z \\ 1+z \end{bmatrix}.$$
<figure><img src="image_7.png" /><figcaption>**Fig. 7:** The S-labeled edges of the graph $G_w$ defined in the proof of Theorem 6.3. Each pair of vertices is also joined by directed edges labeled G (not shown).</figcaption></figure>

**Proof idea:** Consider the graph $G_w$ with vertices {$*, B_O^circ, B_O^{circ}, B_O^{\otimes}, B_O^{\otimes}$} and the following directed, labeled edges: for each pair $u, v$ of vertices (allowing $u = v$), $G_w$ has a directed edge $u \xrightarrow{S} v$ unless $u = B_O^circ$ or $u = *$ and $v = B_O^{circ}$ or $v = *$, and for every pair $u, v$ of vertices, $G_w$ has a directed edge $v \xrightarrow{G} w$. The graph $G_w$ is illustrated in Figure 7.

We identify each walk $\alpha_0 \xrightarrow{\alpha_0} B_1 \xrightarrow{\alpha_1} \cdots B_k \xrightarrow{\alpha_k} *$ with the word $\alpha_0 B_1 \alpha_1 \cdots B_k \alpha_k$. Observe that the first two conditions in Definition 6.1 exactly correspond to the restrictions on edges involving $*$ and the final condition exactly corresponds to edges not involving $*$. Thus the legal words are exactly the walks on this graph that start and end at $*$, with no intermediate instances of $*$. The first half of the conclusion follows by an application of the transfer-matrix method, as in [6, Section 4.7], and the second half follows from Proposition 6.2 and the fact that the weight map $wt$ is an algebra homomorphism between $R\langle S, G, B_O^circ, B_O^{\otimes}, B_O^{\otimes}, B_O^{\otimes} \rangle$ and $R\llbracket x, z \rrbracket$. $\square$

Now that we have enumerated sum-indecomposable (3 + 1)-avoiding posets, the only remaining step is to express the generating function for all (3 + 1)-avoiding posets in terms of the generating function for sum-indecomposables. This turns out to be extremely simple.

**Theorem 6.4** Let $I(x, z)$ be the generating function of nonempty sum-indecomposable (3 + 1)-avoiding posets and let $G_T(x, z)$ be the generating function for all trimmed strongly graded (3 + 1)-avoiding posets. Then

$$G_T(x, z) = (1 - I(x, z))^{-1},$$

and the generating function for all strongly graded (3 + 1)-avoiding posets is

$$G_T(x, e^x - 1) = 1 + \frac{e^{2x}(2e^x - 3) + e^x(e^x - 2)^2 \Psi(x)}{e^x(2e^x + 1) + (e^{2x} - 2e^x - 1)\Psi(x)}.$$

**Proof:** By Proposition 4.3 and Proposition 4.4 each trimmed (3 + 1)-avoiding poset $P$ corresponds to a unique sequence $P_1 \oplus_L P_2 \oplus_L \cdots \oplus_L P_k$ of sum-indecomposable (3 + 1)-avoiding posets, and all such sequences give a trimmed (3 + 1)-avoiding poset $P$. Then the first half of the result is a standard exercise in the theory of combinatorial species. The second half is just a calculation, combining Proposition 6.2 and Theorem 6.2 with Proposition 4.2. For $\#P = 0, 1, \dots$, the resulting number of posets is 1, 1, 3, 13, 111, 1381, 22383, ... $\square$
# 7 Extensions

In this section we mention extremely briefly some extensions of our work; see [4] for details. Using the same techniques as in the preceding sections, one can easily refine the enumeration of strongly graded (3 + 1)-avoiding by height. We can show that weakly graded (3 + 1)-avoiding posets look “mostly” like strongly graded posets, with maximal vertices permissible only in the top two vertex levels and minimal vertices only in the bottom two vertex levels. The results of the previous two sentences allow us to compute that the generating function for weakly graded (3 + 1)-avoiding posets is $(e^{-x} - 1)\Psi(x) + \frac{2e^{3x}+(e^{3x}-2e^{2x})\Psi(x)}{e^x(2e^x+1)+(e^{2x}-2e^{x-1})\Psi(x)}$. One can also give asymptotics for the associated sequences; the number of strongly graded (3 + 1)-avoiding posets on $n$ vertices and the number of weakly graded (3 + 1)-avoiding posets on $n$ vertices are both asymptotic to $n! \cdot [x^n]\Psi(x)$.

# Acknowledgments

We wish to thank Alejandro Morales and Richard Stanley for valuable conversations. Yan Zhang was supported by an NSF graduate research fellowship.

# References

[1] Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, and Sergey Kitaev. (2 + 2)-free posets, ascent sequences and pattern avoiding permutations. *J. Combin. Theory Ser. A*, 117(7):884–909, 2010.

[2] Peter C. Fishburn. Intransitive indifference with unequal indifference intervals. *J. Mathematical Psychology*, 7:144–149, 1970.

[3] David A. Klarner. The number of graded partially ordered sets. *J. Combinatorial Theory*, 6:12–19, 1969.

[4] Joel Brewster Lewis and Yan X Zhang. Enumeration of graded (3 + 1)-avoiding posets. arXiv:1106.5480v1.

[5] Mark Skandera. A characterization of (3 + 1)-free posets. *J. Combin. Theory Ser. A*, 93(2):231–241, 2001.

[6] Richard P. Stanley. *Enumerative combinatorics. Vol. 1*, volume 49 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, 1997.

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

[8] Richard P. Stanley and John R. Stembridge. On immanants of Jacobi-Trudi matrices and permutations with restricted position. *J. Combin. Theory Ser. A*, 62(2):261–279, 1993.