Funciones combinatorias de Morse y permutaciones aleatorias

Question

Esta pregunta tiene su origen en la topología combinatoria. En la década de los 90 R. Forman propuesto un discreto contraparte de Morse de la teoría. En su caso, una función de Morse en un triangular espacio es una función que asigna un número a cada cara y el cumplimiento de determinadas condiciones.

La teoría ha encontrado hermosa aplicaciones, pero tiene una limitación: discreta Morse funciones son difíciles de encontrar, a diferencia de la lisa caso de que lisa Morse funciones son una moneda de diez centavos por docena. Eso me hizo pensar que tal vez no hay muchos de esos discretos funciones de Morse. Así que, naturalmente, uno puede preguntar, ¿de verdad muchas Morse funciones existen en un determinado espacio triangular.

La cuestión se trata con la más simple triangular espacio, es decir, un segmento de línea que divide en $n$-subintervalos. El problema de contar el Morse combinatoria de las funciones de este triangular espacio se reduce a la siguiente puramente combinatoria problema.

Considerar el grupo $S_{2n+1}$ de las permutaciones del conjunto

$$ V_n:=\lbrace 0,1,\dotsc,2n\rbrace. $$

Un punto de $i\in V_n$ es llamado un punto interior si $i\neq 0,2n$. Un punto interior $i\in V_n$ es un mínimo local de una permutación $\phi\in S_{2n+1}$ si

$$ \phi(i-1)> \phi(i) <\phi(i+1). $$

Un máximo local es definido de una manera similar. Aquí está la pregunta.

Denotar por $p_n$ la probabilidad de que una permutación aleatoria de $S_{2n+1}$ ha la propiedad de que todos sus interiores mínimos locales (si alguna) son incluso y todos sus el interior de los máximos locales (si alguna) son impares. Es verdadero (como yo creo) que $p_n\to 0$ as $n\to\infty$? Puede para ser más precisos acerca de la el comportamiento de $p_n$ as $n\to\infty$?

Por ejemplo, cuando se $n=1$ las permutaciones de $\lbrace0,1,2\rbrace$ la satisfacción de las restricciones anteriores se

$$ (0,1,2), (2,1,0), (0,2,1), (1,2,0). $$

Por lo tanto $p_1=\frac{2}{3}$.

Gracias.

Answer 1

Este es un boceto de una solución por mi estudiante Yan Zhuang y a mí. Un papel con todos los detalles (y resultados) se puede encontrar en el Conteo de permutaciones por la alternancia de los descensos, Electrónica J. Combinat. 21 (4) (2014), El Papel #P4.23.

Nos encontramos con la exacta exponencial de generación de función para el recuento de estas permutaciones y se derivan de la asymptotics de ella.

En primer lugar, no hay ninguna razón de la enumerativa punto de vista a considerar sólo las permutaciones de longitud impar. Así que vamos a $u_n$ el número de permutaciones de $\{1,2,\dots, n\}$, en la que cada pico es uniforme y cada valle es impar, donde un pico de $\pi\in S_n$ es $i$, con $1<i<n$, de tal manera que $\pi(i-1)<\pi(i)>\pi(i+1)$, y los valles se definen de manera similar. El primer par de valores de $u_n$ son $u_0=1$, $u_1=1$, $u_2=2$,$u_3=4$, $u_4=13$, $u_5=50$, $u_6=229$. Vamos \begin{equation} U(x) = \sum_{n=0}^\infty u_n \frac{x^n}{n!}.\end{equation} La mejor fórmula para $U(x)$ es \begin{equation} U(x) = \left( 1-E_1x +E_3 \frac{x^3}{3!}-E_4\frac{x^4}{4!}+E_6\frac{x^6}{6!}-E_7\frac{x^7}{7!} +\cdots\right)^{-1}, \tag{1}\end{equation} donde $$\sum_{n=0}^\infty E_n \frac{x^n}{n!} = \sec x + \tan x.$$ Una fórmula equivalente a (1), que es el más útil para asymptotics es \begin{equation}U(x) = \frac{3\sin\frac x 2 + 3\cosh \frac {\sqrt3}{2} x} {3\cos \frac x 2 -\sqrt 3\sinh \frac{\sqrt3}{2} x}. \tag{2}\end{equation}

Desde $U(x)$ es meromorphic con un solo polo en su círculo de convergencia, en $x=\alpha:=1.299828316\cdots$, nos encontramos por técnicas estándar que $u_n/n!$ es asintótica a $2\beta^{n+1}$ donde $\beta:=\alpha^{-1}=.7693323708\cdots$.

La fórmula (2) puede ser probado por la búsqueda de una recurrencia de $u_n$, la conversión de una ecuación diferencial, y la solución. (Necesitamos utilizar un auxiliar de la secuencia, y considerar la posibilidad de pares e impares $n$ por separado, por lo que realmente conseguir un sistema de cuatro ecuaciones diferenciales.)

Podemos dar una más conceptual de la prueba de (1). Primero nos tenga en cuenta que el aspecto similar exponencial de generación de función \begin{equation}\left( 1-x + \frac{x^3}{3!}-\frac{x^4}{4!}+\frac{x^6}{6!}-\frac{x^7}{7!} +\cdots\right)^{-1}\tag{3}\end{equation} (OEIS secuencia A049774) cuenta permutaciones sin aumento de la ejecución de longitud mayor que 2.

