¿Cuál es el tamaño mínimo de un orden parcial que es universal para todos los órdenes parciales de tamaño n?

Question

Una orden parcial $\mathbb{B}$ es universal para una clase $\cal{P}$ de órdenes parciales si cada orden en $\cal{P}$ incrustaciones orden-preservación en $\mathbb{B}$ .

Por ejemplo, cada orden parcial $\langle\mathbb{P},\lt\rangle$ mapea el orden-preservación en su poder establecido por el mapa $$p\mapsto\{q\in\mathbb{P}\mid q\leq p\}$$ que envía cada elemento $p$ a su cono inferior.

Por lo tanto, el orden del conjunto de la potencia $\langle P(\{1,2,\ldots,n\}),{\subseteq}\rangle$ es universal para la clase de órdenes parciales de tamaño $n$ . Esto proporciona un orden de tamaño $2^n$ que es universal para órdenes de tamaño $n$ .

Pregunta. ¿Cuál es el tamaño mínimo de un parcial que es universal para órdenes de tamaño $n$ ?

En concreto, ¿existe un límite superior polinómico?

Se pueden hacer al menos ligeras mejoras en el $2^n$ límite superior, al observar que el conjunto vacío no era necesario, ya que nunca surge como un cono inferior, y no necesitamos todo los átomos, ya que si se necesitan, se puede utilizar el coátomos en su lugar. Sospecho que hay un montón de residuos en el orden del conjunto de potencia, pero el mejor límite superior que conozco es sigue siendo exponencial.

Para un límite inferior, mis conocimientos actuales son débiles y están lejos de ser exponencial. Cualquier orden que sea universal para órdenes de tamaño $n$ contendrá una cadena y una anticadena, por lo que tenga un tamaño de al menos $2n-1$ . (Este límite es exacto para $n\leq 3$ .) Un alumno de mi curso de introducción a la lógica lo amplió a $n\log(n)$ considerando $k$ cadenas (y anticadenas) de tamaño $n/k$ .

¿Se pueden encontrar mejores límites inferiores?

Curiosamente, el mismo estudiante observó que no podemos in general esperar encontrar único órdenes universales más pequeñas, ya que encontró varios órdenes de tamaño 5 que son universales para órdenes de tamaño 3 y que son mínimos con esa propiedad. Así que, en general, no podemos esperar un único orden universal óptimo. ¿Se produce este fenómeno para cada $n$ ? (También encontró órdenes universales mínimos de tamaño mayor que el orden universal de tamaño mínimo).

Answer 1

Denota por $F(n)$ el número de órdenes parciales diferentes en el conjunto de cardinalidad $n$ . Entonces el tamaño mínimo $N$ de un orden parcial que es universal para órdenes de tamaño $n$ satisface $\binom{N}{n}\geq F(n)$ . Podemos limitar $F(n)$ de la siguiente manera (para simplificar, asumo que $n$ es par): toma $n/2$ elementos azules y $n/2$ elementos rojos, y luego decidir para cada par de elementos rojos y azules $r_i$ , $b_j$ , ya sea $r_i > b_j$ o no. Obtenemos $2^{n^2/4}$ órdenes parciales, y cada clase de isomorfismo se cuenta como máximo $n!$ veces. Así que, $N^n/n!> \binom{N}{n}\geqslant F(n)\geqslant 2^{n^2/4}/n!$ Por lo tanto $N>2^{n/4}$ .

Answer 2

En este trabajo demostramos https://arxiv.org/abs/2012.01764 que el respuesta es $2^{n/4+o(n)}$ . Como se observa en las otras respuestas, un conteo muestra que esto es óptimo (hasta el término de orden inferior).

Actualización: 7 de mayo de 2021. Lamentablemente hubo un fallo en nuestra prueba y tenemos que retirar esta respuesta. El resultado principal del artículo sigue siendo válido, pero no podemos obtener el poset universal como consecuencia directa de nuestro esquema de etiquetado de comparabilidad para los posets.

Lo siento mucho, siéntase libre de votar en contra de esta respuesta.

Answer 3

No existe un límite superior polinómico.

Dejemos que $P_n$ sea el número de órdenes parciales en $n$ elementos. Se sabe que $P_n \geq 2^{n^2/4}$ . Por lo tanto, cualquier método de representación única de los órdenes parciales en $n$ elementos, digamos en binario, requerirá al menos $\log_2(2^{n^2/4}) = O(n^2)$ bits.

Supongamos ahora que para cada $n$ hay un orden parcial en $n^k$ o menos, elementos, donde $k$ es una constante, que es universal para la clase de órdenes parciales sobre $n$ elementos. Fijar algún ordenamiento canónico de los órdenes parciales y dejar que $U(n)$ sean los primeros órdenes parciales universales sobre $n^k$ o menos elementos.

Etiquete cada uno de los elementos en $U(n)$ con un número único de $1$ hasta $\log_2(f(n)) = O(\log n)$ de alguna manera canónica fija. Ahora cada orden parcial sobre $n$ Los elementos pueden describirse de forma única escribiendo para cada elemento la etiqueta correspondiente en $U(n)$ . Esto requiere $O(n\log n)$ bits. Sin embargo, esta representación no es del todo completa, ya que parece requerir la descripción de $U(n)$ para reconstruir realmente un orden parcial dada su representación en esta forma.

Sin embargo, como $U(n)$ es el primer orden parcial universal en $n^k$ o menos elementos, en lugar de añadir una codificación de $U(n)$ a cada orden parcial directamente podemos añadir en su lugar una codificación de la siguiente máquina de Turing $M$ . $M$ recibe tres argumentos $n$ , $i$ y $j$ y acepta si el elemento $i$ es menor que el elemento $j$ en $U(n)$ y rechaza lo contrario. Dada una máquina de Turing así, podemos reconstruir claramente el orden parcial. $M$ simplemente enumera todos los órdenes parciales de tamaño entre $n$ y $n^k$ y se detiene en la primera orden parcial que es universal para todas las órdenes parciales en $n$ elementos. A continuación, etiqueta los elementos de $U(n)$ de manera canónica y acepta si el elemento etiquetado $i$ en $U(n)$ es menor que el elemento etiquetado $j$ en $U(n)$ . Esta TM tiene un tamaño constante.

Así, podemos representar de forma única y completa todos los órdenes parciales en $n$ elementos por $O(n\log n) + O(1) = O(n\log n)$ bits, lo cual es una contradicción ya que hay demasiados pedidos parciales en $n$ elementos para ser representados en sólo $O(n\log n)$ bits.