%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2018}
\articlenumber{73}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}


%These are what I added
%%%%%%%%%%%%
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{question}[thm]{Question}
\usepackage{enumerate}
\usepackage{ytableau}
\ytableausetup{smalltableaux}
\newcommand{\N}{\mathbf{N}}
\newcommand{\Z}{\mathbf{Z}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\C}{\mathbf{C}}
\newcommand{\QSym}{\textrm{QSym}}
\newcommand{\KP}{K_P(\x)}
\newcommand{\KQ}{K_Q(\x)}
\newcommand{\Comp}{\textrm{Comp}}
\newcommand{\des}{\textrm{des}}
\renewcommand{\k}{\mathbf{k}}
\DeclareMathOperator{\anti}{anti}
\DeclareMathOperator{\co}{co}
\newcommand{\antikij}{\anti_{k,i,j}}
\DeclareMathOperator{\alphajump}{\alpha\text{-}jump}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\sh}{sh}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\jump}{jump}
\DeclareMathOperator{\upjump}{up-jump}
\usepackage{tikz, tikz-3dplot, pgfplots}
\usepackage{tkz-graph}
\usetikzlibrary{matrix}
\usetikzlibrary[positioning,patterns] % tikz libraries for relative positioning and silly patterns
\usepackage{color}
\newcommand{\TikZ}{Ti$k$Z }
%%%%%%%%%%%%



\usepackage{lipsum}

%% define your title in the usual way
\title{$P$-Partition Generating Function Equivalence of Naturally Labeled Posets}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Ricky Ini Liu\thanks{\href{mailto:riliu@ncsu.edu}{riliu@ncsu.edu}. Partially supported by NSF grant DMS-1700302.}\addressmark{1} \and Michael Weselcouch\thanks{\href{mailto:mweselc@ncsu.edu}{mweselc@ncsu.edu}. Partially supported by NSF grant DMS-1700302.}\addressmark{1}}
%\thanks{\href{mailto:hello@world.c}{hello@world.c}.Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}


%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, North Carolina State University}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{The \emph{$P$-partition generating function} of a (naturally labeled) poset $P$ is a quasisymmetric function enumerating order-preserving maps from $P$ to $\Z^+$. Using the Hopf algebra of posets, we give necessary conditions for two posets to have the same generating function. In particular, we show that they must have the same number of antichains of each size and the same shape (as defined by Greene). We also discuss which shapes guarantee uniqueness of the $P$-partition generating function and give a method of constructing pairs of non-isomorphic posets with the same generating function.}

