Unimodality conjecture for pattern occurrences in Mallows permutations

At least 2 years old · documented by 2023

Let $\boldsymbol{\sigma}_{n,p}$ be a Mallows random permutation of $[n]$ with parameter $p\in[0,\infty)$ . For a permutation pattern $\pi$ , let $\mathbb{E}_{n,p}(\pi)$ denote the expected number of occurrences of $\pi$ in $\boldsymbol{\sigma}_{n,p}$ .

Mallows unimodality conjecture. If $\pi$ is any consecutive permutation pattern, then the function $p\mapsto\mathbb{E}_{n,p}(\pi)$ is unimodal.

The conjecture is motivated by the analogous expected-occurrence conjecture for permutations with a fixed number of inversions. The source gives no proof or resolution.

References

Primary source

David Bevan and Dan Threlfall, “Thresholds for patterns in random permutations with a given number of inversions”, arXiv:2312.01182 (2024).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A reader-posted argument claims a complete proof that the expected number of consecutive pattern appearances rises and then falls as the Mallows parameter changes, but no independent verification is reported.

Bevan and Threlfall formulate the Mallows unimodality conjecture: for every consecutive pattern, its expected number of appearances is unimodal in the parameter. Their paper records this as Conjecture 28 rather than a theorem.

Known results

Crane, DeSalvo, and Elizalde give an exact formula for the expected count of a consecutive pattern in a Mallows permutation, depending on its inversion number; they do not prove unimodality.

Posted attempt

A reader-posted argument claims a complete proof: it reduces the expectation to a pattern inversion weight divided by the Mallows inversion generating function, then claims strict log-concavity in the logarithm of the parameter. The argument has not been independently verified.

Current status (as of August 2026): The primary paper records the conjecture as open, while a complete proof claim has appeared in reader discussion without independent verification; no confirmed proof or counterexample is reported.

Sources

ProofThis solution needs a summarySee full solutionHide full solution

Full proof, with strict log-parameter concavity and an exact characterization of the maximum.

Let $\pi\in S_k$ , put $s=\operatorname{inv}(\pi)$ , and write

Z_k(p)=\sum_{\tau\in S_k}p^{\operatorname{inv}(\tau)} =\prod_{j=1}^k(1+p+\cdots+p^{j-1}).

The consecutive-homogeneity property of the Mallows distribution gives, at every position $i$ ,

\mathbb P_p\!\left( \operatorname{pat}(\sigma(i),\ldots,\sigma(i+k-1))=\pi \right)=\frac{p^s}{Z_k(p)}.

Indeed, condition on the set of values occupying this consecutive block and on the entire outside configuration. Every outside position lies wholly to the left or right of the block, so the cross-block inversion count depends only on its set of values, not on their internal ordering. The conditional weight of each internal relative ordering $\tau$ is therefore proportional to $p^{\operatorname{inv}(\tau)}$ .

Summing over the $n-k+1$ possible positions yields

\mathbb E_{n,p}(\pi) =(n-k+1)\frac{p^s}{Z_k(p)}. \tag{1}

This exact expectation is already contained in Crane, DeSalvo, and Elizalde, The probability of avoiding consecutive patterns in the Mallows distribution, Theorem 8.1, equation (33). The remaining issue in the present conjecture is unimodality as the parameter varies.

For $p>0$ , set $\theta=\log p$ , and let $I$ be the inversion count of a Mallows permutation of length $k$ at parameter $e^\theta$ . Differentiating (1) gives

\frac{d}{d\theta} \log\mathbb E_{n,e^\theta}(\pi) =s-\mathbb E_\theta[I],

and, more strongly,

\frac{d^2}{d\theta^2} \log\mathbb E_{n,e^\theta}(\pi) =-\operatorname{Var}_\theta(I)<0 \qquad(k\ge2). \tag{2}

The variance is strictly positive because both the identity and a permutation with one inversion have positive probability at every finite $\theta$ . Thus the expectation is strictly log-concave as a function of $\log p$ .

Writing $K=\binom{k}{2}$ , the mean $\mathbb E_\theta[I]$ increases continuously and strictly from $0$ to $K$ . Therefore:

If $0<s<K$ , there is a unique maximizer $p_s>0$ , characterized by $\mathbb E_{p_s}[I]=s$ ; the expectation strictly increases before $p_s$ and strictly decreases afterwards.
If $s=0$ , the expectation strictly decreases and attains its maximum at $p=0$ .
If $s=K$ , it strictly increases and tends to $n-k+1$ as $p\to\infty$ .
For $k=1$ the expectation is constant; if $n<k$ , it is identically zero.

This proves the conjecture for every consecutive pattern, every $n$ , and the entire parameter range $p\in[0,\infty)$ .

Source: Bevan and Threlfall, Thresholds for Patterns in Random Permutations with a Given Number of Inversions, Electronic Journal of Combinatorics 31(4) (2024), Conjecture 28.