Podemos definir una alternancia de ejecución de una permutación $\pi$ a un máximo larga de la forma $\pi(2i)<\pi(2i+1)>\pi(2i+2)<\cdots\mathrel{<\atop >}\pi(j)$ o $\pi(2i+1)>\pi(2i+2)<\pi(2i+3)>\cdots \mathrel{<\atop >}\pi(j)$. A continuación, las permutaciones contado por $u_n$ son permutaciones sin alternando correr de longitud mayor que 2, y (1) puede ser probado de una manera que es análoga a la prueba de (3).

Las fórmulas que involucran los números de $E_n$ y "la alternancia de los descensos", utilizando la misma idea básica, se han probado por Denis Chebikin, Las variaciones en los descensos y las inversiones en las permutaciones, Electrónica J. Combinat. 15 (2008), Trabajo De Investigación R132.

Answer 2

La propuesta de Karl Waugh puede ser fijo. Que nos llame a una permutación agradable si satisface las condiciones del problema. Vamos a $a_0 a_1\cdots a_{2n}$ be a permutation of $V_n$. Existen seis posibles orden de los números de $a_0, a_1, a_2$, todos igualmente probables. Dos de estas órdenes son incompatibles con la amabilidad, así que hay un $2/3$ la probabilidad de compatibilidad. También hay un $2/3$ de probabilidad, independiente de los valores de $a_0,a_1,a_2$ que $a_3,a_4,a_5$ son compatible con amabilidad. Continuando con este argumento da un superior enlazado de $(2/3)^{\lfloor (2n+1)/3\rfloor}\to 0$ en la probabilidad de que un permutación de $0,1,\dots,2n$ a ser agradable.

Un pensamiento adicional. La alternancia de las permutaciones son agradables. El número de $E_n$ de la alternancia de las permutaciones de $1,2,\dots,n$ (con un número de Euler) satisface $E_n\sim C(2/\pi)^nn!$. Si $f(2n+1)$ indica el número de bonito permutaciones de $V_n$, entonces esto sugiere que el límite de $$ L=\lim_{n\to \infty} \left( \frac{f(2n+1)}{(2n+1)!}\right)^{1/(2n+1)} $$ existe. Las observaciones anteriores muestran que, a continuación, $$ \frac{2}{\pi}=0.6366\cdots \leq L\leq\left(\frac 23\right)^{1/3}= 0.8735\cdots. $$ Sería interesante determinar este límite. El límite superior puede se hizo arbitraria cerca de $L$ observando los bloques de longitud $k$ (en lugar de la longitud de tres) como $k\to\infty$. Haciendo por $k=10$ rendimientos (modulo error de cálculo) un límite superior de $L\leq (405581/10!)^{1/5} = 0.64515\cdots$.

Answer 3

Originalmente pensé que la respuesta a su pregunta podría ser deducido a partir de los resultados en un artículo reciente escrito por Sara Billey, Chris Burdzy, y a mí, arXiv:1209.0693. Teorema 1.1, en la que el papel da una enumeración resultado por el número de permutaciones en S_n que tiene un determinado conjunto de cumbres (lo que usted llama interior de los máximos locales). Por desgracia, el teorema se aplica solamente si el número de elementos en el pico de conjunto es constante con respecto a n, lo cual no es cierto en este caso. Sería muy interesante encontrar un análogo de este teorema, donde el tamaño del pico de establecer varía con n.

Saludos, Bruce Sagan

PS Gracias a Richard Stanley para señalar este post para nosotros.

Answer 4

Tratando de responder a la última pregunta, creo que el siguiente debería hacerlo, pero no estoy 100% seguro.

Por un lado, podemos ver que si n=1, que exactamente 2 de los 6 permutaciones satisface la condición, hacer 1 una maxima. Si nos movemos a n=2, entonces tenemos que asegurarnos de 1 y 3 son de maxima, 2 siendo mínimas se derivan de estos.

Si nos fijamos en el movimiento de numbesr 0, 1 y 2, y "limitar" las permutaciones de estos - aka si van a 0, 4, 3, a continuación, podemos tratar de que como 0, 2, 1 mediante la reducción de los valores hasta que están en el rango - entonces no es difícil ver que por lo que 1/3 de permutaciones hacer 1 una maxima, y que una de 1/3 de hará 3 una maxima. Por lo tanto $p_2 \le 1/9$.

Una similar unido debería ser capaz de demostrar que $p_n \le (1/3)^n$ que va a satisfacer su demanda.

Answer 5

Por favor, permítame responder a una modificación de la pregunta. Parece mejor para mí contar discretos gradiente de flujos en lugar de Morse discreta funciones (por supuesto, esto es una cuestión de opinión). En el caso de la subdivisión del segmento en n subintervalos, el número discreto de gradiente de flujos es el número de elecciones en una ruta con 2n bordes. Este es el número de Fibonacci $F_{2n+1}$ (si $F_0=F_1=1$).

(Aquí tengo en cuenta el diagrama de Hasse en el poset de vacío caras de una célula compleja. Uno dirige cada borde en este diagrama de abajo, y un discreto flujo de gradiente se obtiene mediante la inversión de los bordes, de manera que cada vértice está contenida en más de un borde invertido y el resultado en forma de grafo dirigido no tiene ningún dirigida ciclos. Cada uno de Morse discreta de la función f da lugar a una discreta gradiente de flujo, dirigiendo una ventaja de cara a obtener el mayor valor por debajo de la f a la cara a conseguir el valor más pequeño.)