%Given a poset $P$, we define the $P$-partition generating function.  This is a quasisymmetric function determined by the linear extensions of $P$.  We will discuss the case when two distinct posets have the same $P$-partition generating function and state necessary conditions that these posets must satisfy. We will see that the shape of a naturally labeled poset plays a large role in determining whether there exists a distinct poset with the same $P$-partition generating function.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{$P$-Partition, Quasisymmetric Function, Combinatorial Hopf Algebra}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{73-Liu-Weselcouch.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
For a finite poset $P$ (labeled with the ground set $[n] = \{1, 2, \dots n \}$), the \emph{$P$-partition generating function} $\KP$ is a quasisymmetric function enumerating certain order-preserving maps from $P$ to $\Z^+$. The question of when two distinct posets can have the same $P$-partition generating function has been studied extensively in the case of skew Schur functions \cite{BTvW, MvW, RSvW}, by McNamara and Ward \cite{McNamaraWard} for general labeled posets, and by Hasebe and Tsujie \cite{HasebeTsujie} for rooted trees. The goal of this paper is to consider the naturally labeled case, that is, to give necessary and sufficient conditions for when two naturally labeled posets have the same $P$-partition generating function. (We say that $P$ is \emph{naturally labeled} if $x \preceq_P y$ implies $x \leq y$ as integers.)

In general, it is not true that a poset can be distinguished by its $P$-partition generating function. The smallest case in which two distinct naturally labeled posets have the same $P$-partition generating function is the two $7$-element posets shown below. We will explore this example further in Section 5, where we give a general construction for non-isomorphic posets with the same generating function.

\begin{center}
\begin{tikzpicture}
 [auto,
 vertex/.style={circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=1mm}]
\node (v1) at ( 0,0) [vertex] {};
\node (v2) at ( 1,0) [vertex] {};
\node (v3) at ( -1,1) [vertex] {};
\node (v4) at ( 0,1) [vertex] {};
\node (v5) at ( 1,1) [vertex] {};
\node (v6) at ( 0,2) [vertex] {};
\node (v7) at ( 1,2) [vertex] {};
\draw [-] (v1) to (v4);
\draw [-] (v4) to (v6);
\draw [-] (v2) to (v5);
\draw [-] (v5) to (v7);
\draw [-] (v1) to (v3);
\draw [-] (v3) to (v6);
\draw [-] (v1) to (v7);
\draw [-] (v2) to (v6);
\end{tikzpicture}
\hspace{3 cm}
\begin{tikzpicture}
 [auto,
 vertex/.style={circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=1mm}]
\node (v1) at ( 4,0) [vertex] {};
\node (v2) at ( 5,0) [vertex] {};
\node (v3) at ( 3,1) [vertex] {};
\node (v4) at ( 4,1) [vertex] {};
\node (v5) at ( 5,1) [vertex] {};
\node (v6) at ( 4,2) [vertex] {};
\node (v7) at ( 5,2) [vertex] {};
\draw [-] (v1) to (v4);
\draw [-] (v4) to (v6);
\draw [-] (v2) to (v5);
\draw [-] (v5) to (v7);
\draw [-] (v1) to (v3);
\draw [-] (v3) to (v7);
\draw [-] (v2) to (v6);
\end{tikzpicture}
\end{center}



%A $P$-partition is a map from $P$ to $\Z^+$ that respects the ordering of $P$.  We will define the $P$-partition generating function $\KP$ to be a formal power series that runs over all $P$-partitions.  Stanley \cite{Stanley} showed that $\KP$ only depends on the linear extensions of $P$.  

We will use tools from the combinatorial Hopf algebra structure on posets due to Schmitt \cite{Schmitt} (see also \cite{ABS}) to prove that if $\KP = \KQ$, then for all triples $(k, i, j)$, $P$ and $Q$ must have the same number of $k$-element order ideals that have $i$ maximal elements and whose complement has $j$ minimal elements. As a result of our proof, one can compute certain coefficients in the fundamental quasisymmetric function expansion of $\KP$ explicitly in terms of the number of such ideals.

%Gessel and Stanley showed in \cite{Gessel, Stanley} CHECK THIS that $\KP$ is determined by the descent sets of the linear extensions of $P$.  Since we are only studying naturally labeled posets, the descents in a linear extension of $P$ correspond to the antichains in $P$.  The shape of a finite poset, denoted $sh(P)$, is the partition $\lambda$ that satisfies
%\[\lambda_1' + \lambda_2'+\cdots+\lambda_i' = a_i\]
%where $a_i$ is the largest number of elements in a union of $i$ antichains of $P$.  If the elements $\{x_1, \dots, x_l\}$ form and antichain in $P$ then there is a linear extension of $P$ where $\{x_1, \dots, x_l\}$ appear consecutively, in decreasing order.  We will use this fact to show that if $\KP = \KQ$ then $P$ and $Q$ must have the same shape.  In fact we will prove a stronger statement, if $supp_L(P) = supp_L(Q)$ then $P$ and $Q$ must have the same shape.  This results led us to ask the following question: for what partitions $\lambda$ where $sh(P) = \lambda$ does $\KP = \KQ$ imply that $P$ is congruent to $Q$?

 We will also show that if $\KP = \KQ$, then $P$ and $Q$ must have the same shape. Here, the \emph{shape} of a finite poset, denoted $\sh(P)$, is the partition $\lambda$ whose conjugate partition $\lambda'$ satisfies
\[\lambda'_1 + \lambda'_2+\cdots+\lambda'_i = a_i,\]
where $a_i$ is the largest number of elements in a union of $i$ antichains of $P$. In fact, we will prove a stronger statement, namely that if the support of $\KP$ and $\KQ$ in the fundamental quasisymmetric function basis is the same, then $P$ and $Q$ must have the same shape. This suggests the following question: for which partitions $\lambda$ does $\sh(P) = \lambda$ guarantee that $P$ is uniquely determined by $\KP$?



We show that if $\sh(P)$ has at most two parts, is a hook shape, or has the form $\sh(P) = (\lambda_1, 2, 1, \dots, 1)$, then $\KP = \KQ$ implies $P \cong Q$. Conversely, we show that if $\sh(P)$ contains $(3, 3, 1)$ or $(2, 2, 2, 2)$, then $\KP = \KQ$ does not necessarily imply $P \cong Q$ by constructing two distinct posets of this shape with the same generating function.  It remains to be answered what happens when $\sh(P) = (\lambda_1, 2, 2, 1, \dots, 1)$.

In Section 2 we will give some preliminary information; in Section 3 we state some necessary conditions for two posets to have the same generating function; in Section 4 we discuss when the shape of a poset ensures that its generating function is unique; and in Section 5 we give a general construction for pairs of posets with the same generating function.

\section{Preliminaries}
%What needs to be defined: Naturally labeled, P-Partition generating function, linear extension, J(P), $anti_{k, i, j}$, Hopf Alg., shape of a poset., ordinal sum

We begin with some preliminaries about posets, quasisymmetric functions, and Hopf algebras. For more information, see \cite{GrinbergReiner, McNamaraWard, Stanley}.

\subsection{Posets and $P$-partitions}
Let $P = (P, \prec)$ be a finite poset. A \emph{labeling} of $P$ is a bijection $\omega \colon P \to \{1, 2, \dots, n\}$.

\begin{defn} For a labeled poset $(P, \omega)$, a \emph{$(P, \omega)$-partition} is a map $\sigma \colon P \to \Z^+$ that satisfies the following:
\begin{enumerate}[(a)]
\item If $x \preceq y$, then $\sigma(x) \leq \sigma(y)$.
\item If $x \preceq y$ and $\omega(x) > \omega(y)$, then $\sigma(x) < \sigma(y)$.
\end{enumerate}
\end{defn}


\begin{defn} The \emph{$(P, \omega)$-partition generating function} $K_{(P, \omega)}(x_1, x_2, \dots)$ for a labeled poset $(P, \omega)$ is given by 
\[ K_{(P, \omega)}(x_1, x_2, \dots ) = \sum_{(P, \omega)\text{-partition } \sigma}x_1^{|\sigma^{-1}(1)|}x_2^{|\sigma^{-1}(2)|}\dots,\]
where the sum ranges over all $(P, \omega)$-partitions $\sigma$.
%\newline \textbf{This was taken word for word from Ward's paper}
\end{defn}
A labeled poset $(P, \omega)$ is equivalent to a poset $P$ with ground set $[n]$. Hence we may refer to the generating function $K_{(P, \omega)}(x_1, x_2, \dots )$ as $K_{P}(x_1, x_2, \dots )$ or $K_{P}(\mathbf{x})$ if the choice of $\omega$ is implicit. 


In this paper, we will usually restrict our attention to the case when $P$ is \emph{naturally labeled}, that is, when $\omega$ is an order-preserving map. In this case, $K_P(\mathbf{x})$ does not depend on our choice of natural labeling but only on the underlying structure of $P$.

A \emph{linear extension} of a poset $P$ with ground set $[n]$ is a permutation $\sigma$ of $[n]$ that respects the relations in $P$, that is, if $x \preceq y$, then $\sigma^{-1}(x) \leq \sigma^{-1}(y)$.  The set of all linear extensions of $P$ is denoted $\mathcal{L}(P)$. %Note that $|\mathcal L(P)|$ is the coefficient of $x_1x_2\cdots x_n$ in $K_P(\mathbf{x})$.

\subsection{Compositions}

A \textit{composition} $\alpha= (\alpha_1, \alpha_2, \dots, \alpha_k)$ of $n$ is a finite sequence of positive integers summing to $n$. The compositions of $n$ are in bijection with the subsets of $[n-1]$ in the following way: for any composition $\alpha$, define \[D(\alpha) = \{\alpha_1, \quad \alpha_1 + \alpha_2, \quad \dots, \quad \alpha_1 + \alpha_2 +\dots +\alpha_{k-1}\} \subseteq [n-1].\]

Likewise, for any subset $S = \{s_1, s_2, \dots, s_{k-1}\}\subseteq [n-1]$ with $s_1<s_2<\dots < s_{k-1}$, we can define the composition
\[\co(S) = (s_1, \quad s_2-s_1, \quad s_3-s_2, \quad \dots, \quad s_{k-1}-s_{k-2}, \quad n-s_{k-1}).\]

%Given two nonempty compositions $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_k)$, $\beta = (\beta_1, \beta_2, \dots, \beta_m)$, their \emph{concatenation} is
%\[\alpha \cdot \beta = (\alpha_1, \alpha_2, \dots, \alpha_k, \beta_1, \beta_2, \dots, \beta_m). \]

%Their \emph{near-concatenation} is
%\[ \alpha \odot \beta = (\alpha_1, \alpha_2, \dots, \alpha_k + \beta_1, \beta_2, \dots, \beta_m). \]

%We will use the shorthand $1^k$ to denote the composition $(\underbrace{1, 1, \dots, 1}_k)$.

%There is a bijection sending $\alpha$ to its \emph{ribbon representation}.  The ribbon representation for $\alpha$ is the skew diagram $\lambda \setminus \mu$ having rows of sizes $(\alpha_1, \dots, \alpha_k)$ read from bottom to top with exactly one column of overlap between adjacent rows.

%For example, the figure below depicts the ribbon representation of $\alpha = (3, 1, 2, 4)$.
%\begin{center}
%\ydiagram{3+4,2+2,2+1,3}
%\end{center}
%Each composition can be written as the near-concatenation of compositions of all $1$s.  The composition $\alpha$ can be expressed as $\alpha = 1^{a_1} \odot 1^{a_2} \odot \dots \odot 1^{a_l}$ where $a_i$ is the number of boxes in the $i^{th}$ column of $\alpha's$ ribbon representation.  We will refer to the expansion $\alpha = 1^{a_1} \odot 1^{a_2} \odot \dots \odot 1^{a_l}$ as the \emph{near-concatenation decomposition} of $\alpha$.  The \emph{leading term of $\alpha$} is $a_1$.  Similarly, the \emph{final term of $\alpha$} is $a_l$.


\subsection{Quasisymmetric Functions}

A \emph{quasisymmetric function} in the variables $x_1, x_2, \dots$ (with coefficients in $\C$) is a formal power series $f(\mathbf{x}) \in \C[[\mathbf{x}]]$ of bounded degree such that, for any composition $\alpha$, the coefficient of $x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_k^{\alpha_k}$ equals the coefficient of $x_{i_1}^{\alpha_1}x_{i_2}^{\alpha_2}\cdots x_{i_k}^{\alpha_k}$ whenever $i_1 < i_2 < \dots < i_k$.  We denote the algebra of quasisymmetric functions by $\textrm{QSym}$.

%There are two natural bases for $\textrm{QSym}$, the monomial basis and the fundamental basis.  The \textit{monomial quasisymmetric function basis}, $\{M_\alpha\}$, indexed by compositions $\alpha$, is given by 
%\[M_\alpha = \sum_{1\leq i_1<i_2<\dots <i_k}  x_{i_1}^{\alpha_1}x_{i_2}^{\alpha_2}\cdots x_{i_k}^{\alpha_{k}}.\]
%For example, $M_{(2, 1)} = \sum_{i<j}x_i^2x_j$.

The \textit{fundamental quasisymmetric function basis} $\{L_\alpha\}$ is indexed by compositions $\alpha$ and is given by
\[L_\alpha = \sum_{\substack{i_1 \leq \dots \leq i_n\\i_s < i_{s+1} \text{ if } s \in D(\alpha)}} x_{i_1}x_{i_2} \cdots x_{i_n}.\]
%In terms of the monomial basis,
%\[L_\alpha = \sum_{\beta \preceq \alpha}M_\beta,\]
%where the sum runs over all refinements $\beta$ of $\alpha$.  (A composition $\beta$ is a \emph{refinement} of $\alpha$ if $\alpha$ can be obtained by adding together adjacent parts of the composition $\beta$.)

%\medskip

%Note that $K_{(P, \omega)}(\mathbf{x}) \in \QSym$ for any labeled poset $(P, \omega)$. Let $\C[\mathcal P]$ denote the $\C$-vector space with basis $\mathcal P$, the set of isomorphism classes of finite posets. We define the function $K\colon \C[\mathcal{P}] \to \QSym$ to be the linear map sending a (naturally labeled) poset $P$ to its $P$-partition generating function $K_P(\mathbf{x})$. We will see later that $\C[\mathcal P]$ and $\QSym$ have the structures of combinatorial Hopf algebras and that $K$ is a Hopf morphism.

For any labeled poset $P$ (on the ground set $[n]$), $K_{P}(\mathbf{x})$ is a quasisymmetric function, and we can express it in terms of the fundamental basis $\{L_\alpha\}$ using the linear extensions of $P$. For any linear extension $\sigma \in \mathcal L(P)$, define the \emph{descent set} of $\sigma$ to be $\des(\sigma) = \{i \mid \sigma(i) > \sigma(i+1)\}$. We abbreviate $\co(\des(\sigma))$ by $\co(\sigma)$.



\begin{thm}[\cite{Gessel, Stanley}]\label{L Expansion}
Let $P$ be a (labeled) poset on $[n]$.  Then
\[ K_{P}(\mathbf{x}) = \sum_{\sigma \in \mathcal{L}(P)}L_{\co(\sigma)}.\]
\end{thm}
In other words, the descent sets of the linear extensions of $P$ determine its $P$-partition generating function.  %This fact will be useful later when showing that two naturally labeled posets $P$ and $Q$ have different $P$-partition generating functions because we can just show that a linear extension of $P$ has a descent set that no linear extension of $Q$ has.

If $\KP = \sum_{\alpha}c_{\alpha}L_{\alpha}$, then we define the \emph{support} of $\KP$ to be
\[\supp(K_P(\mathbf{x})) = \{ \alpha \mid c_{\alpha} \neq 0\}.\]


\subsection{Antichains and Shape}
An \textit{antichain} is a subset $A$ of a poset $P$ such that any two elements of $A$ are incomparable. The \textit{width} of $P$ is the size of its longest antichain.

%The antichain structure of a naturally labeled poset $P$ plays an important role in determining which sets can appear as descent sets for linear extensions of $P$.  Since $P$ is naturally labeled, elements $i < j$ form an antichain in $P$ if and only if there exists a linear extension of $P$ in which $j$ appears immediately before $i$.  This means that every descent in a linear extension of $P$ is formed by a $2$-element antichain.  Similarly, if there is a linear extension of $P$ that has $i$ consecutive descents, then these elements form an $(i+1)$-element antichain in $P$.  %This shows that the size of some of $P$'s antichains can be obtained by $K_P(\mathbf{x})$.
The following Duality Theorem due to Greene allows one to associate to any poset a partition called its \emph{shape}. For $k \geq 0$, let $a_k$ (resp. $c_k$) denote the maximum cardinality of a union of $k$ antichains (resp. chains) in $P$.  Let $\lambda_k = c_k - c_{k-1}$ and $\tilde\lambda_k = a_k - a_{k-1}$ for $k \geq 1$. 
\begin{thm}[Greene \cite{Greene}, \cite{e9b51c683eb94f0d8d7529457db47fa6}]  For any finite poset $P$,  the sequence $\lambda = (\lambda_1, \lambda_2, \dots)$ and $\tilde\lambda = (\tilde\lambda_1, \tilde\lambda_2, \dots)$ are weakly decreasing and form conjugate partitions of the number $n = |P|$.
\end{thm}

The partition $\lambda$ is called the \emph{shape} of $P$. Note that the number of nonzero parts in $\sh(P)$ equals the width of $P$.






\subsection{Poset of Order Ideals}

An \emph{order ideal} of a poset $P$ is a subset $I$ such that $x \in I$ implies $y \in I$ for $y \leq x$. The set of all order ideals of $P$, ordered by inclusion, forms a poset that we will denote $J(P)$.  In fact, $J(P)$ is a finite ranked distributive lattice.  The rank of an ideal is the number of elements in the ideal. %  It is also the minimum number of chains needed to partition $P$ into a union of chains. If the width of $P$ equals $m$, then $J(P)$ is isomorphic to a sublattice of $\mathbb{N}^m$.  Suppose $J(P)$ is partitioned into $m$ chains, $C_1, \dots C_m$, $J(P)$ is embedded into $\mathbb{N}^m$ by mapping an ideal $I$ to the point $(a_1, a_2, \dots, a_m)$ where $a_i = |I \cap C_i|$.  When referring to $J(P)$ we will treat it as a sublattice of $\mathbb{N}^m$.

Each ideal $I$ in $J(P)$ covers a number of elements equal to the number of maximal elements of $I$, and $I$ is covered by a number of elements equal to the number of minimal elements of $P\setminus I$.  Let $\antikij(P)$ be the number of $k$-element ideals $I$ of $P$ such that $I$ has $i$ maximal elements and such that $P \setminus I$ has $j$ minimal elements.  Equivalently, $\antikij(P)$ is the number of rank $k$ elements of $J(P)$ that cover $i$ elements and are covered by $j$ elements.  %Observe that 
%\[\sum_{i, j} \antikij(P) = \rank_k(P)\]
%where $\rank_k(P)$ is the number of $k$-element ideals of $P$.


If there is only one element of a certain rank in $J(P)$, then $P$ can be expressed as $P = Q \oplus R$, where $\oplus$ is \emph{ordinal sum}. (By definition, in the ordinal sum $P = Q \oplus R$, $x\preceq_P y$ if and only if $x \preceq_Q y$, $x \preceq_R y$, or $x \in Q$ and $y \in R$.)

\begin{defn}
A finite poset $P$ is \emph{irreducible} if $P = Q \oplus R$ implies that either $Q \cong P$ or $R \cong P$.
\end{defn}

Each poset has a unique (up to isomorphism) ordinal sum decomposition, $P = P_1 \oplus P_2 \oplus \dots \oplus P_k$ with $P_i$ irreducible and $|P_i|=n_i$ for $i = 1, \dots, k$.  The ranks in which $J(P)$ has exactly one element are $0, n_1, n_1 + n_2, \dots, n_1 + n_2 + \dots + n_k$.  Linear extensions of $P$ can be broken up into $k$ parts: the first $n_1$ elements form a linear extension of $P_1$, the next $n_2$ elements form a linear extension of $P_2$ and so on.  In the case when $P$ is naturally labeled, if elements $a$ and $b$ form a descent in a linear extension of $P$, then $a$ and $b$ must both be in $P_i$ for some $i$.  This means that no linear extension of $P$ has a descent in the locations $n_1, n_1 + n_2, \dots,$ and $n_1+n_2+ \dots + n_k$.

\begin{lem}\label{K of reducible}
Suppose $P$ has an ordinal sum decomposition $P = P_1 \oplus P_2 \oplus \dots \oplus P_k$ and $Q$ has an ordinal sum decomposition $Q = Q_1 \oplus Q_2 \oplus \dots \oplus Q_j$.  If $K_P(\mathbf{x}) = K_Q(\mathbf{x})$ then $k = j$ and $K_{P_i}(\mathbf{x}) = K_{Q_i}(\mathbf{x})$ for $i = 1, \dots, k$.
\end{lem}

\begin{proof}
This follows immediately from the fact that linear extensions can only have descents in their irreducible parts.
\end{proof}

\subsection{Hopf Algebra}

Let $\mathcal{J}$ denote the set of all finite distributive lattices up to isomorphism. The free $\C$-module, $\C[\mathcal{J}]$, whose basis consists of isomorphism classes of distributive lattices $[J] \in \mathcal{J}$, can be given a Hopf algebra structure known as the \textit{reduced incidence Hopf algebra} \cite{Schmitt}. Multiplication and comultiplication are defined as follows:%Multiplication, unit, comultiplication, and counit are defined as follows:
\begin{align*}
\nabla([J_1] \otimes [J_2])&:= [J_1 \times J_2],\\
\Delta[J] &:= \sum_{x \in J} [\hat{0}, x] \otimes [x, \hat{1}]
\end{align*}
%\[1_{\mathbf{k}[\mathcal{J}]} : = [0]\]
%\[
%\epsilon[J] := \left\{
%        \begin{array}{ll}
%            1 & \text{if } |J|=1, \\
%            0 & \text{otherwise.}
%        \end{array}
%    \right.
%\]
where  $[a, b] = \{x \in J \mid a \leq x \leq b\}$.  In fact, the reduced incidence Hopf algebra can be made into a combinatorial Hopf algebra after choosing an appropriate character.  A \emph{combinatorial Hopf algebra} $\mathcal{H}$ is a graded connected Hopf algebra over a field $\k$ equipped with a character (multiplicative linear function) $\zeta\colon \mathcal{H} \rightarrow \k$ \cite{ABS}.
%(This definition was taken from COMBINATORIAL HOPF ALGEBRAS AND GENERALIZED DEHN-SOMMERVILLE RELATIONS MARCELO AGUIAR, NANTEL BERGERON, AND FRANK SOTTILE)
We define the character of the reduced incidence Hopf algebra to be the map $\zeta\colon \C[\mathcal{J}] \rightarrow \C$ defined on basis elements by $\zeta([J]) = 1$ for all $J$ and extended linearly.

These functions can similarly be defined on the free $\C$-module, $\C[\mathcal{P}]$, whose basis consists of isomorphism classes of posets $P$ in $\mathcal{P}$, the set of all finite posets:
\begin{align*}
\nabla([P_1] \otimes [P_2])&:= [P_1 \cup P_2],\\
%\[1_{\mathbf{k}[\mathcal{P}]} : = \varnothing\]
\Delta[P] &:= \sum_{I} [I] \otimes [P \setminus I],
\end{align*}
where the sum runs over all order ideals $I$ of $P$.
%\[
%\epsilon[P] := \left\{
%        \begin{array}{ll}
%            1 & \text{if } |P|=0, \\
%            0 & \text{otherwise.}
%        \end{array}
%    \right.
%\]
The corresponding character of $\C[\mathcal{P}]$ is $\zeta_{\mathcal{P}}\colon \C[\mathcal{P}] \rightarrow \C$ defined by $\zeta_{\mathcal P}(P) = 1$ for all $P$, extended linearly.
These functions all commute with the map $J$ that sends $P$ to $J(P)$, so $J$ is a Hopf isomorphism.

We can define the \textit{graded comultiplication} $\Delta_{k, n-k}[P]$ by
\[\Delta_{k, n-k}[P] := \sum_{\substack{I \subseteq P \\ |I| = k}} [I] \otimes [P \setminus I].\]

The map $K\colon \mathcal{P} \rightarrow \QSym$ that sends $P$ to the $P$-partition generating function $K_P(\mathbf{x})$ is the unique Hopf morphism that satisfies $\zeta_{\mathcal{P}} = \zeta_{\mathcal{Q}} \circ K$, where the character $\zeta_Q$ for $\QSym$ is the linear function that sends $L_n$ to $1$ and all other $L_\alpha$ to $0$.

%%%%%%%%%%
%NEW SECTION%
%%%%%%%%%%

\section{Necessary Conditions}

In this section, we will describe various necessary conditions for two naturally labeled posets to have the same partition generating function.

\subsection{Order ideals and antichains}
Recall that $\antikij(P)$ is defined to be the number of $k$-element order ideals of $P$ that cover $i$ elements in $J(P)$ and are covered by $j$ elements.

\begin{thm}\label{Anti}
If $\KP = \KQ$ then $\antikij(P) = \antikij(Q)$ for all triples $k, i, j$.
\end{thm}

\begin{proof}[Proof sketch]
There exists a linear function $\max_i\colon \QSym \rightarrow \Z$ such that
\[
\max\nolimits_i(\KP) = \left\{
        \begin{array}{ll}
            1 & \quad \text{if $P$ has exactly $i$ maximal elements,} \\
            0 & \quad \text{otherwise.}
        \end{array}
    \right.
\]
Explicitly, on the fundamental basis $\{L_\alpha\}$,
\[
\max\nolimits_i(L_{\alpha}) = \left\{
        \begin{array}{ll}
            (-1)^{(k-i+1)}\binom{k}{i-1} & \quad \text{if } \alpha = (n-k, \underbrace{1, 1, \dots, 1}_k),\\
            0 & \quad \text{otherwise.}
        \end{array}
    \right.
\]
Similarly, there exists a linear function $\min_i\colon \QSym \rightarrow \Z$ satisfying $\min_i(\KP) = 1$ if $P$ has exactly $i$ minimal elements, and $0$ otherwise.

%Observe that $\antikij(P)$ counts the number of order ideals $I$ such that $|I| = k$, $I$ has $i$ maximal elements, and $P\backslash I$ has $j$ minimal elements. It follows that
Then
\[\antikij(P) = ((\max\nolimits_i \otimes \min\nolimits_j) \circ \Delta_{k, n-k})(K_P(\mathbf{x})),\]
which depends only on $K_P(\mathbf{x})$.
\end{proof}

This shows that $\antikij(P)$ can be expressed as a linear combination of the coefficients of the fundamental basis expansion of $\KP$. In fact, if we order the compositions in lexicographic order, then the leading coefficient of $\antikij(P)$ is $c_{\alpha(k,i,j)}(P)$, where
%$\alpha = (k-i) \odot 1^i \odot 1^j \odot (n-k-j)$.
\begin{align*}
\alpha(k,i,j) &= \co([k-i+1,k+j-1]\setminus\{k\})\\
&= (k-i+1, \underbrace{1, \dots, 1}_{i-2}, 2, \underbrace{1, \dots, 1}_{j-2}, n-k-j-1),
\end{align*}
and all coefficients contributing to any $\antikij(P)$ have this form. One can then deduce the following result.

\begin{cor}
Let $c_\alpha(P)$ and $c_\alpha(Q)$ denote the coefficient of $L_\alpha$ in $\KP$ and $K_Q(\mathbf{x})$, respectively.  Then $\antikij(P) = \antikij(Q)$ for all triples $(k,i,j)$ if and only if $c_{\alpha(k,i,j)}(P) = c_{\alpha(k,i,j)}(Q)$ for all triples $(k,i,j)$.
\end{cor}

It follows that an easily counted property of $J(P)$ determines many of the coefficients in the fundamental basis expansion of $\KP$.

We also obtain as a corollary the following result, conjectured by McNamara and Ward \cite{McNamaraWard}.
\begin{cor}
If $\KP = \KQ$, then $P$ and $Q$ have the same number of antichains of size $i$ for all $i$.
\end{cor}
\begin{proof}
The number of antichains of size $i$ in $P$ is $\sum_{k,j} \antikij(P)$.
\end{proof}

\subsection{Shape}

Next, we show that the shape of the poset $P$ is determined by $\KP$, or more specifically, by its support.

\begin{thm} \label{shape}
If $\supp(\KP) = \supp(\KQ)$, then $\sh(P) = \sh(Q)$.
\end{thm}

\begin{proof}[Proof sketch]
Since $P$ is naturally labeled, elements $i < j$ form an antichain in $P$ if and only if there exists a linear extension of $P$ in which $j$ appears immediately before $i$.  This means that every descent in a linear extension of $P$ is formed by a $2$-element antichain, and similarly, if there is a linear extension of $P$ that has $i$ consecutive descents, then these elements form an $(i+1)$-element antichain in $P$. Hence $P$ has $k$ disjoint antichains of total size $a_k$ if and only if there is a linear extension of $P$ that has $k$ decreasing runs of total size $a_k$, which can be determined from $\supp(\KP)$.
\end{proof}

\begin{cor}
If $K_P(\mathbf{x}) = K_Q(\mathbf{x})$, then $\sh(P) = \sh(Q)$.
\end{cor}
\begin{proof}  Follows directly from the previous theorem.
\end{proof}


\subsection{Jump}

Let the \textit{jump} of an element $x$, denoted $\jump(x)$, be the maximum number of relations in a saturated chain from $x$ down to a minimal element.  %The \textit{jump sequence} of a naturally labeled poset $P$ is $\jump(P) = (j_0, \dots, j_k)$, where $j_i$ equals the number of elements with jump $i$, and $k$ is the maximum jump of any element.
McNamara and Ward \cite{McNamaraWard} prove that if two posets have the same partition generating function, then they must have the same number of elements of jump $i$ for any $i$ using the following result.
\begin{thm}[{\cite[Corollary 5.3]{McNamaraWard}}]
	If $P$ and $Q$ have the same partition generating function, then so do the induced subposets consisting of elements of jump at least $i$.
\end{thm}

A similar argument gives the following result.
\begin{thm}
	If $P$ and $Q$ have partition generating functions with the same support, then so do the induced subposets consisting of elements of jump at least $i$.
\end{thm}

%Note that in the case when $P$ and $Q$ are naturally labeled, the previous theorem on requires that $P$ and $Q$ have the same support.
%The jump sequence of a naturally labeled poset can be interpreted in terms of minimal elements.  Let $P_i$ denote the induced subposet of $P$ that consists of elements of $P$ with jump at least $i$.  Then $j_i$ is equal to the number of minimal elements of $P_i$.
We define the \textit{upward jump} of an element $x$, denoted $\upjump(x)$, to be the maximum number of relations in a saturated chain from $x$ up to a maximal element.  %Then the \textit{upward jump sequence} of a naturally labeled poset is $\upjump(P) = (l_0, \dots, l_k)$, where $l_i$ equals the number of elements with up-jump $i$.
We then define the \textit{jump pair} of $x$ to be $(\jump(x), \upjump(x))$.


%Let $P'_i$ denote the induced subposet of $P$ that consists of elements of $P$ with up-jump greater than or equal to $i$.  We can see that $j'_i$ is equal to the number of maximal elements of $P'_i$.


\begin{thm}
	If $\supp(\KP) = \supp(\KQ)$, then $P$ and $Q$ have the same number of elements with jump pair $(i, j)$ for all $i$ and $j$.
\end{thm}

\begin{proof}[Proof sketch]
	Let $P_{ij}$ be the induced subposet of $P$ consisting of all elements with jump at least $i$ and up-jump at least $j$. By the previous theorem and its dual, $\supp(K_{P_{ij}}(\mathbf x))$ is determined by $\supp(\KP)$, hence so is $|P_{ij}|$. This implies the result since the number of elements with jump pair $(i,j)$ is $|P_{ij}| - |P_{i+1,j}|-|P_{i,j+1}| + |P_{i+1,j+1}|$.
\end{proof}
%By removing maximal and minimal elements from a poset  we can generalize the concept of $jump$.

%\begin{defn}
%Let $\alpha$ be a length $k$ sequence of $0$s and $1$s.  Define $P_{\alpha}^i$ recursively by $P_{\alpha}^0 =P$ and, for $i>0$, 
%\[
%P_{\alpha}^i = 
%\left\{
%        \begin{array}{ll}
%            P_{\alpha}^{i-1}\setminus \{\text{minimal elements of $P_{\alpha}^{i-1}$}\} & \text{if } \alpha_i =0, \\
%            P_{\alpha}^{i-1}\setminus \{\text{maximal elements of $P_{\alpha}^{i-1}$}\} & \text{if } \alpha_i =1. 
%        \end{array}
%    \right.
%\]
%
%The \textit{$\alpha$-jump sequence of a poset}, denoted \textit{$\alpha$-jump($P$)} is \textit{$\alpha$-jump($P$)} $= (j_0, \dots j_k)$, where 
%\[
%j_i = 
%\left\{
%        \begin{array}{ll}
%            \textit{number of minimal elements of } P_{\alpha}^i & \text{if }\alpha_i = 0, \\
%            \textit{number of maximal elements of } P_{\alpha}^i & \text{if }\alpha_i =1.
%        \end{array}
%    \right.
%\]
%\end{defn}
%Note that if $\alpha = 0 \dots 0$, then $\alpha\text{-}jump(P) = jump(P)$.  Similarly, if $\alpha = 1 \dots 1$, then $\alpha\text{-}jump(P) = u\text{-}jump(P)$.

%\begin{thm}
%If $supp_L(\KP) = supp_L(K_Q(\mathbf{x}))$ then $\alpha\text{-}jump(P) = \alpha\text{-}jump(Q)$ for all sequences $\alpha$.
%\end{thm}

%\begin{proof}
%The number of minimal and maximal elements of $P$ are determined the supports.  We continue recursively by looking at the support of $P$ with either the minimal or maximal elements of $P$ removed.
%\end{proof}

%\begin{cor}
%If $\KP = \KQ$ then $\alpha\text{-}jump(P) = \alpha\text{-}jump(Q)$ for all sequences $\alpha$.
%\end{cor}

%The composition that did not get removed throughout the entire algorithm will be referred to as the \textit{$\alpha$-jump composition of $P$}.


%%%%%%%%%%
%NEW SECTION%
%%%%%%%%%%

\section{Uniqueness from shape}

Since Theorem~\ref{shape} shows that posets with the same generating function must have the same shape, one can ask for which shapes is a poset of that shape uniquely determined by its generating function. The next result shows that this is the case when $\lambda$ has at most two parts, that is, for posets of width 2.

\begin{thm}\label{width2}
Let $P$ and $Q$ be width $2$ posets.  Then $\KP =\KQ$ if and only if $P \cong Q$.
\end{thm}
\begin{proof}[Proof idea]
It is enough to show that the result holds for irreducible width 2 posets.  An irreducible width 2 poset must have exactly 2 minimal elements.  Suppose $P$ has minimal elements $x_0$ and $y_0$, and let $P' = P \backslash \{x_0,y_0\}$. Then $K_{P'}(\mathbf x)$ is determined from $K_P(\mathbf x)$, so $P'$ is determined up to isomorphism by induction. Thus it remains to determine how the minimal elements of $P$ compare to elements in $P'$.

To do this, we use the operations from the reduced incidence Hopf algebra. For instance, if there is a unique order ideal $I$ of $P$ isomorphic to a chain of size $a$, then
\[K_{P \setminus I}(\mathbf x) = (\zeta \otimes id)\Delta_{a, n-a}(\KP)- (\zeta \otimes id)\Delta_{a-2, n-a+2}(K_{P'}(\mathbf{x})),\]
so $P \setminus I$ is determined up to isomorphism by induction. This is typically enough to determine the entire structure of $P$ since we can often choose $a$ so that $P \setminus I$ is the dual order ideal generated by either $x_0$ or $y_0$. (The complete proof involves several cases of this form.)
\end{proof}
%Theorem \ref{width2} tells us that any poset $P$ whose shape $\lambda$ satisfies $\lambda_3 = 0$ has a unique $P$-partition generating function.

A partition $\lambda$ is a \emph{hook} if $\lambda_2 \leq1$, i.e., $\lambda = (\lambda_1, 1, 1, \dots, 1)$.  If $sh(P)$ is a hook, then we say that the poset $P$ is \emph{hook-shaped}.

\begin{thm}\label{Hook}
If $\sh(P)$ is a hook and $\supp(\KP) = \supp(\KQ)$, then $P \cong Q$.
\end{thm}
%This theorem can be stronger.  Only the supports have to be the same.

\begin{proof}[Proof sketch]
If $P$ is hook-shaped, then it is completely determined by the jump pairs of its elements.
\end{proof}



\begin{example}
Consider the following two hook shaped posets.

\begin{center}

\begin{tikzpicture}
 [auto,
 vertex/.style={circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=1mm}, scale = .58]
\node(P) at (-2, 6) {$P =$};
\node (1) at (0,0) [vertex,label=left:$1$] {};
\node (2) at (0,1) [vertex,label=left:$2$] {};
\node (3) at (0,2) [vertex,label=left:$3$] {};
\node (4) at (0,3) [vertex,label=left:$4$] {};
\node (5) at (1,3) [vertex,label=left:$5$] {};
\node (6) at (2,3) [vertex,label=left:$6$] {};
\node (7) at (3,3) [vertex,label=left:$7$] {};
\node (8) at (4,3) [vertex,label=left:$8$] {};
\node (9) at (5,3) [vertex,label=left:$9$] {};
\node (10) at (0,4) [vertex,label=left:$10$] {};
\node (11) at (0,5) [vertex,label=left:$11$] {};
\node (12) at (0,6) [vertex,label=left:$12$] {};
\node (13) at (0,7) [vertex,label=left:$13$] {};
\draw [-] (1) to (2);
\draw [-] (1) to (9);
\draw [-] (2) to (7);
\draw [-] (2) to (8);
\draw [-] (2) to (3);
\draw [-] (3) to (4);
\draw [-] (3) to (5);
\draw [-] (3) to (6);
\draw [-] (4) to (10);
\draw [-] (5) to (10);
\draw [-] (6) to (12);
\draw [-] (7) to (13);
\draw [-] (8) to (13);
\draw [-] (9) to (11);
\draw [-] (10) to (11);
\draw [-] (11) to (12);
\draw [-] (12) to (13);
\end{tikzpicture}
\begin{tikzpicture}
 [auto,
 vertex/.style={circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=1mm}, scale = .58]
\node(Q) at (-2, 6) {$Q =$};
\node (1) at (0,0) [vertex,label=left:$1$] {};
\node (2) at (0,1) [vertex,label=left:$2$] {};
\node (3) at (0,2) [vertex,label=left:$3$] {};
\node (4) at (0,3) [vertex,label=left:$4$] {};
\node (5) at (1,3) [vertex,label=left:$5$] {};
\node (6) at (2,3) [vertex,label=left:$6$] {};
\node (7) at (3,3) [vertex,label=left:$7$] {};
\node (8) at (4,3) [vertex,label=left:$8$] {};
\node (9) at (5,3) [vertex,label=left:$9$] {};
\node (10) at (0,4) [vertex,label=left:$10$] {};
\node (11) at (0,5) [vertex,label=left:$11$] {};
\node (12) at (0,6) [vertex,label=left:$12$] {};
\node (13) at (0,7) [vertex,label=left:$13$] {};
\draw [-] (1) to (2);
\draw [-] (1) to (9);
\draw [-] (2) to (7);
\draw [-] (2) to (8);
\draw [-] (2) to (3);
\draw [-] (3) to (4);
\draw [-] (3) to (5);
\draw [-] (3) to (6);
\draw [-] (4) to (10);
\draw [-] (5) to (10);
\draw [-] (6) to (12);
\draw [-] (7) to (13);
\draw [-] (8) to (11);
\draw [-] (9) to (13);
\draw [-] (10) to (11);
\draw [-] (11) to (12);
\draw [-] (12) to (13);
\end{tikzpicture}
\end{center}
These posets have different generating functions because the element $9 \in P$ has jump 1 and upward jump 3, but no element of $Q$ does.
\end{example}

We also consider posets $P$ whose shape is nearly a hook, namely for which $\sh(P) = (\lambda_1, 2, 1, \dots, 1)$.  

\begin{thm}\label{NearHook}
Suppose $\sh(P) = \sh(Q) = (\lambda_1, 2, 1, \dots, 1)$.  Then $\KP = \KQ$ if and only if $P \cong Q$.
\end{thm}

Although the posets in Theorem~\ref{NearHook} are very similar to
hook-shaped posets, this theorem requires much more care to prove due to
various subtleties. For instance, Theorem \ref{Hook} only requires that
$\supp(P) = \supp(Q)$ whereas Theorem \ref{NearHook} requires that $\KP =
\KQ$.  Indeed, there exist pairs of non-isomorphic posets of shape $(\lambda_1, 2, 1, \dots, 1)$ whose generating functions have the same support (but which are necessarily different).

For most of the remaining shapes, we present a negative result in the next section.

%%%%%%%%%%
%NEW SECTION%
%%%%%%%%%%

\section{Posets with the same $P$-partition generating function}

In this section, we give a method for constructing distinct posets with the same generating function.

Given a poset $P$ and a pair of incomparable elements $(x, y)$, write $P+(x \prec y)$ for the poset obtained by adding the relation $x \prec y$ to $P$ (and taking the transitive closure).

\begin{lem}\label{Kequiv}
Suppose $R$ is a finite poset with an automorphism $\phi\colon R \rightarrow R$. Let $e=(e_1, e_2)$ and $f=(f_1, f_2)$ be two pairs of incomparable elements of $R$ such that in $R+(f_2 \prec f_1)$, both $e_1\prec e_2$ and $\phi(e_1)\prec \phi(e_2)$. Then $\KP=\KQ$, where
\begin{align*}
P &= R+(f_1 \prec f_2) + (e_1 \prec e_2),\text{ and}\\
Q &= R+(f_1 \prec f_2) + (\phi(e_1) \prec \phi(e_2)),
\end{align*}
assuming both are naturally labeled.
%Let $e$ be the covering relation $e_1 \prec e_2$ and $f$ be the covering relation $f_1 \prec f_2$ and assume that adding these relations to $R$ do not make a cycle.  Let $m>0$ be the the smallest number such that $\phi^{m+1}(e) = e$.  Let $P = R + e + \phi(e) + \dots + \phi^{m-1}(e) +f$ and $Q = R + \phi(e) + \dots + \phi^m(e) + f$. If the relations $e = e_1 \prec e_2$ and $\phi^m(e) = \phi^m(e_1) \prec \phi^m(e_2)$ are no longer covering relations when $f' = f_2 \prec f_1$ is added to $P-f$ or $Q - f$, then $P$ and $Q$ are $K$-equivalent.
\end{lem}

\begin{proof}[Proof sketch]
	The linear extensions of $P$ are precisely those of $R + (e_1 \prec e_2)$ except for those of $R+(e_1 \prec e_2) + (f_2 \prec f_1) = R+(f_2 \prec f_1)$. Similarly, the linear extensions of $Q$ are those of $R + (\phi(e_1) \prec \phi(e_2)) \cong R+(e_1 \prec e_2)$ except for those of $R+(f_2 \prec f_1)$. Hence $\KP$ and $\KQ$ are both equal to the difference of $K_{R+(e_1 \prec e_2)}(\mathbf x)$ and $K_{R+(f_2 \prec f_1)}(\mathbf x)$ (taking care that $R + (f_2 \prec f_1)$ is not naturally labeled).
\end{proof}
(One can also formulate a more general version of this result in which more relations are added.)
	
%Suppose $P$ and $Q$ are defined as they are above.  Suppose $f$ is the relation $x \prec y$.  Let $S$ be the poset formed by removing the relation $x \prec y$ from $P$.  Every linear extension of $S$ is either a linear extension of $P$ or a linear extension of $S + f'$.  That is to say, $K_S(\mathbf{x}) = \KP + K_{S + f'}(\mathbf{x})$. Solving for $\KP$ we have, $\KP = K_S(\mathbf{x}) - K_{S + f'}(\mathbf{x})$.
%
%Similarly, let $S'$ be the poset formed by removing the relation $x \prec y$ from $Q$.  The linear extension of $Q$ are the linear extensions of $S'$ with the linear extensions of $S' + f'$ removed.  That is to say, $K_{S'}(\mathbf{x}) = \KQ + K_{S' + f'}(\mathbf{x})$. Solving for $\KQ$ we have, $\KQ = K_{S'}(\mathbf{x}) - K_{S' + f'}(\mathbf{x})$.
%
%Notice that $S = R  + e + \phi(e) + \dots + \phi^{m-1}(e)$ and $S' = R + \phi(e) + \dots + \phi^m(e)$ so $S \cong S'$ since $S' = \phi(S)$ meaning $S$ and $S'$ are $K$-equivalent.
%
%Since when you add the relation $f'$ to $R$ the relations $e$ and $\phi^m(e)$ are implied,
%\[S + f' = R + e + \phi(e) + \dots + \phi^{m-1}(e) +f' = R + \phi(e) + \dots + \phi^{m-1}(e) +f'\]
%and
%\[S' + f' = R + \phi(e) + \dots + \phi^{m}(e) +f' = R + \phi(e) + \dots + \phi^{m-1}(e) +f'.\]
%These are clearly isomorphic so they are $K$-equivalent.
%
%Therefore $P$ and $Q$ are $K$-equivalent.
%\end{proof}
\begin{example}\label{sevenelement}
Consider the following $7$-element posets.  The posets $P_7$ and $Q_7$ are not isomorphic but they are $K$-equivalent.
\begin{center}
\begin{tikzpicture}
 [auto,
 vertex/.style={circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=1mm}]
\node(P) at (-2, 1) {$P_7 =$};
\node (v1) at ( 0,0) [vertex,label=left:$1$] {};
\node (v2) at ( 1,0) [vertex,label=left:$2$] {};
\node (v3) at ( -1,1) [vertex,label=left:$3$] {};
\node (v4) at ( 0,1) [vertex,label=left:$4$] {};
\node (v5) at ( 1,1) [vertex,label=left:$5$] {};
\node (v6) at ( 0,2) [vertex,label=left:$6$] {};
\node (v7) at ( 1,2) [vertex,label=left:$7$] {};
\draw [-] (v1) to (v4);
\draw [-] (v4) to (v6);
\draw [-] (v2) to (v5);
\draw [-] (v5) to (v7);
\draw [-] (v1) to (v3);
\draw [-] (v3) to (v6);
\draw [-] (v1) to (v7);
\draw [-] (v2) to (v6);
\end{tikzpicture}
\hspace{1 cm}
\begin{tikzpicture}
 [auto,
 vertex/.style={circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=1mm}]
\node(Q) at (2, 1) {$Q_7 =$};
\node (v1) at ( 4,0) [vertex,label=left:$1$] {};
\node (v2) at ( 5,0) [vertex,label=left:$2$] {};
\node (v3) at ( 3,1) [vertex,label=left:$3$] {};
\node (v4) at ( 4,1) [vertex,label=left:$4$] {};
\node (v5) at ( 5,1) [vertex,label=left:$5$] {};
\node (v6) at ( 4,2) [vertex,label=left:$6$] {};
\node (v7) at ( 5,2) [vertex,label=left:$7$] {};
\draw [-] (v1) to (v4);
\draw [-] (v4) to (v6);
\draw [-] (v2) to (v5);
\draw [-] (v5) to (v7);
\draw [-] (v1) to (v3);
\draw [-] (v3) to (v7);
\draw [-] (v2) to (v6);
\end{tikzpicture}
\hspace{1 cm}
\begin{tikzpicture}
 [auto,
 vertex/.style={circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=1mm}]
\node(R) at (-2, 1) {$R =$};
\node (v1) at ( 0,0) [vertex,label=left:$1$] {};
\node (v2) at ( 1,0) [vertex,label=left:$2$] {};
\node (v3) at ( -1,1) [vertex,label=left:$3$] {};
\node (v4) at ( 0,1) [vertex,label=left:$4$] {};
\node (v5) at ( 1,1) [vertex,label=left:$5$] {};
\node (v6) at ( 0,2) [vertex,label=left:$6$] {};
\node (v7) at ( 1,2) [vertex,label=left:$7$] {};
\draw [-] (v1) to (v4);
\draw [-] (v4) to (v6);
\draw [-] (v2) to (v5);
\draw [-] (v5) to (v7);
%\draw [-] (v1) to (v3);
%\draw [-] (v3) to (v6);
\draw [-] (v1) to (v7);
\draw [-] (v2) to (v6);
\end{tikzpicture}

\end{center}

We can express $P_7$ and $Q_7$ in terms of the poset $R$ with a nontrivial automorphism along with some additional covering relations.

The automorphism $\phi$ is the map that fixes $3$ and swaps the two chains, $e = (3,6)$, and $f = (1,3)$.  Note that $\phi(e) = (3,7)$, and adding the relation $3 \prec 1$ to $R$ makes both $3 \prec 6$ and $3 \prec 7$. By Lemma \ref{Kequiv}, we have $K_{P_7}(\mathbf{x}) = K_{Q_7}(\mathbf{x})$.
\end{example}

\begin{example}\label{cycle}
Consider the following $8$-element posets.

\begin{center}
\begin{tikzpicture}
 [auto,
 vertex/.style={circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=1mm}]
\node(P) at (-1, .5) {$P_8 =$};
\node (1) at ( 0,0) [vertex,label=left:$1$] {};
\node (2) at ( 1,0) [vertex,label=left:$2$] {};
\node (3) at ( 2,0) [vertex,label=left:$3$] {};
\node (4) at ( 3,0) [vertex,label=left:$4$] {};
\node (5) at ( 0,1) [vertex,label=left:$5$] {};
\node (6) at ( 1,1) [vertex,label=left:$6$] {};
\node (7) at ( 2,1) [vertex,label=left:$7$] {};
\node (8) at (3, 1) [vertex,label=left:$8$] {};
\draw [-] (1) to (5);
\draw [-] (1) to (8);
\draw [-] (2) to (5);
\draw [-] (2) to (6);
\draw [-] (3) to (6);
\draw [-] (3) to (7);
\draw [-] (4) to (7);
\draw [-] (4) to (8);
\draw [-] (1) to (6);
\draw [-] (3) to (5);
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}
 [auto,
 vertex/.style={circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=1mm}]
\node(Q) at (-1, .5) {$Q_8 =$};
\node (1) at ( 0,0) [vertex,label=left:$1$] {};
\node (2) at ( 1,0) [vertex,label=left:$2$] {};
\node (3) at ( 2,0) [vertex,label=left:$3$] {};
\node (4) at ( 3,0) [vertex,label=left:$4$] {};
\node (5) at ( 0,1) [vertex,label=left:$5$] {};
\node (6) at ( 1,1) [vertex,label=left:$6$] {};
\node (7) at ( 2,1) [vertex,label=left:$7$] {};
\node (8) at (3, 1) [vertex,label=left:$8$] {};
\draw [-] (1) to (5);
\draw [-] (1) to (8);
\draw [-] (2) to (5);
\draw [-] (2) to (6);
\draw [-] (3) to (6);
\draw [-] (3) to (7);
\draw [-] (4) to (7);
\draw [-] (4) to (8);
\draw [-] (2) to (7);
\draw [-] (3) to (5);
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}
[auto,
vertex/.style={circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=1mm}]
\node(R) at (-1, .5) {$R =$};
\node (1) at ( 0,0) [vertex,label=left:$1$] {};
\node (2) at ( 1,0) [vertex,label=left:$2$] {};
\node (3) at ( 2,0) [vertex,label=left:$3$] {};
\node (4) at ( 3,0) [vertex,label=left:$4$] {};
\node (5) at ( 0,1) [vertex,label=left:$5$] {};
\node (6) at ( 1,1) [vertex,label=left:$6$] {};
\node (7) at ( 2,1) [vertex,label=left:$7$] {};
\node (8) at (3, 1) [vertex,label=left:$8$] {};
\draw [-] (1) to (5);
\draw [-] (1) to (8);
\draw [-] (2) to (5);
\draw [-] (2) to (6);
\draw [-] (3) to (6);
\draw [-] (3) to (7);
\draw [-] (4) to (7);
\draw [-] (4) to (8);
\end{tikzpicture}
\end{center}

The automorphism $\phi$ is the permutation $(1234)(5678)$, $e = (1,6)$, $\phi(e) = (2,7)$, and $f=(3,5)$. Adding the relation $5 \prec 3$ to $R$ implies both $1 \prec 6$ and $2 \prec 7$, so once again, Lemma \ref{Kequiv} implies $K_{P_8}(\mathbf{x}) = K_{Q_8}(\mathbf{x})$.
\end{example}

Observe that the posets in Example \ref{sevenelement} have shape $(3, 3, 1)$, and the posets in Example \ref{cycle} have shape $(2, 2, 2, 2)$.  We can generalize these examples to make pairs of posets of larger shapes that are $K$-equivalent.

\begin{thm}
For all partitions $\lambda$ with $\lambda \supset (3, 3, 1)$ or $\lambda \supset (2, 2, 2, 2)$, there exist posets $P$ and $Q$ such that $P \ncong Q$, $\sh(P)=\sh(Q) = \lambda$, and $\KP = \KQ$.
\end{thm}

\begin{proof}[Proof sketch]
We base our construction off of the posets $P_7$ and $Q_7$ from Example \ref{sevenelement} and posets $P_8$ and $Q_8$ from Example \ref{cycle}.
Observe that if $\sh(P) = \mu = (\mu_1, \dots, \mu_k)$ and $\sh(Q) = \nu = (\nu_1, \dots, \nu_l)$, then
\begin{align*}
\sh(P \oplus Q) &= \mu + \nu = (\mu_1+\nu_1, \mu_2+\nu_2, \dots ),\\
\sh(P \cup Q) &= \mu \cup \nu = (\mu_1'+\nu_1', \mu_2'+\nu_2', \dots )',
\end{align*}
(where $\mu'$ and $\nu'$ are the conjugate partitions of $\mu$ and $\nu$, respectively).
%We will prove this result by building off of the posets $P_7$ and $Q_7$ from Example \ref{sevenelement} and posets $P_8$ and $Q_8$ from Example \ref{cycle}.
%Let $P_7$ and $Q_7$ be the $7$-element posets from Example \ref{sevenelement}, and let $P_8$ and $Q_8$ be the $8$-element posets from Example \ref{cycle}.

Suppose first that $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_k)$ is a partition that contains $(3, 3, 1)$.  %We first form two $K$-equivalent posets that have shape $(\lambda_1, \lambda_2, \lambda_3)$ and then take the disjoint union with disjoint chains of sizes $\lambda_4, \lambda_5, \dots, \lambda_k$.
Consider the following posets:

\begin{tikzpicture}
 [auto,
 vertex/.style={circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=1mm}]
\node(P) at (-2, 2) {$P' =$};
\node (v1) at ( 0,0) [vertex,label=left:$$] {};
\node (v2) at ( 1,0) [vertex,label=left:$$] {};
\node (v3) at ( -1,1) [vertex,label=left:$$] {};
\node (v4) at ( 0,.4) [vertex,label=left:$$] {};
\node (v5) at ( 1,.4) [vertex,label=left:$$] {};
\node (v6) at ( 0,2) [vertex,label=left:$$] {};
\node (v7) at ( 1,2) [vertex,label=left:$$] {};
\node (v8) at (-1,.5) [vertex] {};
\node (v9) at (-1,1.5) [vertex] {};
\node (v10) at (.5, 2.5) [vertex] {};
\node (v11) at (.5, 3) [vertex] {};
\draw [-] (v1) to (v4);
\draw [dashed] (v4) to (v6);
\draw [-] (v2) to (v5);
\draw [dashed] (v5) to (v7);
\draw [-] (v1) to (v3);
\draw [-] (v3) to (v6);
\draw [-] (v1) to (v7);
\draw [-] (v2) to (v6);
\draw [dashed] (v8) to (v3);
\draw [dashed] (v3) to (v9);
\draw [-] (v6) to (v10);
\draw [-] (v7) to (v10);
\draw [dashed] (v10) to (v11);
\draw [decorate,decoration={brace,amplitude=5pt},xshift=-4pt,yshift=0pt]
(-1.1,.5) -- (-1.1,1.5) node [black,midway,xshift=-0.2cm] 
{\footnotesize $\lambda_3$};
\draw [decorate,decoration={brace,amplitude=5pt,mirror,raise=4pt},yshift=0pt]
(1.1,0) -- (1.1,2) node [black,midway,xshift=0.9cm] {\footnotesize
$\lambda_2$};
\draw [decorate,decoration={brace,amplitude=2pt,mirror,raise=4pt},yshift=0pt]
(.55,2.5) -- (.55,3) node [black,midway,xshift=1.6cm] {\footnotesize
$\lambda_1 - \lambda_2$};
\end{tikzpicture}
\hspace{3 cm}
\begin{tikzpicture}
 [auto,
 vertex/.style={circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=1mm}]
\node(Q) at (-2, 2) {$Q' =$};
\node (v1) at ( 0,0) [vertex,label=left:$$] {};
\node (v2) at ( 1,0) [vertex,label=left:$$] {};
\node (v3) at ( -1,1) [vertex,label=left:$$] {};
\node (v4) at ( 0,.4) [vertex,label=left:$$] {};
\node (v5) at ( 1,.4) [vertex,label=left:$$] {};
\node (v6) at ( 0,2) [vertex,label=left:$$] {};
\node (v7) at ( 1,2) [vertex,label=left:$$] {};
\node (v8) at (-1,.5) [vertex] {};
\node (v9) at (-1,1.5) [vertex] {};
\node (v10) at (.5, 2.5) [vertex] {};
\node (v11) at (.5, 3) [vertex] {};
\draw [-] (v1) to (v4);
\draw [dashed] (v4) to (v6);
\draw [-] (v2) to (v5);
\draw [dashed] (v5) to (v7);
\draw [-] (v1) to (v3);
\draw [-] (v3) to (v7);
\draw [-] (v2) to (v6);
\draw [dashed] (v8) to (v3);
\draw [dashed] (v3) to (v9);
\draw [-] (v6) to (v10);
\draw [-] (v7) to (v10);
\draw [dashed] (v10) to (v11);
\draw [decorate,decoration={brace,amplitude=5pt},xshift=-4pt,yshift=0pt]
(-1.1,.5) -- (-1.1,1.5) node [black,midway,xshift=-0.2cm] 
{\footnotesize $\lambda_3$};
\draw [decorate,decoration={brace,amplitude=5pt,mirror,raise=4pt},yshift=0pt]
(1.1,0) -- (1.1,2) node [black,midway,xshift=0.9cm] {\footnotesize
$\lambda_2$};
\draw [decorate,decoration={brace,amplitude=2pt,mirror,raise=4pt},yshift=0pt]
(.55,2.5) -- (.55,3) node [black,midway,xshift=1.6cm] {\footnotesize
$\lambda_1 - \lambda_2$};
\end{tikzpicture}

Since $\lambda_2 \geq 3$, $P' \ncong Q'$.  It follows from Lemma \ref{Kequiv} that $P'$ and $Q'$ are $K$-equivalent.  Note that $\sh(P') = \sh(Q')= (\lambda_1, \lambda_2, \lambda_3)$. Taking the disjoint union of either $P'$ or $Q'$ with disjoint chains of lengths $\lambda_4$, $\lambda_5$, \dots gives the result.
%
% Let $R$ be the poset of disjoint chains of sizes $\lambda_4, \lambda_5, \dots, \lambda_k$. Let $P = P' \cup R$ and $Q = Q' \cup R$.  These posets have the desired shape and since $K_{P'}(\mathbf{x}) = K_{Q'}(\mathbf{x})$ it follows that $\KP = \KQ$.

If $\lambda \supset (2, 2, 2, 2)$, then we can take the ordinal sum of either $P_8$ or $Q_8$ with a union of chains of sizes $\lambda_1-2$, \dots, $\lambda_4-2$, and then take the disjoint union with a union of chains of sizes $\lambda_5$, $\lambda_6$, \dots.
%a similar construction but we build off of $K$-equivalent posets of shape $(2, 2, 2, 2)$.
%Now suppose $\lambda \supset (2, 2, 2, 2)$ but it does not contain $(3, 3, 1)$.  This means $\lambda = (\lambda_1, 2^j, 1^l)$.  Suppose $\lambda$ had $j$ parts of size $2$ and $l$ parts of size $1$.    Let $C$ be the $\lambda_1 - 2$ element chain and let $R$ be the poset with $j-3$ disjoint $2$-element chains and $l$ disjoint single elements.
%Let $P = (P_8 \oplus C) \cup R$ and let $Q = (Q_8 \oplus C) \cup R$.  These posets have the desired shape and since $P_8$ and $Q_8$ are $K$-equivalent, $\KP = \KQ$.
\end{proof}

The only remaining shapes for which it is not known whether there exist non-isomorphic $K$-equivalent posets are those of the form $(\lambda_1, 2, 2, 1, 1, 1, \dots)$.

\begin{question}
	Do there exist non-isomorphic posets of shape $\lambda$ with $\lambda_2=\lambda_3=2$ and $\lambda_4<2$ that are $K$-equivalent?
\end{question}

%\lipsum[3]

%\begin{equation}\label{eqn:eq1}
%\int_0^\infty \exp(-x)dx = 1.
%\end{equation}

%\begin{lem}\label{lem:lem1}
%\lipsum[11]
%\end{lem}

%\lipsum[10]

%\begin{figure}
%\centering
%\includegraphics[width=0.5\textwidth]{plot}
%\caption{A plot of a function.}
%\label{fig:plot}
%\end{figure}

%\subsection{A subsection}

%\lipsum[5]

%\begin{align*}
%1 + 1 + 1 &= 2 + 1 \\ &= 3.
%\end{align*}

%\subsubsection{A subsubsection}

%\lipsum[17]

%Here is a citation~\cite{greenwade93} with URL. Here is another
%citation~\cite{MR4}, which is the earliest-numbered Math Review with a
%functioning DOI: MR0000004. Finally, a reference to
%equation~\eqref{eqn:eq1}. And a reference to Figure~\ref{fig:plot}.

%\acknowledgements{\lipsum[20]}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
