Dos [n] [n] la función de las familias

Question

$\bf Note.$ Esta pregunta tenía una recompensa, así que al final he aceptado la mejor (y única) respuesta pero en realidad todavía está abierta. Es que (esperemos) equivalente a esta pregunta, si usted tiene alguna idea, por favor, publicarlo allí.

$\bf Question.$ Revisión n. Estamos interesados en la más grande de t para el cual existen dos familias de funciones, $P_i,Q_i$, de tamaño t de [n] [n] tal que para cualquier $i,j$ cada vez que se considere la secuencia infinita $P_i(Q_j(P_i(Q_j\ldots P_i(3))\ldots)$ (donde el número de iteraciones tiende a infinito), no contiene de 2 y una infinidad de 1 si $i=j$ y no contiene de 1 y una infinidad de 2 si $i\ne j$.

$\bf A lower bound.$ Yo sé de una construcción que muestra que $t\ge 2^{\frac n2-O(1)}.$ Para cada subconjunto $S$ de [n] que contiene exactamente un de $2k$ $2k+1$ $2\le k\le \frac n2-2$ construimos un par de funciones, $P_S,Q_S$ como sigue. Para cualquier número m denotar por $m^+$ el elemento más pequeño de $S$ que es más grande que el m o si todos los elementos de a $S$ son en la mayoría de m, entonces definimos ser 1. $P_S(1)=1, P_S(2)=2$ y para los más grandes $m$'s $P_S(m)=m^+$, mientras que $Q_S(1)=1, Q_S(2)=2$ y para los más grandes $m$'s $Q_S(m)=m$ si $m\in S$ $Q_S(m)=2$ si $m\notin S$. De esta manera podemos ir a través de todos los elementos de S y terminan en 1 si las funciones tienen el mismo índice, pero se nos empuja a 2 si se diferencian.

$\bf Upper bound.$ Por supuesto, es verdad que $t\le n^n$. Por lo que se puede hacer mejor que $2^n$?

Answer 1

Bueno, así que traté de ver cómo esto podría funcionar. Después de algunas reflexiones que he decidido que uno puede así tomar $P_i=Q_i$, por lo que la órbita de 3 (bajo la acción de $P_i$) es un ciclo que contiene 1. Si usted toma la longitud de este ciclo de aproximadamente el $n/2$, envíe $2\to 3$ y todo lo demás a 2, que no es una mala idea, excepto que no funciona para todos los posibles $n/2$-subconjuntos; de lo contrario, tendríamos aproximadamente el$\binom{n}{n/2}$$i$, tal y como quería, para empezar. Si ahora miramos en la órbita de 3 en $(P_iP_j)$ en este entorno bastante rápidamente a la conclusión de que no es inherente a un "teorema de la ciudad" (ver Babai-Frankl del libro) y por lo tanto $2^{n/2}$ es realmente la mejor posible. Por supuesto, en el pleno de la generalidad cosas raras que podría ser posible - no tengo la intuición de esto, pero esto no se ve bien y a menos que la diferencia es realmente importante para algunas aplicaciones no recomiendo trabajar en este problema.