Pigeonhole pregunta principal 1

Question

Deje $m = n^3 + 1$ y deje $\sigma_1, \sigma_2, \sigma_3$ 3 permutaciones de $\{{1,2,...m}\}$. Demostrar que dos de estas permutaciones tienen el mismo subsequence que se $n+1$ largo.

He tratado de usar el Erdos-Szekeres teorema (cada permutación de $n^3+1$ ha monótonamente creciente larga en $n^2+1$ largo o monótonamente decreciente larga en $n+1$) pero yo no tenía ni idea de proceder.

Cualquier ayuda será apreciada.

Answer 1

Creo que quiere imitar a la prueba de la Erdos-Szekeres teorema, no se aplican directamente. La etiqueta de cada una de las $1\le j\le m$ con el triple de $(a,b,c)$ donde $a$ es la longitud de los más comunes larga de $\sigma_1$ e $\sigma_2$ que termina en $j,$ $b$ es la más común subsequence de $\sigma_1$ e $\sigma_3$ que termina en $j,$ y $c$ es la más común subsequence de $\sigma_2$ e $\sigma_3$ que termina en $j.$

Me reclama que no hay dos elementos de obtener la misma etiqueta, por supongamos $1\le j,k \le m,$ con $j\ne k$ , y que tanto $j$ e $k$ obtener la misma etiqueta. Si $j$ precede $k$ tanto $\sigma_1$ e $\sigma_2$ entonces $k$ tiene un mayor $a-$etiqueta de $j$, ya que se puede anexar $k$ a la mayor comunes larga que termina en $j$. Del mismo modo, $k$ no puede preceder a $j$ tanto $\sigma_1$ e $\sigma_2$ por lo que podemos asumir $j$ precede $k$ en $\sigma_1$ e $k$ precede $j$ en $\sigma_2$. A continuación, $j$ e $k$ debe venir en el mismo orden en $\sigma_3$ como $\sigma_1$ o $\sigma_2$ , de modo que tienen diferentes $b-$etiquetas diferentes o $c-$etiquetas.

Si el más largo de los comunes larga es de longitud $n$ o menos, entonces hay en la mayoría de las $n^3$ etiquetas diferentes, pero tenemos $n^3+1$ etiquetas diferentes, contradicción.

EDITAR Se me acaba de ocurrir que hay muchas pruebas de la Erdos-Szekeres teorema conocido. Me estoy refiriendo a la de aquí

Answer 2

Mi argumento se basa en una comprensión de posets y Mirsky del teorema, el cual puede ser usado para demostrar Erdos-Szekeres. Estoy que no sé cómo demostrarlo con Erdos-Szekeres, si eso es lo que quieres. También, me doy cuenta de que es muy largo. El primer párrafo explica poset ideas y cómo se aplican a estos posets.

Definimos posets $P_{1,2}, P_{1,3}, P_{2,3}$ en nuestra serie $\{1,2,\ldots,m\}$ donde $i<j$ en $P_{1,2}$ si $i$ aparece antes de $j$ tanto $\sigma_1$ e $\sigma_2$, y definimos el orden en las otras dos posets del mismo modo. En el fin de la teoría, una cadena es un conjunto de elementos de la $\{x_1,x_2,\ldots, x_i\}$ satisfacción $x_1<x_2<\ldots x_i$, y un antichain es un conjunto $A$ donde tenemos ni $a<b$ ni $b<a$ para $a,b\in A$. En este idioma, queremos mostrar que uno de estos posets contiene una cadena de tamaño, al menos, $n+1$. Dos elementos $x$ e $y$ en $P_{1,2}$ son incomparables (significado ni es mayor que la otra) si $x$ aparece antes de $y$ en $\sigma_1$ e $y$ aparece antes de $x$ en $\sigma_2$, o viceversa. Por lo tanto, si $A=\{x_1,x_2,\ldots,x_n\}$ es un antichain en $P_{1,2}$, e $\sigma_1$ contiene $x_1x_2\ldots x_n$ como una larga, a continuación, $\sigma_2$ contiene $x_nx_{n-1}\ldots x_1$ como larga. En otras palabras, si $A$ es un antichain en $P_{1,2}$, a continuación, $\sigma_1$ e $\sigma_2$ contienen $A$ en pedidos de enfrente.

Mirsky del teorema establece que para un finito poset, el tamaño de la más larga de la cadena es igual al tamaño de la más pequeña antichain descomposición, o una partición de nuestro conjunto en los bloques donde no hay dos elementos en el mismo bloque son comparables por nuestro ordenamiento. En primer lugar, mirar a $P_{1,2}$: si tenemos una cadena de tamaño, al menos, $n+1$, hemos terminado. De lo contrario, nuestro mayor cadena de tamaño en la mayoría de las $n$, así que por Mirsky del teorema, nuestro pequeño antichain descomposición en la mayoría de las $n$ antichains. Por el principio del palomar, uno de los $n$ antichains debe contener, al menos, $n^2+1$ elementos. Vamos a llamar a este antichain $A=\{x_1,x_2,\ldots, x_{n^2+1}\}$. Sin pérdida de generalidad, dicen que aparecerán en el orden en $\sigma_1$, y por lo tanto en el orden opuesto en $\sigma_2$.

Ahora nos fijamos en $P_{1,3}$ restringido a $A$. Si tenemos una cadena de tamaño, al menos, $n+1$, hemos terminado. De lo contrario, el más largo de la cadena de tamaño en la mayoría de las $n$, y nuestro pequeño antichain descomposición en la mayoría de las $n$ antichains. Desde $|A|\geq n^2+1$, el principio del palomar nos dice que debemos tener una antichain en $A$ con al menos $n+1$ elementos. Llamar a este antichain $A'$, que es un subconjunto de a$A$. Decir $A'=\{x'_1,x'_2,\ldots, x'_{n+1}\}$, donde $x'_1,x'_2,\ldots,x'_{n+1}$ es una larga de $x_1,x_2,\ldots,x_{n^2+1}$. Por lo tanto, donde los elementos de $A'$ aparecen en el orden dado en $\sigma_1$, deben aparecer en el orden opuesto en $\sigma_3$. Pero ya hemos dicho que los elementos de la $A$, que incluyen la $A'$, aparecen en $\sigma_2$ también en el frente de $\sigma_1$'s para, a continuación, $A'$ aparece en el mismo orden en $\sigma_2$ como $\sigma_3$, por lo que tienen en común un larga de tamaño $n+1$.