\documentclass[ALCO]{cedram} \usepackage{ytableau,shuffle} \usepackage[enableskew,vcentermath]{youngtab} \usepackage{latexsym,amsmath,amssymb,verbatim,tikz,tikz-cd} \usepackage{mathtools} \usepackage{graphicx,xcolor,accents} \usepackage[english]{babel} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{graphicx} \usepackage{csquotes} \usepackage{shuffle} \usepackage{bm} \usepackage{bbm} \usepackage{enumitem} \usepackage{subcaption} \usepackage{caption} \renewcommand{\thesubfigure}{\Alph{subfigure}} \usepackage{dirtytalk} \newcommand{\sym}{\mathrm{Sym}} \newcommand{\qsym}{\mathrm{QSym}} \newcommand{\Des}{\operatorname{Des}} \newcommand{\Asc}{\operatorname{Asc}} \newcommand{\Syt}{\operatorname{SYT}} \newcommand{\Short}{\operatorname{Short}} \newcommand{\Loop}{\operatorname{Loop}} \newcommand{\Stable}{\operatorname{Stable}} \newcommand{\len}{\operatorname{len}} \newcommand{\height}{\operatorname{height}} \newcommand{\core}{\operatorname{core}} \newcommand{\res}{\operatorname{res}} \newcommand{\row}{\operatorname{row}} \newcommand{\insrt}{\operatorname{insert}} \newcommand{\UP}{\operatorname{UP}} \newcommand{\DOWN}{\operatorname{DOWN}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\NN}{\mathbb{N}} \newcommand{\RR}{\mathbb{R}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\PP}{\mathbb{P}} \newcommand{\F}{\mathcal{F}} \newcommand{\Q}{\mathcal{Q}} \newcommand{\A}{\mathcal{A}} \newcommand{\M}{\mathcal{M}} \newcommand{\I}{\mathcal{I}} \newcommand{\PM}{\mathcal{PM}} \newcommand{\Pcal}{\mathcal{P}} \newcommand{\odds}{\mathrm{odds}} \makeatletter \newcommand{\proofstep}[1]{% \par% \addvspace{\medskipamount}% \textbf{#1\@addpunct{.}}\enspace\ignorespaces } \newcommand\restr[2]{{% \left.\kern-\nulldelimiterspace % #1 % \vphantom{\big|} % \right|_{#2} % }} \makeatother \title{Schur-positivity of short chords in matchings} \author{\firstname{Avichai} \lastname{Marmor}} \address{Department of Mathematics\\ Bar-Ilan University\\ Ramat-Gan 52900\\ Israel} \email{avichai@elmar.co.il} \thanks{Partially supported by the Israel Science Foundation, Grant No.\ 1970/18, and by the European Research Council under the ERC starting grant agreement No.\ 757731 (LightCrypt).} \keywords{Quasi-symmetric function, Schur-positive set, symmetric function, pattern avoidance, matchings, Bessel polynomials} %% Mathematical classification (2000) %% This will not be printed but can be useful for database search \subjclass{20C30, 05A19, 05E05} \begin{document} \newtheorem{observation}[cdrthm]{Observation} \newtheorem{problem}[cdrthm]{Problem} \newtheorem*{problem*}{Problem} \begin{abstract} We prove that the set of matchings with a fixed number of unmatched vertices is Schur-positive with respect to the set of short chords. Two proofs are presented. The first proof applies a new combinatorial criterion for Schur-positivity, % while the second is bijective. The coefficients in the Schur expansion are derived, and interpreted in terms of Bessel polynomials. Then, we present a variant of Knuth equivalence for matchings, and show that every equivalence class corresponds to a Schur function. We proceed to find various refined Schur-positive sets, including the set of matchings with a prescribed crossing number and the set of matchings with a given number of pairs of intersecting chords. Finally, we characterize all the matchings $m$ such that the set of matchings avoiding $m$ is Schur-positive. \end{abstract} \maketitle %\tableofcontents \section{Introduction} \label{sec:introduction} Denote the set of nonnegative integers by $\NN$, and the set of positive integers by $\PP$. Given $N\in \NN$ and a set $\A$, together with a set-valued function $D:\A\to 2^{[N-1]}$ which is sometimes called a \emph{statistic}, we define its quasisymmetric generating function \[ \Q_{D} (\A) = \sum_{a \in \A} F_{N, D(a)}, \] where $F_{N, S}$ is the \emph{fundamental quasisymmetric function} introduced by Gessel~\cite{knuth_classes_schur_positive}, indexed by a subset $S \subseteq [N-1]$ (see Section~\ref{subsec:definitions symmetric functions} for more background). We write $\Q(\A)$ instead of $\Q_{D}(\A)$ when $D$ is clear from the context. The following long-standing problem was first addressed in~\cite{gessel1993counting}. \begin{problem}[Gessel and Reutenauer] Find sets $\A$ and statistics $D$ for which $\Q_{D}(\A)$ is symmetric. \end{problem} When $\Q_{D}(\A)$ is symmetric, we say that $\A$ is symmetric with respect to the statistic $D$ (we omit $D$ when it is clear from the context). If $\A$ is symmetric, then there is a unique expansion \[ \Q_{D} (\A) = \sum_{\lambda \vdash N} c_\lambda s_\lambda, \] where $c_\lambda \in \QQ$ and $s_\lambda$ are Schur functions (discussed in Section~\ref{subsec:definitions symmetric functions}). The coefficients $c_\lambda$ are called the \emph{Schur coefficients} of $\A$. If $c_\lambda \in \NN$ for all $\lambda \vdash N$, we say that $\A$ is Schur-positive with respect to $D$. Gessel and Reutenauer also addressed the following problem: \begin{problem} Find Schur-positive sets $\A$. \end{problem} The study of symmetric functions is partially motivated by the correspondence between symmetric functions of degree $N$ and class functions on the symmetric group $S_N$, which is established through the Frobenius characteristic map described in~\cite[Chapter 4.7]{sagan_book}. A symmetric function is Schur-positive if its corresponding class function is a proper character (see~\cite{adin_roichman_fine_set} for a detailed explanation). This perspective provides a rich algebraic framework for studying symmetric and Schur-positive sets. During the last few decades, many Schur-positive subsets of the symmetric group $S_N$ were constructed with respect to the standard descent function of $S_N$, where a permutation $\pi \in S_N$ has $i \in \Des(\pi)$ if and only if $\pi(i) > \pi(i+1)$. A fundamental construction is due to Gessel~\cite{knuth_classes_schur_positive}, who proved that every set of permutations which is closed under the Knuth equivalence relations is Schur-positive. Furthermore, he showed that every Knuth class $\A \subset S_N$ (\ie equivalence class of the Knuth relations) satisfies $\Q_{\Des}(\A) = s_\lambda$ for some $\lambda \vdash N$. This result has many direct consequences. For example, for every $J \subseteq [N-1]$, the set $D_{N,J}^{-1} = \{ \pi^{-1} \mid \Des(\pi)=J\} \subseteq S_N$ is Schur-positive because it is closed under the Knuth relations. Other examples of Schur-positive sets of permutations include all conjugacy classes, as proven by Gessel and Reutenauer~\cite{gessel1993counting}, and the set of permutations $\pi \in S_N$ with a fixed number of inversions (\ie $i \pi(j)$), a result demonstrated by Adin and Roichman \cite[Prop.\ 9.5]{adin_roichman_fine_set}. Some Schur-positive sets that do not consist of permutations were found as well. For instance, Gessel~\cite{knuth_classes_schur_positive} proved that for every partition $\lambda \vdash N$, the set $\Syt(\lambda)$ of standard Young tableaux of shape $\lambda$ is Schur-positive (see Section~\ref{subsec:schur positive sets} for details). In this work, we focus on the set of matchings of a given set of vertices. \begin{definition} \label{def:matching} A matching $m$ on a finite set of vertices $S \subseteq \PP$ is an unordered partition of $S$ into blocks, each block of size $1$ or $2$. If a block of a matching $m$ contains only the vertex $i$, we say that $i$ is an \emph{unmatched vertex} of $m$ and denote $(i) \in m$. If a block contains both $i$ and $j$ for $i 0$. Thus, the proof will be completed when we establish Equation~\eqref{eqn:first proof no consecutive indices is schur positive - odds set}. Denote $\A_1 = \{a \in \A \mid 1\in D(a)\}$. Furthermore, define a new statistic $D_1:\A_1 \to 2^{[N-3]}$ by $D_1(a) = (D(a)\setminus\{1\})-2$. Notice that $\A_1$ satisfies the requirements of Lemma~\ref{lem:if sparse and good sizes then schur positive two rows} with respect to $D_1$, where $N$ is replaced by $N-2$. Therefore, we may assume, by the induction hypothesis, that Lemma~\ref{lem:if sparse and good sizes then schur positive two rows} holds for $\A_1$. Thus, we can apply Equation~\eqref{eqn:first proof no consecutive indices is schur positive - set containment} for $\A_1$, while replacing $c_k$ with $|\A_1(D_1 = \odds(k))| = |\A(D = \odds(k+1))| = c_{k+1}$, and obtain \begin{equation}\label{eqn:first proof no consecutive indices is schur positive - induction} \left|\A_1(D_1 \supseteq J)\right| = \sum_{k=0}^{n-1} c_{k+1} \left|\Syt(N-2-k,k)(\Des \supseteq J)\right|. \end{equation} If we substitute $J = \odds(i-1)$ into Equation~\ref{eqn:first proof no consecutive indices is schur positive - induction}, we obtain \[ \left|\A_1(D_1 \supseteq \odds(i-1))\right| = \sum_{k=0}^{n-1} c_{k+1} \left|\Syt(N-2-k,k)(\Des \supseteq \odds(i-1))\right|. \] Notice that $\left|\A_1(D_1 \supseteq \odds(i-1))\right| = \left|\A(D \supseteq \odds(i))\right|$. Moreover, by Lemma~\ref{lem:remove first descent from syt}, the number of tableaux $T$ of shape $(N-k-1,k-1)$ with $\Des(T) \supseteq \odds(i-1)$ is equal to the number of tableaux $T$ of shape $(N-k,k)$ with $\Des(T) \supseteq \odds(i)$. Therefore, we can reformulate the equation and obtain that \[ \left|\A(D \supseteq \odds(i))\right| = \sum_{k=1}^{n} c_k \left|\Syt(N-k,k)(\Des \supseteq \odds(i))\right|. \] The only difference between this equation and Equation~\eqref{eqn:first proof no consecutive indices is schur positive - odds set} is the omission of the summand corresponding to $k=0$. However, this summand evaluates to zero and does not affect the overall expression. Indeed, $\left|\Syt(N,0)(\Des \supseteq \odds(i))\right| = 0$, since the unique SYT of shape $(N)$ has no descents. \end{proof} \subsection{Second proof of Lemma~\ref{lem:if sparse and good sizes then schur positive two rows}} \label{subsec:proof if sparse and good sizes then schur positive two rows by superstandard} As a first step of this proof, we prove that a set satisfying the conditions of Lemma~\ref{lem:if sparse and good sizes then schur positive two rows} is symmetric. \begin{lemma} \label{lem:sufficent condition symmetry two rows} Let $\A$ be a finite set with a sparse statistic $D:\A \to 2^{[N-1]}$, and denote $n = \lfloor\frac{N}{2} \rfloor$. Assume that there are constants $b_k \in \NN$ for $0 \le k \le n$, such that for every sparse set $J \subseteq [N-1]$, $|\A(D \supseteq J)| = b_{|J|}$. Then $\A$ is symmetric with respect to $D$. \end{lemma} \begin{proof} Following Lemma~\ref{lem:symmetric complement is symmetric}, it suffices to prove that $\A$ is symmetric with respect to the complementary statistic $\bar{D}$. As we proceed to prove it by Lemma~\ref{lem:my symmetry criterion}, let us find $|\A_{\bar{D}}(\alpha)|$ for all $\alpha = (\alpha_1, \dots, \alpha_\ell) \vDash N$. If a composition $\alpha$ has $\max_i (\alpha_i) > 2$, then there exists $j \in [N-2]$ such that $j,j+1 \notin S_\alpha$, where $S_\alpha$ is the set corresponding to $\alpha$. By Definition~\ref{def:respect composition}, for every element $a \in \A_{\bar{D}}(\alpha)$ we have $\bar{D}(a) \subseteq S_\alpha$, so $j, j + 1 \notin \bar{D}(a)$. Consequently, $j,j+1 \in D(a)$, and the set $D(a)$ is not sparse. However, $D$ is assumed to be a sparse function, so $\A_{\bar{D}}(\alpha) = \emptyset$. Now assume that $\max_i (\alpha_i) \le 2$, and denote by $k = |\{i \mid \alpha_i = 2\}|$ the number of occurrences of $2$ in $\alpha$. Thus, we have $\ell = N - k$. Consider the set $J = [N-1] \setminus S_\alpha$. Notably, the set $J$ is sparse and consists of $k$ elements. Let $a \in \A$ be an element. We have $a \in \A_{\bar{D}}(\alpha)$ if and only if $\bar{D}(a) \subseteq S_\alpha$, or equivalently, $D(a) \supseteq J$. Thus, $|\A_{\bar{D}}(\alpha)| = |\A(D \supseteq J)| = b_k$. To conclude, if $\alpha$ contains an element larger than $2$ then $\A_{\bar{D}}(\alpha) = \emptyset$. Otherwise, the size of $\A_{\bar{D}}(\alpha)$ depends only on the number of occurrences of $2$ in $\alpha$. Therefore, $|\A_{\bar{D}}(\alpha)| = |\A_{\bar{D}}(\beta)|$ for all $\alpha \sim \beta \vDash N$. By Lemma~\ref{lem:my symmetry criterion}, we obtain that $\A$ is symmetric. \end{proof} As the next step of the proof, we prove that $\A$ is Schur-positive and find its Schur coefficients. For this, we define a total order on partitions $\lambda \vdash N$: \begin{definition} \label{def:conjugate order} Let $\lambda, \mu \vdash N$ be partitions of $N$. Let $\lambda_i' = |\{j \mid \lambda_j \ge i\}|$ denote the length of the $i$-th column in the Young diagram of $\lambda$. We say that $\mu$ is \emph{larger} than $\lambda$ in the \emph{conjugate order}, and denote $\mu' > \lambda'$, if there exists $i$ such that $\mu_j' = \lambda_j'$ for all $j < i$ and $\mu_i' > \lambda_i'$. \end{definition} Following Hamaker, Pawlowski and Sagan \cite[Section 5]{S3_patterns_list}, we define the \emph{column superstandard} Young tableau of shape $\lambda \vdash N$, obtained by filling the columns of the Young diagram of shape $\lambda$ one by one. We denote it by $T_\lambda \in \Syt(\lambda)$. Formally, $(T_\lambda)_{i,j} = \lambda_1' + \cdots + \lambda_{j-1}' + i$. For example, if $\lambda = (4,2,2,1)$, then $T_\lambda$ is the SYT in Figure~\ref{fig:SYT_lambda example}. \begin{figure}[htb] \[ \young(1589,26,37,4) \] \caption{The SYT $T_\lambda$ for $\lambda = (4,2,2,1)$.} \label{fig:SYT_lambda example} \end{figure} The power of these notions may be reflected by the following statement: \begin{lemma} \label{lem:superstandard characterize coefficients} Let $\lambda, \mu \vdash N$ be two partitions. Then: \begin{enumerate} \item $\Des(T_\lambda) = [N-1] \setminus \{\lambda_{1}', \lambda_{1}'+\lambda_{2}', \dots\}$. \item If $\Des(T) = [N-1] \setminus \{\lambda_{1}', \lambda_{1}'+\lambda_{2}', \dots\}$ for some $T \in \Syt(\mu)$, then $\mu' \ge \lambda'$. Furthermore, if $\mu = \lambda$ then $T = T_\lambda$. \end{enumerate} \end{lemma} \begin{proof} The first assertion is obvious, so let us focus on the second assertion. Let $T \in \Syt(\mu)$ be a tableau, and assume that $\Des(T) = \Des(T_\lambda)$ and $T \ne T_\lambda$. We aim to show that $\mu' > \lambda'$. Let us denote the first column that differs between $T$ and $T_\lambda$ by $i$. The $i$-th column of $T_\lambda$ contains the entries $s+1,\dots,s+\lambda_{i}'$, where $s = \lambda_1' + \dots + \lambda_{i-1}'$. To prove $\mu' > \lambda'$, it suffices to show that all these entries also appear in the $i$-th column of $T$. Assume, by contradiction, that some of these entries appear in other columns of $T$. Let $x$ be the minimal such entry, and let $j \ne i$ be the column of $T$ that contains $x$. Since $s+1$ appears in the $i$-th column of $T$, we may assume that $x > s+1$. If $j < i$, this contradicts the assumption that $T$ and $T_\lambda$ agree in the first $i-1$ columns. On the other hand, if $j > i$, then $x$ appears in the first row of $T$, since it is the minimal entry of the $j$-th column of $T$. Consequently, we obtain that $x-1 \notin \Des(T)$, while $x-1 \in \Des(T_\lambda)$, which contradicts the assumption that $\Des(T) = \Des(T_\lambda)$. \end{proof} Lemma~\ref{lem:superstandard characterize coefficients} associates the Young diagram of shape $\lambda$ with the set $\Des(T_\lambda)$. As we will see later, this association is powerful in analysing the Schur coefficients of symmetric sets. Standard Young tableaux with at most $2$ rows have a slightly stronger property: \begin{lemma} \label{lem:superstandard two rows characterize coefficients} Let $\lambda = (N-k_1,k_1)$ and $\mu = (N-k_2,k_2)$ be two partitions of $N$ with at most two parts each. Then: \begin{enumerate} \item $\Des(T_\lambda) = \odds(k_1)$. \item If $\Des(T) = \odds(k_1)$ for some $T \in \Syt(\mu)$, then $k_1 = k_2$ and $T = T_\lambda$. \end{enumerate} \end{lemma} \begin{proof} The first assertion is obvious, so let us focus on the second assertion. Let $T \in \Syt(\mu)$ be a tableau, and suppose that $\Des(T) = \Des(T_\lambda)$. Given that both $T$ and $T_\lambda$ have two rows each, it suffices to show that $\row_2(T) = \row_2(T_\lambda)$. Since $\Des(T) = \{1,3,\dots,2k_1-1\}$, it follows that $\{1,3,\dots,2k_1-1\} \subseteq \row_1(T)$ and $\{2,4,\dots,2k_1\} \subseteq \row_2(T)$. Consequently, we have $2k_1+1 \in \row_1(T)$. As $T$ has no descents beyond index $2k_1-1$, all entries greater than $2k_1$ must appear in the first row. Therefore, we conclude that $\row_2(T) = \{2,4,\dots,2k_1\}$. \end{proof} Now we are ready to prove that if a set is symmetric with respect to a sparse statistic then it is Schur-positive: \begin{lemma} \label{lem:if two rows and symmetric then schur positive} Let $\A$ be a symmetric set with respect to a sparse statistic $D:\A \to 2^{[N-1]}$, and denote $n = \lfloor\frac{N}{2} \rfloor$. Then $\A$ is Schur-positive, and its Schur expansion is \[ \Q_{D} (\A) = \sum_{k=0}^n |\A(D = \odds(k))|\; s_{N-k,k}. \] \end{lemma} \begin{proof} The set $\A$ is assumed to be symmetric, so by Theorem~\ref{thm:criterion schur positive young}, we have \begin{equation}\label{eqn:proof symmetric set with no consecutive indices is schur positive} \sum_{a \in \A} \boldsymbol{t}^{D(a)} = \sum_{\lambda \vdash N} c_\lambda \sum_{T \in \Syt(\lambda)} \boldsymbol{t}^{\Des(T)}, \end{equation} where $c_\lambda$ are the Schur coefficients of $\A$. It suffices to show that if there exists $k$ such that $\lambda=(N-k,k)$ then $c_\lambda = |\A(D = \odds(k))|$, and otherwise $c_\lambda=0$. If $\A = \emptyset$, then $\Q_{D}(\A) = 0$, and the statement holds. Therefore, we may assume that $\A \ne \emptyset$, and consequently, there exists $c_\lambda \ne 0$ for some partition $\lambda \vdash N$. Let $\mu \vdash N$ be a partition with $c_\mu \ne 0$, maximal in the conjugate order (\ie such that $c_\lambda = 0$ for every $\lambda \vdash N$ with $\lambda' > \mu'$). Equation~\eqref{eqn:proof symmetric set with no consecutive indices is schur positive} implies that the equation \begin{equation}\label{eqn:proof symmetric set with no consecutive indices is schur positive - specific set} |\A(D = J)| = \sum_{\lambda \vdash N} c_\lambda \left|\Syt(\lambda)(\Des = J)\right| \end{equation} holds for all $J \subseteq [N-1]$. Let us find the right-hand side of Equation~\eqref{eqn:proof symmetric set with no consecutive indices is schur positive - specific set} when substituting $J = \Des(T_\mu)$. Let $T \in \Syt(\lambda)$ be a tableau with $\Des(T) = \Des(T_\mu)$. By Lemma~\ref{lem:superstandard characterize coefficients}, we have $T = T_\mu$ or $\lambda' > \mu'$. However, if $\lambda' > \mu'$ then $c_\lambda = 0$. Therefore, if $T \in \Syt(\lambda)$ has $\Des(T) = \Des(T_\mu)$ and $c_\lambda \ne 0$, then $T = T_\mu$. Consequently, substituting $J = \Des(T_\mu)$ into Equation~\eqref{eqn:proof symmetric set with no consecutive indices is schur positive - specific set}, we find that $|\A(D = \Des(T_\mu))| = c_\mu \neq 0$. We may conclude that there exists an element $a \in \A$ with $D(a) = \Des(T_\mu)$. The set $D(a)$ is sparse, so $\{1,2\} \nsubseteq D(a)$. Lemma~\ref{lem:superstandard characterize coefficients} implies that $\{1,2\} \subseteq \Des(T_\mu)$ whenever $\mu_1' >2$, so we may deduce that $\mu_1' \le 2$. Therefore, $c_\lambda = 0$ for every partition $\lambda$ with more than $2$ parts. Thus, we can reformulate Equation~\eqref{eqn:proof symmetric set with no consecutive indices is schur positive - specific set} as \begin{equation}\label{eqn:proof symmetric set with no consecutive indices is schur positive:equation with only two rows} |\A(D = J)| = \sum_{k=0}^n c_k \left|\Syt(N-k,k)(\Des = J)\right|. \end{equation} By Lemma~\ref{lem:superstandard two rows characterize coefficients}, since only partitions into at most two parts are involved in Equation~\eqref{eqn:proof symmetric set with no consecutive indices is schur positive:equation with only two rows}, substituting $J = \Des(T_{\lambda})$ for $\lambda = (N-k,k)$ yields $|\A(D = \odds(k))| = c_k$, as required. \end{proof} \begin{proof}[Second proof of Lemma~\ref{lem:if sparse and good sizes then schur positive two rows}] The lemma follows directly from Lemma~\ref{lem:sufficent condition symmetry two rows} together with Lemma~\ref{lem:if two rows and symmetric then schur positive}. \end{proof} \section{Short chords of matchings} \label{sec:short chords in matchings} In this section, we analyze the set of matchings $\M_{N,f}$ with respect to short chords (Recall Definition~\ref{def:matching} and Definition~\ref{def:short}). First, we apply Theorem~\ref{thm:criterion schur positive two rows} to establish Theorem~\ref{thm:matchings schur positive}, which asserts that $\M_{N,f}$ is Schur-positive. Next, we provide a bijective proof of Theorem~\ref{thm:matchings schur positive}, which will be utilized in Section~\ref{sec:refinements} to refine the Schur-positivity result. Finally, we demonstrate that the Schur expansion of $\Q_{\Short} (\M_{N,f})$ may be explicitly interpreted in terms of Bessel polynomials. \subsection{First proof of Theorem~\ref{thm:matchings schur positive}} \begin{proof}[\unskip\nopunct] Clearly, the function $\Short: \M_{N,f} \to 2^{[N-1]}$ is sparse (as defined in Definition~\ref{def:sparse}). Let $J = \{j_1, \dots, j_k\} \subseteq [N-1]$ be a sparse set, and let us enumerate the elements of $\M_{N,f}(\Short \supseteq J)$. In every matching in $\M_{N,f}(\Short \supseteq J)$, the vertices $j_i$ and $j_i + 1$ are matched for all $1 \le i \le k$, and the remaining $N-2k$ vertices can be matched in any way, subject to the condition that exactly $f$ vertices remain unmatched. Therefore, we have \[ |\M_{N,f}(\Short \supseteq J)| = |\M_{N-2k,f}|, \] and thus it depends only on the size of $J$. By applying Theorem~\ref{thm:criterion schur positive two rows}, we conclude that $\M_{N,f}$ is Schur-positive with respect to $\Short$, with the following Schur expansion: \[ \Q_{\Short} (\M_{N,f}) = \sum_{k=0}^n |\M_{N,f}(\Short = \{1,3,5,\dots, 2k-1\})|\ s_{N-k,k}. \] (While Theorem~\ref{thm:criterion schur positive two rows} sums over $0 \le k \le \lfloor\frac{N}{2} \rfloor$, this sum only goes up to $n = \frac{N-f}{2}$. However, the extra summands equal 0 and do not affect the expression.) Clearly, \[ |\M_{N,f}(\Short = \{1,3,5,\dots, 2k-1\})| = |\M_{N-2k,f}(\Short = \emptyset)|, \] and we obtain the required Schur expansion. \end{proof} \subsection{Bijective proof of Theorem~\ref{thm:matchings schur positive}} \label{subsec:bijective proof matchings schur positive} Before presenting the bijective proof of Theorem~\ref{thm:matchings schur positive}, we give some definitions and notations for matchings: \begin{definition} \label{def:restriction of matching} Given a matching $m \in \M_N$, we say that a set $S \subseteq [N]$ is $m$-invariant if for every chord $(i,j) \in m$ we have $i \in S$ if and only if $j \in S$. Moreover, for a matching $m$ and an $m$-invariant set $S$ we define the \emph{restriction} of $m$ to $S$, denoted $\res_S(m)$, to be a matching on $S$ which is obtained by removing all the vertices not in $S$ from $m$. \end{definition} For example , consider the matching $m_1 = \{(1,2),\; (3,5),\; (4)\} \in \M_{5,1}$ as in Figure~\ref{fig:core first example before}. The set $S_1=\{1,2,4\}$ is $m_1$-invariant, and $\res_{S_1}(m_1)=\{(1,2),\; (4)\}$. On the other hand, the set $S_2 = \{1,2,3\}$ is not $m_1$-invariant, so $\res_{S_2}(m_1)$ is not defined. \begin{observation} \label{obs:restriction of matching to set and complement defines uniquely} Let $S \subseteq [N]$ be a set of vertices, let $m_1$ be a matching on $S$, and let $m_2$ be a matching on $[N]\setminus S$. Then there exists a unique matching $m \in \M_N$ such that $\res_S(m) = m_1$ and $\res_{[N] \setminus S}(m) = m_2$. \end{observation} Now let us present a bijection \[ F:\M_{N,f} \to \bigcup_{k=0}^n \M_{N-2k,f}(\Short = \emptyset) \times \Syt(N-k,k), \] that sends matchings $m \in \M_{N,f}$ to pairs $(m_0,T)$, where $m_0$ is a short-chord-free matching on $[N-2k]$ with $f$ unmatched vertices and $T\in \Syt(N-k,k)$ for some $0\le k \le n$, such that $\Des T = \Short m$ for all $m$. By Theorem~\ref{thm:criterion schur positive young}, the existence of such a bijection implies Theorem~\ref{thm:matchings schur positive}. \subsubsection{Constructing the bijection} \label{subsec:constructing the bijection} First, we define the core of a matching: \begin{definition} \label{def:core of matching} The reduction process for a given matching $m$ repeatedly removes any short chords of the matching until there are no short chords left. The remaining vertices are then re-indexed with natural numbers starting from $1$ while keeping their relative order, resulting in a matching denoted by $\core(m)$. A chord or vertex of $m$ is called \emph{stable} if it is not removed during the process, and unstable otherwise. The set of stable vertices of $m$ is denoted $\Stable(m)$. \end{definition} Proposition~\ref{prop:core well defined} below implies that $\core(m)$ and $\Stable(m)$ are well-defined and are independent of the order of the steps. For a matching $m \in \M_{N,f}$, we also define $T(m)$ as the unique SYT consisting of $N$ cells arranged in two rows, such that \[ \row_2(T) = \{j \mid \text{the chord } (i,j) \in m \text{ is unstable}\}. \] Recall that when writing $(i,j) \in m$ we assume that $ii$. If $(i,i+1) \notin m$ then $j i+1$, and we obtain that the unstable chord $(j,i+1)$ intersects the chord $(i,j')$, contradicting Lemma~\ref{lem:properties of core--intersect stable}. Therefore, we may conclude that $(i,i+1) \in m$ and $i \in \Short m$. \end{proof} \subsubsection{Proof of bijection} \label{subsec:proof of bijection} In this section we will prove that the transformation $F$ defined in Section~\ref{subsec:constructing the bijection} is indeed a bijection, by constructing its inverse function. In order to construct the inverse function, we will establish a correspondence between standard Young tableaux of two rows and ballot paths. We define ballot paths as follows: \begin{definition} \label{def:ballot path} Let $N \in \NN$ be a nonnegative integer. A \emph{ballot path} of length $N$ is a sequence of $N$ steps, where each step is either $(1,1)$ or $(1,-1)$. The path starts at the origin $(0,0)$. Namely, each step either moves one unit up and one unit right, or one unit down and one unit right. The path is said to be valid if it never goes below the x-axis, \ie the y-coordinate of a point on the path is always non-negative. The set of ballot paths from $(0,0)$ to $(N,t)$ is denoted $\Pcal_{N,t}$. Given a ballot path $p \in \Pcal_{N,t}$, denote by $p_i$ the y-coordinate of $p$ after $i$ steps; in particular, $p_0=0$. The set $\UP(p) \subseteq [N]$ ($\DOWN(p) \subseteq [N]$) consists of the indices $i$ such that $p_i > p_{i-1}$ (respectively, $p_i < p_{i-1}$). Finally, define the height of the $i$-th \emph{step} of a path $p$ to be the maximum height of its two endpoints, and denote it by $\height_p(i) := \max(p_{i-1},p_i)$. \end{definition} The bijection between SYTs of two rows and ballot paths is direct: Associate $T \in \Syt(N-k,k)$ with the path $p(T) \in \Pcal_{N,N-2k}$ such that $\UP(p(T)) = \row_1(T)$ and $\DOWN(p(T)) = \row_2(T)$. For example, consider the tableau $T \in \Syt(7,3)$ described in Figure~\ref{fig:core second example core}, with $\row_2(T) = \{5,6,9\}$. It is associated with the ballot path $p := p(T) \in \Pcal_{10,4}$ presented in Figure~\ref{fig:ballot path example}. The ballot path $p$ has, for example, $2 \in \UP(p)$ because $p_2 = 2 > p_1 = 1$. Conversely, $5 \in \DOWN(p)$ because $p_5 = 3 < p_4 = 4$. In addition, $\height_p(3) = \max(p_2,p_3) = 3$ while $\height_p(5) = \max(p_4,p_5) = 4$. \begin{figure} \centering \[\begin{tikzcd}[column sep=small] {} &&&& \bullet &&&& \bullet && \bullet \\ &&& \bullet && \bullet && \bullet && \bullet & {} \\ && \bullet &&&& \bullet &&&& {} \\ & \bullet &&&&&&&&& {} \\ {} &&&&&&&&&&& {} \arrow[shorten >= -5pt, shorten <= -5pt, "2", no head, from=4-2, to=3-3, line width=2.5pt] \arrow[shorten >= -5pt, shorten <= -5pt, ""{name=0, anchor=center, inner sep=0}, "3", no head, from=3-3, to=2-4] \arrow[shorten >= -5pt, shorten <= -5pt, ""{name=1, anchor=center, inner sep=0}, "4", no head, from=2-4, to=1-5] \arrow[shorten >= -5pt, shorten <= -5pt, ""{name=2, anchor=center, inner sep=0}, "6", no head, from=2-6, to=3-7] \arrow[shorten >= -5pt, shorten <= -5pt, "7", no head, from=3-7, to=2-8, line width=2.5pt] \arrow[shorten >= -5pt, shorten <= -5pt, ""{name=3, anchor=center, inner sep=0}, "8", no head, from=2-8, to=1-9] \arrow[shorten >= -5pt, shorten <= -5pt, ""{name=4, anchor=center, inner sep=0}, "9", no head, from=1-9, to=2-10] \arrow[shorten >= -5pt, shorten <= -5pt, "10", no head, from=2-10, to=1-11, line width=2.5pt] \arrow[shorten >= -5pt, shorten <= -5pt, from=5-1, to=5-12] \arrow[shorten >= -5pt, shorten <= -2pt, from=5-1, to=1-1] \arrow[shorten >= -5pt, shorten <= -5pt, ""{name=5, anchor=center, inner sep=0}, "5", no head, from=1-5, to=2-6] \arrow[shorten >= -5pt, shorten <= -2pt, "1", no head, from=5-1, to=4-2, line width=2.5pt] \arrow[shorten >= -5pt, shorten <= -5pt, loosely dashed, no head, from=4-2, to=4-11] \arrow[shorten >= -5pt, shorten <= -5pt, loosely dashed, no head, from=3-3, to=3-11] \arrow[shorten >= -5pt, shorten <= -5pt, loosely dashed, no head, from=2-8, to=2-11] \arrow[dotted, no head, from=0, to=2] \arrow[dotted, no head, from=3, to=4] \arrow[dotted, no head, from=1, to=5] \end{tikzcd}\] \caption{A ballot path $p \in \Pcal_{10,4}$} \label{fig:ballot path example} \end{figure} Next, for a given ballot path $p \in \Pcal_{N,t}$, we construct a set $\Stable(p)$ and a perfect matching $m_{\text{unstable}}(p)$ on $[N]\setminus\Stable(p)$ as follows: For every vertex $j \in \DOWN(p)$, we match it in $m_{\text{unstable}}(p)$ to the maximal $i < j$ such that $\height_p(i)=\height_p(j)$. Since $p$ is a valid ballot path, it can be deduced that for every $j \in \DOWN(p)$, there exists a unique $i \height_p(i)$ for all $j>i$, so $\left|\Stable(p)\right| = t$. We are now ready to describe the inverse bijection of $F$, denoted \[ \tilde{F}:\bigcup_{k=0}^n \M_{N-2k,f}(\Short = \emptyset) \times \Syt(N-k,k) \to \M_{N,f}. \] Given a short-chord-free matching $m_0 \in \M_{N-2k,f}(\Short = \emptyset)$ and a tableau $T \in \Syt(N-k,k)$ for some $k$, denote $p = p(T) \in \Pcal_{N,N-2k}$. We will construct a matching $m_{\text{stable}}$ on $\Stable(p)$ and a matching $m_{\text{unstable}}$ on $[N]\setminus\Stable(p)$, and then apply Observation~\ref{obs:restriction of matching to set and complement defines uniquely} to obtain $\tilde{F}(m_0,T) \in \M_{N,f}$. We construct these sub-matchings as follows: \begin{itemize} \item $m_{\text{stable}}$: Since $p \in \Pcal_{N,N-2k}$, we infer that $\left|\Stable(p)\right| = N-2k$. Therefore, we may rename the vertices of $m_0 \in \M_{N-2k,f}$ to $\Stable(p)$ as follows: There exists a unique bijection $\varphi:[N-2k] \to \Stable(p)$ such that $i < j$ if and only if $\varphi(i) <\varphi(j)$ for all $i,j$. The matching $m_{\text{stable}}$ on $\Stable(p)$ consists of the chords $(\varphi(i), \varphi(j))$ for all $(i,j) \in m_0$. \item $m_{\text{unstable}} = m_{\text{unstable}}(p)$ is the matching described earlier. \end{itemize} For example, consider $m_0 = \{(1,3),\; (2,4)\} \in \M_{4,0}(\Short = \emptyset)$ and $T \in \Syt(N-k,k)$ presented in Figure~\ref{fig:core second example core}. As mentioned before, $T$ is associated with the ballot path $p := p(T) \in \Pcal_{10,4}$ presented in Figure~\ref{fig:ballot path example}. Therefore, we obtain the matching $m_{\text{unstable}}(p) = \{(3,6),\; (4,5),\; (8,9)\}$ (with the pairs of steps that correspond to its chords connected by dotted lines in the figure) and $\Stable(p) = \{1,2,7,10\}$ (with the steps that correspond to these vertices denoted by bold lines). Applying the order-preserving bijection $\varphi:[4] \to \{1,2,7,10\}$ on $m_0$ yields the matching $m_{\text{stable}} = \{(1,7),\; (2,10)\}$. Therefore, \[ \tilde{F}(m_0,T) = \{(1,7),\; (2,10),\; (3,6),\; (4,5),\; (8,9)\} \] is the matching presented in Figure~\ref{fig:core second example before}. It remains to show that $\tilde{F}$ is indeed the inverse function of $F$. We will do so in two steps. \proofstep{Step 1: $\tilde{F}\circ F = Id$} \begin{lemma} \label{lem:F_tilde(F)=id} Let $m \in \M_{N,f}$ be a matching, and denote $F(m) = (\core(m),T)$. Then $\tilde{F}(\core(m),T) = m$. \end{lemma} \begin{proof} Denote $\left|\Stable(m)\right| = N-2k$, implying that $\core(m) \in \M_{N-2k,f}$ and $T \in \Syt(N-k,k)$. Moreover, denote $p=p(T) \in \Pcal_{N,N-2k}$. First, we prove that \begin{equation} \label{eqn:lemma F_tilde(F)=id} \res_{[N]\setminus\Stable(m)}(m) = m_{\text{unstable}}(p). \end{equation} We note that the set $[N] \setminus \Stable(m)$ is $m$-invariant, so the left-hand side of Equation~\eqref{eqn:lemma F_tilde(F)=id} is well-defined. Notice that $|[N]\setminus\Stable(m)| = |[N]\setminus\Stable(p)| = 2k$ and that $\res_{[N]\setminus\Stable(m)}(m)$ is a perfect matching. Therefore, in order to prove that Equation~\eqref{eqn:lemma F_tilde(F)=id} holds, it suffices to prove that any unstable chord of $m$ belongs to $m_{\text{unstable}}(p)$ too. Let $(i,j) \in m$ be an unstable chord. Thus, we may deduce that $i \in \UP(p)$ and $j \in \DOWN(p)$. Let $i' \in \UP(p)$ such that $i < i' < j$. By Lemma~\ref{lem:properties of core--chord unstable iff all midpoints unstable}, $i'$ is an endpoint of an unstable chord $(i',j') \in m$ with $i' < j'$. By Lemma~\ref{lem:properties of core--intersect stable}, we obtain that the chord $(i,j)$ does not intersect $(i',j')$, implying that $i < i' < j' < j$. On the other hand, every $j' \in \DOWN(p)$ with $i < j' < j$ is an endpoint of an unstable chord $(i',j') \in m$ with $i < i' < j' < j$. Therefore, we obtain a bijection from $\UP(p) \cap [i,j]$ to $\DOWN(p) \cap [i,j]$ (with $i$ matched with $j$), so $\height_p(i) = \height_p(j)$. Moreover, this bijection has the property that if $i' \in \UP(p) \cap [i,j]$ is matched with $j' \in \DOWN(p) \cap [i,j]$ then $i' < j'$ (\ie the ascending steps of the path appear before the associated descending steps), so $\height_p(j) < \height_p(i')$ for all $i' \in \UP(p) \cap [i+1,j-1]$. We may conclude that $(i,j) \in m_{\text{unstable}}(p)$ for every unstable chord $(i,j)$ of $m$ and prove that Equation~\eqref{eqn:lemma F_tilde(F)=id} holds. Next, we denote $m' = \tilde{F}(\core(m),T)$ and prove that $m=m'$. From Equation~\eqref{eqn:lemma F_tilde(F)=id} we deduce that the supports of the matchings $\res_{[N]\setminus\Stable(m)}(m)$ and $m_{\text{unstable}}(p)$ are identical, and therefore $\Stable(m) = \Stable(p)$. Thus, the set $[N]\setminus\Stable(m)$ is both $m$-invariant and $m'$-invariant, and restricting each of these matchings to $[N]\setminus\Stable(m)$ results in $m_{\text{unstable}}(p)$. In addition, it can be easily verified from the descriptions of $F$ and $\tilde{F}$ that $\res_{\Stable(m)}(m) = \res_{\Stable(m)}(m')$ is the matching obtained by relabeling the vertices of $\core(m)$ with the elements of $\Stable(m)$ in increasing order. By Observation~\ref{obs:restriction of matching to set and complement defines uniquely}, we may deduce that $m=m'$. \end{proof} \proofstep{Step 2: $F \circ \tilde{F} = Id$} \begin{lemma} \label{lem:F(F_tilde)=id} Let $m_0 \in \M_{N-2k,f}$ with $\Short(m_0) = \emptyset$ and $T \in \Syt(N-k,k)$ for some $k$, and denote $m = \tilde{F}(m_0,T)$. Then $\core(m)=m_0$ and $T(m) = T$. \end{lemma} \begin{proof} Denote $p=p(T) \in \Pcal_{N,N-2k}$ and $\Stable(p) = \{i_1, \dots, i_{N-2k}\}$ where $i_1 < \cdots i_{N-2k}$. We first prove that $\Stable(m) = \Stable(p)$. Notice that the matching $m_{\text{unstable}}(p)$ is non-crossing. This can be viewed visually from Figure~\ref{fig:ballot path example}, where $m_{\text{unstable}}(p)$ is denoted by horizontal dotted lines that cross the path only in their endpoints. Indeed, let $j_1 < j_2 < j_3 < j_4$ be four vertices, and assume, by contradiction, that both $(j_1,j_3)$ and $(j_2,j_4)$ belong to $m_{\text{unstable}}(p)$. By the definition of $m_{\text{unstable}}(p)$, the assumption $(j_1,j_3) \in m_{\text{unstable}}(p)$ implies that $\height_p(j_1) = \height_p(j_3)$, and $\height_p(j) \ne \height_p(j_1)$ for all $j_1 < j < j_3$. Since $\height_p(j_1+1) \ge \height_p(j_1)$ and due to the discrete continuity of the path, we obtain that $\height_p(j) > \height_p(j_1)$ for all $j_1 < j < j_3$. Consequently, we obtain $\height_p(j_2) > \height_p(j_1) = \height_p(j_3)$. Similarly, the assumption $(j_2,j_4) \in m_{\text{unstable}}(p)$ implies that $\height_p(j_3) > \height_p(j_2)$, in contradiction. Therefore, we may conclude that the matching $m_{\text{unstable}}(p)$ is non-crossing. Next, we may infer that for every $1 \le \ell < N-2k$, the segment $[i_\ell+1,i_{\ell+1}-1]$ is $m$-invariant and the restricted matching $\res_{[i_\ell+1,i_{\ell+1}-1]}(m)$ is perfect and non-crossing. By Lemma~\ref{lem:properties of core--perfect non-crossing unstable}, we obtain that $j \notin \Stable(m)$ for all $i_\ell < j < i_{\ell+1}$. Similarly, we obtain that if $j < i_1$ or $j > i_{N-2k}$ then $j \notin \Stable(m)$, and therefore $\Stable(m) \subseteq \Stable(p)$. Thus, a valid reduction process of $m$ may begin with removing every vertex not in $\Stable(p)$. We may deduce from the description of $\tilde{F}$ that $\res_{\Stable(p)}(m)$ is the matching obtained by relabeling the vertices of $m_0$ with the elements of $\Stable(p)$ in increasing order. This matching is short-chord-free, so $\Stable(m) = \Stable(p)$ and $\core(m) = m_0$. It remains to prove that $T(m) = T$, namely that $p' = p$, where $p' := p(T(m))$. Since $\Stable(m) = \Stable(p)$, we may infer from the description of $\tilde{F}$ that \[ \DOWN(p) = \{j \mid \text{the chord } (i,j) \in m \text{ is unstable}\}. \] Thus, $\DOWN(p) = \DOWN(p')$ and therefore $p = p'$. \end{proof} Finally, we conclude the bijective proof: \begin{proof}[Bijective proof of Theorem~\ref{thm:matchings schur positive}] By Theorem~\ref{thm:criterion schur positive young}, it suffices to prove that \[ \sum_{m \in \M_{N,f}} \boldsymbol{t}^{\Short(m)} = \sum_{k=0}^N |\M_{N-2k,f}(\Short = \emptyset)| \sum_{T \in \Syt(N-k,k)} \boldsymbol{t}^{\Des(T)}, \] where $\boldsymbol{t}^J := \prod_{j \in J} t_j$ for $J \subseteq [N-1]$. Equivalently, it suffices to present a bijection between $\M_{N,f}$ and $\bigcup_{k=0}^n \M_{N-2k,f}(\Short = \emptyset) \times \Syt(N-k,k)$, such that if $m \mapsto (m_0,T)$ then $\Short(m) = \Des(T)$. The transformation $F$ defined by $F(m) = (\core(m),T(m))$ is a bijection by Lemma~\ref{lem:F_tilde(F)=id} combined with Lemma~\ref{lem:F(F_tilde)=id}, and it satisfies $\Short(m) = \Des(T(m))$ by Proposition~\ref{prop:F statistic preserving}. \end{proof} \subsection{Analysis of the coefficients and relations with Bessel polynomials} \label{subsec:schur coefficients bessel} The \emph{Bessel polynomials} $\theta_n(x)$, sometimes called the \emph{reverse Bessel polynomials}, are given by the generating function \[ \frac{1}{\sqrt{1-2v}} \exp\left[x(1-\sqrt{1-2v})\right] = \sum_{n=0}^\infty \frac{v^n}{n!} \theta_n(x). \] They also have the explicit formula \[ \theta_n(x) = \sum_{k=0}^n \frac{(2n-k)!}{k!(n-k)!2^{n-k}} x^k. \] For more information about the Bessel polynomials, the reader is referred to~\cite{bessel_polynomials_book}. McSorley and Feinsilver \cite[Theorem 3.5]{bessel_polynomials_mathcings} discovered the following identity: \begin{theorem}[McSorley and Feinsilver] For every $n \ge 0$: \[ \theta_n(x-1) = \sum_{i=0}^n h(P_{2n},i)x^i, \] where $h(P_{2n},i)$ is the number of perfect matchings on $2n$ vertices with $i$ short chords. \end{theorem} An equivalent formulation of this result states that \[ \theta_n(x) = \sum_{i=0}^n h(P_{2n},i)(x+1)^i, \] so the sequence $h(P_{2n},i)$ can be thought of as the coefficients of the Taylor expansion of $\theta_n(x)$ around $x=-1$. \begin{observation} For every $n \ge 0$: \[ h(P_{2n},i) = |\M_{2n-i,i} (\Short=\emptyset)|. \] \end{observation} \begin{proof} We give a bijective proof for the statement. The bijection sends a perfect matching $m \in \M_{2n,0}$ with $i$ short chords to a short-chord-free matching on $2n-i$ vertices with $i$ unmatched vertices, by replacing every short chord with an unmatched vertex. For example, the perfect matching $\{(1,5),\; (2,3),\; (4,6)\} \in \M_{6,0}$ is sent to $\{(1,4),\; (2),\; (3,5)\} \in \M_{5,1}$. Clearly, this gives a bijection between the two desired sets. \end{proof} Therefore, we can reformulate Theorem~\ref{thm:matchings schur positive} and obtain: \begin{corollary} \label{cor:schur expansion bessel} Let $n,f \in \NN$ be nonnegative integers, and denote $N=2n+f$. Then the Schur expansion of the set $\M_{N,f}$ with respect to $\Short$ is given by the formula \[ \Q_{\Short} (\M_{N,f}) = \sum_{k=0}^n h(P_{N+f-2k},f) s_{N-k,k}, \] where $h(P_{N+f-2k},f)$ is the coefficient of $(x+1)^f$ in the Taylor expansion of the Bessel polynomial $\theta_{n+f-k}(x)$ around $x=-1$ \end{corollary} \section{Refinements of the bijection} \label{sec:refinements} In this section, we will utilize the bijection $F$ discussed in Section~\ref{subsec:bijective proof matchings schur positive} to refine Theorem~\ref{thm:matchings schur positive} and find many Schur-positive sets of matchings with respect to the set of short chords. Indeed, given non-negative integers $N$ and $k$, for every short-chord-free matching $m_0 \in \M_{N-2k}(\Short = \emptyset)$, the set \[ \{m \in \M_{N} \mid \core(m) = m_0 \} \] is Schur-positive (as we will see later in Corollary~\ref{cor:closed under knuth like is schur positive}). \subsection{Sets closed under Knuth equivalence} As a first refinement of the Schur-positivity of $\M_{N,f}$, we study the Knuth equivalence of matchings presented in Definition \ref{def:knuth like equivalence}. The power of this notion is reflected by the following theorem: \begin{theorem} \label{thm:knuth like equivalent iff same core} Two matchings $m_1, m_2 \in \M_N$ are Knuth equivalent if and only if $\core(m_1) = \core(m_2)$. \end{theorem} We will prove Theorem~\ref{thm:knuth like equivalent iff same core} in two steps: \proofstep{Step 1: If two matchings are equivalent then they have the same core} \begin{lemma} Let $m_1, m_2 \in \M_N$ be two Knuth equivalent matchings. Then $\core(m_1) = \core(m_2)$. \end{lemma} \begin{proof} Since $m_1$ and $m_2$ are equivalent, we deduce that $m_2$ can be obtained from $m_1$ by a sequence of elementary Knuth transformations. Notably, given a matching $m \in \M_N$ and a matching $\varphi(m)$ obtained from $m$ by applying an elementary Knuth transformation, the matchings $m$ and $\varphi(m)$ differ only in the relative position of a certain short chord, and therefore $\core(\varphi(m)) = \core(m)$. A direct induction shows that $\core(m_1) = \core(m_2)$. \end{proof} \proofstep{Step 2: If two matchings have the same core then they are equivalent} \begin{lemma} \label{lem:if same core then equivalent} Let $m_1, m_2 \in \M_N$ be matchings, and assume that $\core(m_1) = \core(m_2)$. Then $m_1$ and $m_2$ are Knuth equivalent. \end{lemma} Before proving Lemma~\ref{lem:if same core then equivalent}, we introduce the notion of inserting a short chord into a matching: \begin{definition} \label{def:insert short chord to matching} Let $m \in \M_N$ be a matching, and let $1 \le i \le N+1$ be an index. Denote by $\insrt_i(m) \in \M_{N+2}$ the matching obtained by \emph{inserting a short chord} that matches the vertices $i$ and $i+1$, while pushing every vertex $j \ge i$ to position $j+2$. Formally, denote by $f_i:[N] \to [N+2]\setminus\{i,i+1\}$ the function that is described as follows: \[ f_i(j) = \begin{cases} j & \text{if $j < i$,}\\ j+2 & \text{if $j \ge i$.} \end{cases} \] Then the matching $\insrt_i(m)$ consists of the chords $(f_i(j_1),f_i(j_2))$ for all $(j_1,j_2) \in m$ together with $(i,i+1)$, and consists of the unmatched vertices $(f_i(j))$ for all $(j) \in m$. \end{definition} For example, if $m = \{(1,3),\; (2,6),\; (4,5)\}$, then we obtain that $\insrt_3(m) = \{(1,5),\; (2,8),\; (3,4),\; (6,7)\}$. The insertion function is closely related to Knuth equivalence, as demonstrated by the following lemmas: \begin{lemma} \label{lem:insert i equivalent insert j} Let $m \in \M_N$ be a matching and let $1 \le i,j \le N+1$ be indices. Then $\insrt_i(m)$ is Knuth equivalent to $\insrt_j(m)$. \end{lemma} \begin{proof} We may assume without loss of generality that $i \le j$, and prove the statement by induction on $j-i$. The statement is obvious for $i=j$. Assume that $i < j$. By Definition~\ref{def:insert short chord to matching}, the matching $\insrt_{i+1}(m)$ is Knuth equivalent to $\insrt_i(m)$. By the induction hypothesis, $\insrt_{i+1}(m)$ is Knuth equivalent to $\insrt_j(m)$ as well. Therefore, $\insrt_i(m)$ is Knuth equivalent to $\insrt_j(m)$. \end{proof} \begin{lemma} \label{lem:insert same chord to equivalent remains equivalent} Let $m_1,m_2 \in \M_N$ be Knuth equivalent matchings, and let $1 \le i \le N+1$ be an index. Then $\insrt_i(m_1)$ and $\insrt_i(m_2)$ are Knuth equivalent. \end{lemma} \begin{proof} By Lemma~\ref{lem:insert i equivalent insert j}, we may assume that $i = N+1$. Assume that $m_2 = \varphi_1 \cdots \varphi_\ell (m_1)$ for some elementary Knuth transformations $\varphi_1, \dots, \varphi_\ell$. We prove the statement by induction on $\ell$. The statement is obvious for $\ell = 0$. Next, assume that $\ell > 0$. By the induction hypothesis, we may assume that $\insrt_{N+1}(m_2)$ is equivalent to $\insrt_{N+1}(\varphi_\ell(m_1))$. Therefore, it suffices to show that $\insrt_{N+1}(m_1)$ is equivalent to $\insrt_{N+1}(\varphi_\ell(m_1))$. Assume that $(j,j+1),\; (j+2,j') \in m_1$ for some $1 \le j,j' \le N$, and that $(j,j'),\; (j+1,j+2) \in \varphi_\ell(m_1)$, as other types of elementary Knuth transformations are handled similarly. Notice that $\insrt_{N+1}(m_1)$ and $\insrt_{N+1}(\varphi_\ell(m_1))$ have all but four chords in common. Specifically, $\insrt_{N+1}(m_1)$ contains the chords $(j,j+1)$ and $(j+2,j')$, while $\insrt_{N+1}(\varphi_\ell(m_1))$ contains the chords $(j,j')$ and $(j+1,j+2)$. Therefore, there exists an elementary Knuth transformation $\varphi$, such that $\varphi(\insrt_{N+1}(m_1)) = \insrt_{N+1}(\varphi_\ell(m_1))$. Thus, the matchings $\insrt_{N+1}(m_1)$ and $\insrt_{N+1}(\varphi_\ell(m_1))$ are equivalent, as required. \end{proof} We can combine Lemma~\ref{lem:insert i equivalent insert j} with Lemma~\ref{lem:insert same chord to equivalent remains equivalent} to obtain the following: \begin{lemma} \label{lem:insert many chords to matching is equivalent} Let $m \in \M_n$ be a matching, and let $i_1,\dots, i_k$ and $j_1,\dots, j_k$ be two sequences. Then the matchings $\insrt_{i_1}\cdots\insrt_{i_k}(m)$ and $\insrt_{j_1}\cdots\insrt_{j_k}(m)$ are Knuth equivalent. \end{lemma} \begin{proof} We prove the statement by induction on $k$. If $k=0$ then the statement is obvious. Next, we assume that $k > 0$, and denote $m_i = \insrt_{i_2}\cdots\insrt_{i_k}(m)$ and $m_j = \insrt_{j_2}\cdots\insrt_{j_k}(m)$. We aim to prove that the matchings $\insrt_{i_1}(m_i)$ and $\insrt_{j_1}(m_j)$ are Knuth equivalent. By the induction hypothesis, $m_i$ and $m_j$ are equivalent. Therefore, by Lemma~\ref{lem:insert same chord to equivalent remains equivalent}, the matchings $\insrt_{i_1}(m_i)$ and $\insrt_{i_1}(m_j)$ are equivalent too. In addition, by Lemma~\ref{lem:insert i equivalent insert j}, the matchings $\insrt_{i_1}(m_j)$ and $\insrt_{j_1}(m_j)$ are equivalent. Therefore, the matchings $\insrt_{i_1}(m_i)$ and $\insrt_{j_1}(m_j)$ are equivalent. \end{proof} \begin{lemma} \label{lem:matching is generated by inserts to its core} Let $m \in \M_N$ be a matching with $k$ unstable chords. Then there exist indices $i_1, \dots, i_k$ such that \[ m = \insrt_{i_1}\cdots\insrt_{i_k}(\core(m)). \] \end{lemma} \begin{proof} We prove the statement by induction on $k$. If $k=0$ then $\core(m) = m$ and the statement is obvious. Assume that a matching $m \in \M_N$ has $k > 0$ unstable chords. Therefore, $m$ has at least one short chord, denoted $(i_1,i_1+1) \in m$. Thus, there exists a matching $m_1 \in \M_{N-2}$ such that $m = \insrt_{i_1}(m_1)$. Notice that $\core(m) = \core(m_1)$, so $m_1$ has $k-1$ unstable chords. Thus, by the induction hypothesis, there exist indices $i_2,\dots,i_k$ such that $m_1 = \insrt_{i_2}\cdots\insrt_{i_k}(\core(m))$ and so $m = \insrt_{i_1}\cdots\insrt_{i_k}(\core(m))$. \end{proof} Now we are ready to prove Lemma~\ref{lem:if same core then equivalent}. \begin{proof}[Proof of Lemma~\ref{lem:if same core then equivalent}] Let $m_1, m_2 \in \M_N$ be matchings with $m_0 := \core(m_1) = \core(m_2)$. Thus, $m_1$ and $m_2$ have the same number of unstable chords, denoted $k$. Following Lemma~\ref{lem:matching is generated by inserts to its core}, we can write $m_1 = \insrt_{i_1}\cdots\insrt_{i_k}(m_0)$ and $m_2 = \insrt_{j_1}\cdots\insrt_{j_k}(m_0)$ for some $i_1,\dots,i_k$ and $j_1,\dots,j_k$. The statement now follows directly from Lemma~\ref{lem:insert many chords to matching is equivalent}.% \end{proof} Theorem~\ref{thm:knuth like equivalent iff same core} implies the following result: \begin{corollary} \label{cor:closed under knuth like is schur positive} If a set $\M \subseteq \M_N$ is closed under Knuth equivalence then it is Schur-positive with respect to $\Short$. Moreover, if $\M$ is a Knuth equivalence class then its generating function is \[ \Q(\M) = s_{N-k,k}, \] where $k$ is the number of unstable chords of some arbitrary matching $m \in \M$. \end{corollary} \begin{proof} Clearly, a disjoint union of Schur-positive sets is Schur-positive. Therefore, it suffices to establish the statement for equivalence classes. Let $\M \subseteq \M_N$ be an equivalence class. By Theorem~\ref{thm:knuth like equivalent iff same core} there exist $0 \le k \le \frac{N}{2}$, $f \ge 0$ and $m_0 \in \M_{N-2k,f}(\Short=\emptyset)$, such that $\M = \{m \in \M_{N,f} \mid \core(m) = m_0\}$. Recall the transformation $F:m \mapsto (\core(m),T(m))$ discussed in Section~\ref{subsec:bijective proof matchings schur positive}, and consider its restriction to $\M$. We obtain that the restricted transformation \[ \restr{F}{\M}:\M \to \{m_0\} \times \Syt(N-k,k) \] is a statistic-preserving bijection. Applying Theorem~\ref{thm:criterion schur positive young} completes the proof. \end{proof} \subsection{Other constructions of Schur-positive sets} We may apply Corollary~\ref{cor:closed under knuth like is schur positive} to obtain other Schur-positive sets of matchings. For example, we can filter $\M_N$ by the isomorphism class of the intersection graph: \begin{definition} Let $m$ be a matching. Its \emph{intersection graph}, denoted $G(m)$, is defined to be the undirected simple graph with the chords of $m$ as its vertices, and with an edge between two vertices if the associated chords of $m$ intersect. \end{definition} It can be easily seen that applying an elementary Knuth transformation on a matching preserves its intersection graph up to graph-isomorphism. Therefore, by Corollary~\ref{cor:closed under knuth like is schur positive}: \begin{corollary} \label{cor:specific intersection graph schur positive} For every $N$ and $f$, the set of matchings $m \in \M_{N,f}$ with a fixed intersection graph up to graph-isomorphism is Schur-positive. \end{corollary} For example, fix $N$ and $f$. Then for every $k$, the set of $k$-crossing matchings in $\M_{N,f}$ (\ie matchings where $k$ is the maximal cardinality of a set of pairwise intersecting chords) is Schur-positive. Equivalently, this is the set of matchings whose intersection graph has a maximal clique with $k$ vertices. As another example, given a matching $m \in \M_{N,f}$, for every $1 \le i \le N$ denote by $I_i(m)$ the number of chords of $m$ that intersect the chord that contains $i$ (if $i$ is an unmatched vertex define $I_i(m)=0$). From Corollary~\ref{cor:specific intersection graph schur positive} we obtain that for any fixed multiset $S$, the set of matchings $m \in \M_{N,f}$ such that $\{I_i(m) \mid i \in [N]\} = S$ (as multisets) is Schur-positive. For example, the following sets are Schur-positive: \begin{itemize} \item The set of matchings $m \in \M_{N,f}$ with exactly $k$ pairs of intersecting chords, \ie such that $\frac{1}{2} \sum_i I_i(m) = k$. \item The set of matchings $m \in \M_{N,f}$ with exactly $k$ intersecting chords, \ie such that $\frac{1}{2} |\{i \mid I_i(m)>0 \}| = k$. \item The set of matchings $m \in \M_{N,f}$ with $k$ the maximal number of times that a chord intersects other chords, \ie with $\max_i I_i(m) = k$. \end{itemize} \subsection{Pattern avoidance in matchings} \label{subsec:pattern avoiding matchings} Sagan and Woo~\cite{problem_find_pattern}, motivated by Elizalde and Roichman~\cite{arc_pattern_avoiding}, posed the problem of determining which sets $\Pi$ of permutations satisfy the property that for all $n$, the set of permutations in $S_n$ that avoid every pattern in $\Pi$ is Schur-positive. This problem has been extensively studied since then~\cite{S3_patterns_list, BloomSagan, my_pattern_theorem}. An analogous question may be asked about Schur-positivity of pattern-avoiding matchings as well. Extensive research has been conducted on pattern avoidance in perfect matchings by Simion and Schmidt~\cite{simion1985restricted}, Jel\'{i}nek and Mansour~\cite{jelinek2010matchings}, Bloom and Elizalde~\cite{bloom2013pattern}, and others, leading to multiple definitions in the literature. Fang, Hamaker, and Troyka~\cite{fang2022pattern} explore some of these definitions and provide a comparison. Additionally, various conventions exist for generalizing pattern avoidance to non-perfect matchings \cite{mansour2013partial, fang2022pattern, mcgovern2019closures}. We adopt the definition from McGovern~\cite{mcgovern2019closures}, which directly generalizes the definition for perfect matchings from~\cite{jelinek2010matchings} and~\cite{cervetti2022enumeration}. \begin{definition} \label{def:pattern avoidance} Let $m_1 \in \M_{N_1}$ and $m_2 \in \M_{N_2}$ for some positive integers $N_1 \le N_2$. We say that $m_2$ \emph{contains the pattern} $m_1$, if there exist indices $1 \le i_1 < \dots < i_{N_1} \le N_2$ such that the following holds: \begin{itemize} \item For all $1 \le j < j' \le N_1$, \[ (j,j') \in m_1 \Longleftrightarrow (i_j,i_{j'}) \in m_2. \] \item For all $1 \le j \le N_1$, \[ (j) \in m_1 \Longleftrightarrow (i_j) \in m_2. \] \end{itemize} Otherwise, we say that $m_2$ \emph{avoids} $m_1$. For two sets of matchings $\M_1 \subseteq \M_{N_1}$ and $\M_2 \subseteq \M_{N_2}$, denote by $\M_2(\M_1)$ the set of matchings in $\M_2$ that avoid every matching in $\M_1$. In addition, denote $\M_2(m) := \M_2(\{m\})$ for a matching $m$. \end{definition} The following problem is analogous to the problem of Sagan and Woo~\cite{problem_find_pattern} regarding pattern-avoiding permutations: \begin{problem} \label{prob:schur positive pattern avoiding matchings} Determine which sets $\M \subseteq \M_N$ of matchings satisfy the property that for all $N',f'$, the pattern-avoiding set $\M_{N',f'}(\M)$ is Schur-positive with respect to $\Short$. \end{problem} While a complete solution of Problem~\ref{prob:schur positive pattern avoiding matchings} seems challenging, we are able to solve the problem in the case where $|\M| = 1$. \begin{proposition} \label{prop:characterize pattern avoiding schur positive singletons} Let $N$ be a nonnegative integer, and let $m \in \M_N$ be a matching. Then the pattern-avoiding set $\M_{N',f'}(m)$ is Schur-positive with respect to $\Short$ for all $N',f'$ if and only if one of the following holds: \begin{enumerate} \item $\Short(m) = \emptyset$, or \item $m=\{(1,2)\}$, the unique perfect matching on two vertices. \end{enumerate} \end{proposition} In the proof of Proposition~\ref{prop:characterize pattern avoiding schur positive singletons}, we will apply the following result: \begin{lemma} \label{lem:avoiding set of short chord free matching is knuth like closed} Let $m \in \M_N$ be a short-chord-free matching, and let $N',f'$ be nonnegative integers. Then the pattern-avoiding set $\M_{N',f'}(m)$ is closed under Knuth equivalence. \end{lemma} \begin{proof} Let $m_1' \in \M_{N',f'}$ be a matching, and let $m_2' \in \M_{N',f'}$ be the result of applying an elementary Knuth transformation on $m_1'$. Assume that $m_1'$ contains the pattern $m$. It suffices to prove that $m_2$ contains $m$ too. By Definition~\ref{def:pattern avoidance}, there exist indices $1 \le i_1 < \dots < i_{N} \le N'$ such that $(j,j') \in m \Longleftrightarrow (i_j,i_{j'}) \in m_1'$ for all $1 \le j < j' \le N$ and $(j) \in m \Longleftrightarrow (i_j) \in m_1'$ for all $1 \le j \le N$. Without loss of generality, we may assume that $(i,i+1) \in m_1'$ and $m_2'$ is obtained from $m_1'$ by interchanging the chord $(i,i+1)$ with the vertex $i+2$. The pattern $m$ is short-chord-free, so $i, i+1 \notin \{i_1,\dots,i_N\}$. Therefore, by considering the index set $\{i_1,\dots,i_N\}$ if $i+2 \notin \{i_1,\dots,i_N\}$ and the set $\{i\}\cup\{i_1,\dots,i_N\} \setminus \{i+2\}$ otherwise, we obtain that the matching $m_2'$ contains $m$ as well. \end{proof} Now, let us prove Proposition~\ref{prop:characterize pattern avoiding schur positive singletons}: \begin{proof}[Proof of Proposition~\ref{prop:characterize pattern avoiding schur positive singletons}] Denote by $f$ the number of unmatched vertices of $m$, and assume that $\M_{N',f'}(m)$ is Schur-positive for all $N',f'$. In particular, we may take $N'=N$ and $f'=f$ and obtain that the set $\M_{N,f}(m)$ is Schur-positive. Since $\M_{N,f}(m) = \M_{N,f} \setminus \{m\}$, we obtain that the generating function $\Q(\M_{N,f} \setminus \{m\})$ is Schur-positive and, as such, symmetric. Clearly, \[ \Q(\M_{N,f} \setminus \{m\})=\Q(\M_{N,f})-\Q(\{m\}). \] By Theorem~\ref{thm:matchings schur positive}, the function $\Q(\M_{N,f})$ is symmetric, so the function $\Q(\{m\}) = F_{\Short(m)}$ is symmetric as well. By Lemma~\ref{lem:singleton not symmetric}, we may deduce that $\Short(m) = \emptyset$ or $\Short(m) = [N-1]$. If $\Short(m) = \emptyset$ then the statement holds. Otherwise, $\Short(m) = [N-1]$. The statistic $\Short$ is sparse (recall Definition~\ref{def:sparse}), so we may deduce that $N\le 2$. If $N=2$ then $\Short(m)=\{1\}$, and therefore $m=\{(1,2)\}$. If $N=1$ then $\Short(m)= \emptyset$. On the other hand, we assume that $\Short(m) = \emptyset$ or $m=\{(1,2)\}$ and prove that $\M_{N',f'}(m)$ is Schur-positive for all $N',f'$. \begin{enumerate} \item Assume that $\Short(m) = \emptyset$, and let $N',f'$ be nonnegative integers. By Lemma~\ref{lem:avoiding set of short chord free matching is knuth like closed}, the set $\M_{N',f'}(m)$ is closed under Knuth equivalence. Therefore, by Corollary~\ref{cor:closed under knuth like is schur positive}, it is Schur-positive. \item Assume that $m=\{(1,2)\}$, and let $N',f'$ be nonnegative integers. Notice that a matching avoids the pattern $m$ if and only if it is an empty matching (\ie with all its vertices unmatched). By Definition~\ref{def:knuth like equivalence}, such a matching is Knuth equivalent only to itself, so $\M_{N',f'}(m)$ is closed under Knuth equivalence. Therefore by Corollary~\ref{cor:closed under knuth like is schur positive}, $\M_{N',f'}(m)$ is Schur-positive. \qedhere \end{enumerate} \end{proof} \section{Further remarks and open problems} \label{sec:further research} \subsection{Criteria for special cases of Schur-positivity} There is a simple well-known criterion for sets under which the generating function $\Q_{D}(\A)$ is non-negatively spanned by the Schur functions of hook shape $s_{N-k,1^k}$: \begin{proposition}[folklore] \label{prop:hook schur positive} A set $\A$ with a statistic $D:\A \to 2^{[N-1]}$ has a generating function of the form \[ \Q_{D}(\A) = \sum_{k=0}^{N-1} c_k s_{N-k,1^k},\ c_k \in \NN \] if and only if for every $J \subseteq [N-1]$, $|\{a \in \A \mid D(a) = J\}|$ depends only on $|J|$. In that case, $c_k = |\{a \in \A \mid D(a) = [k]\}|$. \end{proposition} \begin{proof} On one hand, assume that there exist $c_k \in \NN$ such that $|\A(D=J)| = c_{|J|}$ for all $J \subseteq [N-1]$. Notice that every tableau of a hook shape $T \in \Syt(N-k,1^k)$ has $|\Des(T)| = k$. Conversely, for every set $J \subseteq [N-1]$ with $|J| = k$ there exists a unique tableau $T \in \Syt(N-k,1^k)$ such that $\Des(T) = J$. Therefore, we obtain the equation \[ \sum_{a \in \A} \boldsymbol{t}^{D(a)} = \sum_{k=0}^{N-1} c_k \sum_{T \in \Syt(N-k,1^k)} \boldsymbol{t}^{\Des(T)}, \] where $\boldsymbol{t}^J := \prod_{j \in J} t_j$ for $J \subseteq [N-1]$. By Theorem~\ref{thm:criterion schur positive young}, this equation implies the statement. The other direction of the proposition states that if $\Q_{D}(\A) = \sum_{k=0}^{N-1} c_k s_{N-k,1^k}$, then $|\{a \in \A \mid D(a) = J\}| = c_{|J|}$. Adin and Roichman \cite[Corollary 8.1]{adin_roichman_fine_set} established that a generating function uniquely determines the descent set distribution, which implies the statement. \end{proof} Similarly to Proposition~\ref{prop:hook schur positive}, Theorem~\ref{thm:criterion schur positive two rows} provides a simple criterion under which $\Q_{D}(\A)$ is non-negatively spanned by the Schur functions of two-row shape $\{s_{N-k,k} \mid 0 \le k \le n\}$. In the spirit of discovering new methods and expanding our understanding, we pose the problem of finding other such criteria, hopeful that they will contribute to further advancements in the study of Schur-positivity and Schur coefficients. \begin{problem} Find other sets of partitions $\Lambda \subseteq \{\lambda \vdash N\}$ and criteria for a given set $\A$ under which $\Q_{D}(\A)$ is non-negatively spanned by the functions $\{s_\lambda \mid \lambda \in \Lambda\}$.% \end{problem} \subsection{Short chords of matchings} Theorem~\ref{thm:matchings schur positive} shows that the set $\M_{N,f}$ of matchings with a given number of unmatched vertices is Schur-positive with respect to the set of short chords, and describes its Schur expansion. In Section~\ref{sec:refinements}, several Schur-positive subsets of $\M_{N,f}$ are presented too. All these sets are shown to be closed under Knuth equivalence (described in Definition~\ref{def:knuth like equivalence}), so their Schur-positivity can be derived from Corollary~\ref{cor:closed under knuth like is schur positive}. It is desired to find Schur-positive sets of other types. \begin{problem} Find other Schur-positive subsets of $\M_{N,f}$ with respect to $\Short$. In particular, find Schur-positive subsets that are not closed under Knuth equivalence. \end{problem} Schur-positive sets of particular interest are pattern-avoiding sets. As discussed earlier in Section~\ref{subsec:pattern avoiding matchings}, Schur-positivity of pattern-avoiding sets was extensively studied in the context of permutations. Recall the problem stated in Section~\ref{subsec:pattern avoiding matchings}: \begin{problem*}[Problem~\ref{prob:schur positive pattern avoiding matchings} above] Determine which sets $\M \subseteq \M_N$ of matchings satisfy the property that for all $N',f'$, the pattern-avoiding set $\M_{N',f'}(\M)$ is Schur-positive with respect to $\Short$. \end{problem*} Proposition~\ref{prop:characterize pattern avoiding schur positive singletons} solves this problem for pattern sets of size $1$. We do not know a general answer for larger pattern sets. The connection identified between the Schur expansion of $\M_{N,f}$ and Bessel polynomials, as revealed in Corollary~\ref{cor:schur expansion bessel}, serves as motivation to investigate the Schur expansion of additional sets: \begin{problem}[Sergi Elizalde, personal communication] Find the Schur expansion of Schur-positive sets of matchings. For instance, find the Schur expansion of the set of $k$-crossing matchings in $\M_{N,f}$, or the Schur expansion of Schur-positive pattern-avoiding sets. \end{problem} \subsection{The involutive length} \label{subsec:schreier graph of perfect matchings} Here, we discuss one of the primary motivations behind this research. We denote by $\I_{2n}$ the set of fixed-point-free involutions in the symmetric group $S_{2n}$. Furthermore, we define the \emph{simple reflections} $s_i = (i,i+1) \in S_{2n}$ for $1 \le i < 2n$, and denote $w_0 = (1,2)(3,4)\cdots (2n-1,2n)$. Adin, Postnikov, and Roichman~\cite{gelfand_involutions} defined the \emph{involutive length} of an involution $w \in \I_{2n}$ as \[ \hat{\ell}(w) := \min\{k \mid s_{i_1}\cdots s_{i_k} w (s_{i_1}\cdots s_{i_k})^{-1} = w_0,\ 1 \le i_1,\dots,i_k <2n\}. \] They also defined the \emph{involutive weak order} $\le_\I$ on $\I_{2n}$, as the reflexive and transitive closure of the relation $w \prec_\I s_i w s_i$ if $\hat{\ell}(s_i w s_i) = \hat{\ell}(w) + 1$. The involutive order is motivated by the Bruhat order defined for Coxeter groups \cite[Chapter 2]{bjorner2005combinatorics}. Since fixed-point-free involutions in $S_{2n}$ naturally correspond to perfect matchings on $2n$ vertices, we will adopt the involutive length and the involutive weak order for perfect matchings in $\PM_{2n} := \M_{2n,0}$ and use the same notation for them. Consider the natural action of $S_{2n}$ on the set $\PM_{2n}$, and denote $m_0 = \{(1,2),\; (3,4),\dots,\;\allowbreak (2n-1,2n)\}$. Notably, the stabilizer of $m_0$ is isomorphic to the hyperoctahedral group $H_n = S_2 \wr S_n$. Furthermore, consider the Schreier graph associated with this action with respect to the simple reflections. % For an illustration of this Schreier graph, see Figure~\ref{fig:schreier graph example} which depicts it when $2n=4$. \begin{figure}[htb] \begin{center} \usetikzlibrary{shapes} \begin{tikzpicture}[node distance={15mm}, thick, main/.style = {draw, ellipse, scale=1}] \node[main] (1) {$12|34$}; \node[main] (2) [above of=1] {$13|24$}; \node[main] (3) [above of=2] {$14|23$}; \draw (1) to (2) node[below=23pt,right, scale=1] {$2$}; \draw (2) to[looseness=1.5, in=-50, out=50] (3) node[below=23pt,right=15pt, scale=1] {$3$}; \draw (2) to[looseness=1.5, in=-130, out=130] (3) node[below=23pt,left=15pt, scale=1] {$1$}; \draw (1) to [out=160,in=200,looseness=5] (1) node[below=0pt,left=39pt, scale=1] {$1$}; \draw (1) to [out=20,in=-20,looseness=5] (1) node[below=0pt,right=39pt, scale=1] {$3$}; \draw (3) to [out=160,in=200,looseness=5] (3) node[below=0pt,left=39pt, scale=1] {$2$}; \end{tikzpicture} \end{center} \caption{Schreier graph of the natural action of $S_4$ on $\PM_4$} \label{fig:schreier graph example} \end{figure} We can create a layered graph by partitioning the vertices (matchings) into layers based on their distance from $m_0$. Specifically, a matching in the $\ell$-th layer is at a distance of $\ell$ from $m_0$. Furthermore, Avni~\cite{avni_perfect_matchings} proved that this graph is bipartite when ignoring loops. Therefore, a matching in one layer is connected to matchings in the adjacent layers, but not within its own layer or to matchings in non-adjacent layers.% It turns out that this graph corresponds to the involutive length and the involutive weak order. First, the index of the layer of a matching $m$ is equal to its involutive length $\hat{\ell}(m)$. Moreover, for every $m_1, m_2 \in \PM_{2n}$ we have $m_1 \le_\I m_2$ if and only if there exists a geodesic path from $m_0$ to $m_2$ passing through $m_1$. Based on the structure of the Schreier graph, we define three natural set-valued functions on perfect matchings, denoted by $\Asc(m)$, $\Loop(m)$, and $\Des(m)$, where $m$ is a matching in $\PM_{2n}$. Given a matching $m \in \PM_{2n}$ and an index $1 \leq i \leq 2n-1$, we define: \begin{itemize} \item $i \in \Asc(m)$ if $s_i \cdot m >_\I m$, where the dot denotes the group action, \item $i \in \Des(m)$ if $s_i \cdot m <_\I m$, and \item $i \in \Loop(m)$ if $s_i \cdot m = m$. \end{itemize} It is noteworthy that $i\in \Asc(m)$ if and only if $\hat{\ell}(s_i \cdot m) > \hat{\ell}(m)$, $i\in \Des(m)$ if and only if $\hat{\ell}(s_i \cdot m) < \hat{\ell}(m)$, and $i\in \Loop(m)$ if and only if $\hat{\ell}(s_i \cdot m) = \hat{\ell}(m)$. The algebraic interest of the graph motivates the analysis of these three statistics, specifically focusing on the question of the Schur-positivity of $\PM_{2n}$ with respect to each of them. As a first step in this direction, it is noteworthy that the definition of $\Asc$ coincides with the standard ascents of permutations when restricted to $\I_{2n}$. Consequently, the Schur-positivity of $\PM_{2n}$ with respect to $\Asc$ can be derived directly from classical properties of the Robinson-Schensted correspondence, as noted for example by Gessel and Reutenauer \cite[end of Section 7]{gessel1993counting}. Moreover, we have the observation $\Loop(m) = \Short(m)$ for a perfect matching $m$. This observation, when combined with Theorem~\ref{thm:matchings schur positive}, implies that $\PM_{2n}$ is Schur-positive with respect to $\Loop$. In contrast, the Schur-positivity of $\PM_{2n}$ with respect to $\Des$ remains a mystery. \begin{question}[Ron Adin and Yuval Roichman, personal communication] Is $\PM_{2n}$ Schur-positive with respect to $\Des$? \end{question} Despite extensive analysis of the $\Des$ statistic, we are currently unable to provide an answer. However, based on experimental results from simulations, we have discovered that $\PM_{2n}$ is Schur-positive with respect to $\Des$ when $2n \leq 14$. Moreover, intriguingly, the statistics $\Asc$ and $\Des$ are found to be equidistributed for all $2n \leq 14$. These findings lead us to propose the following conjecture: \begin{conjecture}[Ron Adin and Yuval Roichman, personal communication] For all $n \in \NN$, \[ \sum_{m \in \PM_{2n}} \boldsymbol{t}^{\Asc(m)} = \sum_{m \in \PM_{2n}} \boldsymbol{t}^{\Des(m)}, \] where $\boldsymbol{t}^J := \prod_{j \in J} t_j$ for $J \subseteq [2n-1]$. \end{conjecture} If this conjecture can be proven, it would establish the Schur-positivity of $\PM_{2n}$ with respect to $\Des$. Furthermore, a bijection on $\PM_{2n}$ that maps ascents to descents may unveil hidden symmetries within the Schreier graph. \longthanks{My sincere thanks to my supervisors, Ron Adin and Yuval Roichman, for their constant support. I also wish to thank Yotam Shomroni, Noam Ta-Shma and Ohad Sheinfeld, for enlightening discussions and valuable editing suggestions. Special appreciation goes to Sergi Elizalde and Bruce Sagan for their insightful comments and suggestions, which significantly contributed to refining the paper.} \bibliographystyle{mersenne-plain} \bibliography{ALCO_Marmor_1001} \end{document}