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}$?


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.

  • $\begingroup$ 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?) $\endgroup$ – Martin Rubey Jan 27 '14 at 8:39
  • $\begingroup$ 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. $\endgroup$ – Sam Hopkins Jan 27 '14 at 16:01
  • $\begingroup$ 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)$. $\endgroup$ – Sam Hopkins Jan 27 '14 at 16:07

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.

  • 1
    $\begingroup$ 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}$. $\endgroup$ – Harry Altman Jan 24 '14 at 2:13
  • $\begingroup$ 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. $\endgroup$ – Sam Hopkins Jan 24 '14 at 2:27
  • $\begingroup$ Yes, I see that I didn't read carefully enough. $\endgroup$ – Brendan McKay Jan 24 '14 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.