# Homomesy in perfect matchings

Assume $n \geq 2$. Let $\mathcal{M}_n$ denote the set of perfect matchings on $[2n] := \{1,\ldots,2n\}$, i.e., the set of partitions of $[2n]$ into pairs. For $M \in \mathcal{M}_n$, and $p = \{a,b\}$,$q = \{c,d\} \in M$ with $a < b$, $c < d$, and $a<c$, we say the pairs $p$ and $q$ are aligned if $a < b < c < d$. Denote the number of alignments of a matching $M$ by \mathrm{al}(M) := |\{ \{p,q\} \subset M\colon p \textrm{ and } q \textrm{ are aligned}\}|.

Is it possible to find a partition $O_n$ of $\mathcal{M}_n$ so that for every $\mathcal{O} \in O_n$ we have

1. $|\mathcal{O}| = 3$;
2. $\sum_{M \in \mathcal{O}} \mathrm{al}(M) = \binom{n}{2}$?

EDIT:

I can add the following context to the problem if it helps. Recall that we say $p$ and $q$ are nesting if $a < c < d < b$ and we say they are crossing if $a < c < b < d$. Let $\mathrm{ne}(M)$ denote the number of nestings of $M$, and $\mathrm{cr}(M)$ the number of crossings. The statement would follow easily if we had $\sum_{M \in \mathcal{M}_n} x_1^{\mathrm{ne}(M)}x_2^{\mathrm{cr}(M)}x_3^{\mathrm{al}(M)} = \sum_{M \in \mathcal{M}_n} x_{w(1)}^{\mathrm{ne}(M)}x_{w(2)}^{\mathrm{cr}(M)}x_{w(3)}^{\mathrm{al}(M)}$ for all $w \in S_3$, the symmetric group on three letters. However this is not the case: nestings, crossings, and alignments are not all equidistributed (although nestings and crossings are). Still, I expect a kind of $S_3$ symmetry with respect to nestings, crossings, and alignments in the form of homomesy (as the title of the question suggests). Recall from Propp and Roby that for a set of combinatorial objects $\mathcal{S}$ and an invertible map $\varphi\colon \mathcal{S} \to \mathcal{S}$ we say the statistic $f\colon \mathcal{S} \to K$ is homomesic with respect to the action of $\varphi$ on $\mathcal{S}$ if $\sum_{x \in \mathcal{O}}f(x)$ is constant among all $\varphi$-orbits $\mathcal{O}$.

Let $\mathrm{Aut}(\mathcal{M}_n)$ denote the group of invertible maps from $\mathcal{M}_n$ to $\mathcal{M}_n$. What I really want to find is some $\tau \in \mathrm{Aut}(\mathcal{M})$ with $\tau^3 = \mathrm{id}$ and such that $\mathrm{al}(\cdot)$ is homomesic with respect to the action of $\tau$ on $\mathcal{M}_n$. Ideally $\tau$ would also satisfy $(\tau \sigma)^2 = \mathrm{id}$, where $\sigma \in \mathrm{Aut}(\mathcal{M}_n)$ is the involution that swaps nestings and crossings defined in this paper of De Medicis and Viennot (see also this paper for a description of the algorithm in English). If this were possible, then defining $\Gamma := \langle \tau, \sigma \rangle \subset \mathrm{Aut}(\mathcal{M}_n)$, we would have $\Gamma \simeq S_3$ and all three of the statistics $\mathrm{ne}(\cdot)$, $\mathrm{cr}(\cdot)$, and $\mathrm{al}(\cdot)$ are homomesic with respect to the action of $\Gamma$ on $\mathcal{M}_n$. This would be interesting as it would be the first instance of non-cyclic (indeed, non-abelian) homomesy that I am aware of.

• Hi Sam! Did you check that there is one for n=3? (In this case there are 15 matchings, and therefore 1401400 set partitions to check, which should be possible even by brute force, no?) – Martin Rubey Jan 27 '14 at 8:39
• It is easy to do $n=3$ by hand (and in fact there are many valid choices already). I also saw that $n=4,5$ are possible with the help of Sage. It actually seems like the flexibility is increasing with $n$, so more interesting to me than an argument that such a partition must exist (by probabilistic arguments, e.g.) would be an explicit description of $\tau$, especially if this map is combinatorially meaningful. – Sam Hopkins Jan 27 '14 at 16:01
• Here is another potentially useful observation: let $\mathcal{D}_n$ denote the set of Dyck sequences, i.e. the set of maps $\varphi\colon [2n] \to \{U,D\}$ such that $|\varphi^{-1}(U) \cap [i]| \geq |\varphi^{-1}(D) \cap [i]|$ for all $i \in [2n]$. There is a natural surjection $\mathrm{type}\colon \mathcal{M}_n \to \mathcal{D}_n$, and $\mathrm{al}(M)$ is determined by $\mathrm{type}(M)$. – Sam Hopkins Jan 27 '14 at 16:07

## 1 Answer

If I understand the way things are counted, the maximum possible value of $\mathrm{al}(M)$ is $\binom{n/2}{2}$. Since this is less than half $\binom{n}{2}$, there is no way to put a matching having no aligned pairs with two other matchings so that the total number of alignments is $\binom{n}{2}$,

So the answer is "no".

ADDED: Withdrawn for the reasons noted in the comments.

• Unfortunately the perfect matching is on $\{1,\ldots,2n\}$, rather than $\{1,\ldots,n\}$, so the maximum value of $\mathrm{al}(M)$ is $\binom{n}{2}$. – Harry Altman Jan 24 '14 at 2:13
• Yes the maximum value of $\mathrm{al}(M)$ is $\binom{n}{2}$, attained uniquely. Fortunately we can pair this matching with two matchings with no alignments: the natural choice appears to be the matching where all pairs cross and the matching where all pairs nest. – Sam Hopkins Jan 24 '14 at 2:27
• Yes, I see that I didn't read carefully enough. – Brendan McKay Jan 24 '14 at 4:48