10
$\begingroup$

I am not sure if it is appropriate to use MathOverflow to publicize a conjecture, but I think this is an interesting question and I have no real ideas of how to solve it.

A permutation on a $n$-element poset $P$ is a list $\sigma = (\sigma_1,\ldots,\sigma_n)$ of the elements of $P$ in some order. We say $\sigma$ contains a permutation $\pi = (\pi_1,\ldots,\pi_k)$ (which we call a pattern) on the $k$-element poset $Q$ if there is some subsequence $\sigma_{i_1},\ldots,\sigma_{i_k}$ with $i_1 < \cdots < i_k$ order-isomorphic to $\pi$: i.e., $\sigma_{i_r} < \sigma_{i_s}$ iff $\pi_{r} < \pi_{s}$ for all $1 \leq r,s \leq k$. If $\sigma$ does not contain $\pi$ then $\sigma$ avoids $\pi$. We write $\pi = \pi_1\cdots\pi_k$ for a pattern instead of using parentheses. Let $\mathrm{Av}_P(\pi)$ denote the number of permutations on $P$ that avoid $\pi$.

In http://arxiv.org/abs/1208.5718 Morgan Weiler and I show that $\mathrm{Av}_P(132) \leq \mathrm{Av}_P(123)$ for all finite posets $P$. (Here $1,2,3$ are elements of the chain poset $1 < 2 < 3$.)

Question: Is it the case that $\mathrm{Av}_P(\{1\}\{1,2\}\{2\}) \leq \mathrm{Av}_P(\{1\}\{2\}\{1,2\})$ for all finite posets $P$? (Here $\{1\},\{2\},\{1,2\}$ are ordered by containment.) This is the case for all posets on seven or fewer elements.

$\endgroup$
1

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.