4
$\begingroup$

Partly inspired by recent developments in enumeration of pattern avoiding permutations, which is known to be connected with Brownian excursions [Hoffman&Rizzolo]. The exciting milestone is the solution of Stanley–Wilf conjecture (BTW Wilf is the same person in this post) in 2004 [Marcus&Tardos] characterizing the pattern-avoiding permutations by limiting the number of such permutations to be $C^n$($C$ being constant) among all permutation of length $n$ in $\mathcal{S}_n$. And Fox showed that the $C$ is almost surely exponential[Fox].

The problem I have in mind is about random permutations acting on a fixed set $M$.


(1) If we put a uniform distribution over $\mathcal{S}_n$, i.e. $Pr(S=S_i)=\frac {1}{n}$ for $\forall i=1,2,\cdots n,S\in\mathcal{S}_n$ and let such a random permutation $S$ act on another fixed set $M\subset\mathbb{R}^{n\times n}$ of matrices of compatible dimensions. Is there existing result stating that by choosing $M$ appropriately, the resulting $S(M)$ will follow some kind of probability law?

(2) Now if we put a uniform distribution over $\mathcal{S}_n(\beta )$ of the collection of $\beta$-avoiding permutations, with the same question in (1), is it possible to choose the set $M\subset\mathbb{R}^{n\times n}$ to make $S(M)$ follow some kind of probability law?

(3)If the answer to (1)(2) are affirmative, what will such a probability law look like when $n\rightarrow\infty$? Will it break down?

I primarily thought of (2) but later think (1) will be easier to illustrate.

Reference

[Fox]Fox, Jacob. "Stanley-Wilf limits are typically exponential." arXiv preprint arXiv:1310.8378 (2013).

[Hoffman&Rizzolo]Hoffman, Christopher, Douglas Rizzolo, and Erik Slivken. "Pattern avoiding permutations and Brownian excursion." arXiv preprint arXiv:1406.5156 (2014). http://www.stat.berkeley.edu/~aldous/Pitman_Conference/Slides/DouglasRizzolo.pdf

[Marcus&Tardos]Marcus, Adam, and Gábor Tardos. "Excluded permutation matrices and the Stanley–Wilf conjecture." Journal of Combinatorial Theory, Series A 107.1 (2004): 153-160.

$\endgroup$
1
  • $\begingroup$ I made another simplification of original problem by restricting ourselves to uniform distribution, if there are some results about non-uniform distributions I would be very interested to know! $\endgroup$
    – Henry.L
    Jul 17, 2017 at 21:08

0

Your Answer

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