Subconjuntos de pequeña dimensión Dushnik-Miller

Question

Dushnik-Miller dimensión de un orden parcial $(P,{\leq})$ es el tamaño más pequeño posible $d$ para una familia ${\leq_1},\ldots,{\leq_d}$ de pedidos totales de $P$ cuya intersección es ${\leq}$ es decir $x \leq y$ si $x \leq_i y$ se cumple simultáneamente para todos $i = 1,\ldots,d$ . Equivalentemente, la dimensión es la menor $d$ tal que $P$ incrusta en $L^d$ de alguna ordenación total $L$ donde $L^d$ está dotado de la ordenación parcial por coordenadas.

Puesto que las cadenas tienen dimensión 1 y las anticadenas dimensión 2, Teorema de Dilworth garantiza que todo poset de tamaño $n$ contiene un $2$ sub-conjunto dimensional de tamaño al menos $\sqrt{n}$ . ¿Es esto óptimo? En general, ¿qué podemos decir de los subconjuntos de dimensión $d$ ?

---

El argumento de Tom Goodwillie más abajo muestra que para un tamaño suficientemente grande $n$ todo poset de tamaño $n$ o bien tiene una anticadena de tamaño $\sqrt{dn}$ o un $d$ -de tamaño $\sqrt{dn}$ . Este resultado es óptimo para $d = 1$ Entendido así, también podría ser óptimo para $d > 1$ también. Para $d = 2$ esto mejora mi límite inferior $\sqrt{n}$ anterior por un factor de $\sqrt{2}$ .

En vista de ello, permítanme reformular la pregunta de la siguiente manera. Sea $F_d(n)$ es el mayor número entero tal que todo poset de tamaño $n$ tiene un $d$ -de tamaño $F_d(n)$ . Tenga en cuenta que $F_1(n) = 1$ para todos $n$ y, cuando $d > 1$ , $F_d(n) \geq \sqrt{dn}$ para un tamaño suficientemente grande $n$ .

Es $F_2(n) \leq C\sqrt{n}$ para alguna constante $C$ ? En general, ¿cuál es el comportamiento asintótico de $F_d(n)$ ?

Answer 1

He aquí una ligera mejora: observando que un poset tiene dimensión $\le 2$ si se puede dividir en dos cadenas, se puede mejorar $\sqrt n$ a $\sqrt {2n}$ para $n>1$ . (Sea la anchura $w$ . Si $w\ge \sqrt {2n}$ entonces existe una anticadena de tamaño $w\ge \sqrt {2n}$ . En caso contrario, existe una partición en $w$ cadenas de tamaño medio $\frac{n}{w}\ge\sqrt{\frac {n} {2} }$ de modo que la unión de las dos mayores de estas cadenas tiene tamaño $\ge\sqrt {2n}$ .)

Answer 2

Elyse Yeager y yo hemos construido ejemplos para un límite superior. Básicamente, si entiendes la dimensión de los subconjuntos de $P$ entonces se entiende la dimensión de los subconjuntos de la potencia lexicográfica $P^k$ . Comenzando con un ejemplo estándar apropiado se obtiene un límite superior sublineal de $F_d(n)$ este límite depende de $d$ y, en particular, tenemos $F_2(n)\leq n^{0.8295}$ .

Nuestra nota está en el arXiv: http://arxiv.org/abs/1404.0021

Answer 3

En este caso, creo que es mejor pensar en la dimensión en términos del hipergrafo de pares incomparables. Para posets de dimensión 2, un poset tiene dimensión 2 si y sólo si el grafo de pares incomparables es bipartito. (véase http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.339 para una prueba)

Por lo tanto, querrás construir posets cuyo grafo de pares incomparables no tenga grandes subgrafos bipartitos inducidos (ya que un subposet corresponderá a un subgrafo inducido del grafo de pares incomparables). Podríamos fijarnos en las construcciones de grafos sin grandes conjuntos independientes (por ejemplo, los aleatorios), ya que éstos no tendrán grandes subgrafos bipartitos.

Para k más grandes, se puede reformular el problema como un problema extremo de coloreado de hipergrafos y probablemente existan algunos resultados de coloreado de hipergrafos?

Answer 4

Junto con Grzegorz Guśpiel y Piotr Micek, hemos llegado a otra construcción de límite superior. Nuestro ejemplo es simplemente un $n^{d+1}$ cuadrícula con orden natural de los productos. Obviamente tiene un $d$ -de tamaño $n^d$ y demostramos que es asintóticamente el mayor subconjunto. Esto da $F_2(n) = O(n^{2/3})$ y, en general $F_d(n) = O(n^\frac{d}{d+1})$ que mejora el límite superior de Ben Reiniger y Elyse Yeager para $d \leq 7$ .

Nuestra demostración utiliza una versión multidimensional del teorema de Marcus-Tardos, y para $d=2$ también ofrecemos un ejemplo ligeramente distinto, que puede analizarse con las manos desnudas.

Puede encontrar los detalles en arXiv: https://arxiv.org/abs/1705.00176