Subsecuencias de permutación

Question

Dadas tres permutaciones $p_1,p_2,p_3$ de $\{1,2,\ldots,n^3+1\}$ demuestre que dos de ellas tienen una subsecuencia común de longitud $n+1$ .

He tratado de resolver esto usando el principio de pigenhole pero no he progresado demasiado, cualquier ayuda sería apreciada

edit: cuando digo subsecuencia me refiero a que hay $1<=r<q<=3$ y $1<=i(1)<i(2)<...<i(n+1)<=n^3+1$ y $1<=j(1)<j(2)<...<j(n+1)<=n^3+1$ para que $p_r(i1)=p_q(j1)$ , $p_r(i2)=p_q(j2)$ y así sucesivamente, no necesariamente consecutivos

Answer 1

Esto se puede demostrar con ideas que se utilizan para demostrar el teorema de Erdos-Szekeres. Sin pérdida de generalidad, podemos suponer $p_1$ es la permutación de identidad (en caso contrario, sólo hay que reetiquetar los números). Entonces, si cualquiera de $p_2$ o $p_3$ tiene una subsecuencia creciente de longitud $n + 1$ hemos terminado. Así que supongamos que sus subsecuencias crecientes más largas son ambas como máximo $n$ .

Para cada $k \in \{1, 2, \ldots , n^3 + 1\}$ , defina $f_i(k)$ para ser la longitud de la subsecuencia creciente más larga de $p_i$ cuyo último término es $k$ . Nuestra suposición dice que $1 \le f_i(k) \le n$ .

Tenga en cuenta que sólo hay $n^2$ valores posibles para el par $(f_2(k), f_3(k))$ . Así, por el principio de encasillamiento, debe existir $n + 1$ enteros

$$k_1 > k_2 > \cdots > k_{n + 1}$$

tal que $(f_2(k_i), f_3(k_i)) = (f_2(k_j), f_3(k_j))$ para todos $i$ y $j$ .

Ahora afirmamos que $(k_1, k_2, \ldots , k_{n + 1})$ es una sucesión de ambos $p_2$ y $p_3$ . De hecho, supongamos que para algunos $i$ , $k_i$ aparece después de $k_{i + 1}$ en la permutación $p_2$ . Entonces, cualquier subsecuencia creciente que termine en $k_{i + 1}$ puede ampliarse uno más añadiendo $k_i$ , lo que contradice la igualdad $f_2(k_i) = f_2(k_{i + 1})$ . El mismo argumento se aplica a $p_3$ por lo que hemos obtenido nuestra subsecuencia común de longitud $n + 1$ .

Answer 2

Eso no es cierto. Considere tres permutaciones : $$p_1 = (1, \dots, n^3+ 1)$$ $$p_2 = (n^3+1, \dots, 1)$$ $$p_3 = (1, n^3, 3, n^3-2, \dots)$$ donde $p_3[i] = p_{i \bmod 2}[i]$

Answer 3

No creo que esa afirmación sea cierta.

No estoy seguro de qué crees que es una permutación de un conjunto, así que vamos a suponer que hablamos de secuencias. Tomemos $n=2$ Así que $n^3+1 = 9$ , por lo que nuestra secuencia es $l=(1,2,3,4,5,6,7,8,9)$ . Ahora tengo estas tres permutaciones:

• $p_1(l) = (1,2,3,4,5,6,7,8,9) = l$
• $p_2(l) = (9,8,7,6,5,4,3,2,1)$
• $p_3(l) = (1,3,5,7,9,2,4,6,8)$

Claramente, ninguno de ellos tiene una subsecuencia común de longitud $n+1=3$ (o incluso de longitud $2$ ).