Sobre el número de tipos de orden en mallas de tamaño polinomial

Resumen:

Sean $\{p_1,\dots,p_n\}$ y $\{q_1,\dots,q_n\}$ dos conjuntos etiquetados de $n$ puntos en posición general en el plano. Decimos que estos dos conjuntos tienen el mismo tipo de orden si para cada tripleta de índices $(i, j, k)$, $p_k$ está arriba de la línea dirigida de $p_i$ a $p_j$ si y sólo si $q_k$ está por arriba de la línea dirigida de $q_i$ a $q_j$. Denotemos el número de tipos de orden distintos por $f(n)$. Una pregunta natural es: ¿qué tan grande puede ser $f(n)$? Se sabe que:
    \[\exp(4(1+O(1/\log n))n \log n) \le f(n) \le \exp(4(1+O(1/\log n))n \log n).\]
Por otro lado, es útil conocer representantes de un tipo de orden dado con coordenadas enteras. Existen tipos de orden con $n$ puntos tales que toda realización con coordenadas enteras positivas tiene una coordenada de tamaño $2^{2^{c_{1}n}}$ y cualquier tipo de orden con $n$ puntos puede realizarse con coordenadas de tamaño a lo más $2^{2^{c_{2}n}}$, para ciertas constantes positivas $c_1$ y $c_2$.

En esta charla, hablaremos sobre las primeras cotas no triviales del número de tipos de orden distintos de $n$ puntos que se pueden realizar en mallas enteras de tamaño polinomial.

Compartir este seminario