Una versión combinatoria para la conjetura polinómica de Hirsch

Considere familias disjuntas de subconjuntos de {1,2, ..., n}, .$t$${\cal F}_1,{\cal F_2},\dots {\cal F_t}$

Suponer que

(*)

Para cada y cada , y , hay que contiene .$i \lt j \lt k$$R \in {\cal F}_i$$T \in {\cal F}_k$$S \in {\cal F}_j$$R \cap T$

La pregunta básica es:

¿Qué tan grande no puede ser?

Lo que se sabe

El límite superior más conocido es cuasi polinomial .$t \le n^{\log n+1}$

El límite inferior más conocido es (hasta un factor logarítmico) cuadrático.

Esta configuración abstracta está tomada del artículo Diameter of Polyhedra: The Limits of Abstraction de Friedrich Eisenbrand, Nicolai Hähnle, Sasha Razborov y Thomas Rothvoss . El límite inferior cuadrático, así como una prueba del límite superior, se pueden encontrar en su artículo.

Motivación

Cada límite superior se aplicará al diámetro de los gráficos de politopos d-dimensionales con n facetas. Para ver esto, asocia a cada vértice el conjunto de las facetas que lo contienen. Luego, a partir de un vértice deje que sean los conjuntos correspondientes a los vértices del politopo de distancia desde .$v$$S_v$$w$${\cal F}_r$$r+1$$w$

Más

Este problema es el tema de polymath3 . Pero pensé que podría ser útil presentarlo aquí y en MO a pesar de ser un problema abierto. Si el proyecto conducirá a subproblemas específicos, yo (u otros) podría intentar preguntarles también.

(Actualización; 5 de octubre :) Un problema específico que es de especial interés es restringir la atención a conjuntos de tamaño d. Sea f (d, n) el valor máximo de t cuando todos los conjuntos de todas las familias tengan el tamaño d. Sea f * (d, n) el valor máximo de t cuando permitimos multisets de tamaño d. Comprender f * (3, n) puede ser crucial.

Problema: ¿f * (3, n) se comporta como 3n o como 4n?

Los límites inferior y superior conocidos son 3n-2 y 4n-1 respectivamente. y dado que el 3 es el comienzo de la secuencia 'd', mientras que el 4 es el comienzo de la secuencia decidir si la verdad es 3 o 4 no puede ser importante. Ver el segundo hilo .$2^{d-1}$

Un amigo mío y yo hemos decidido probar el método de fuerza bruta y calcular algunos valores de para valores pequeños de y . Esto es totalmente imposible sin emplear la poda, y esperamos que los trucos que hemos encontrado nos den una idea del resto del problema. Hasta ahora, no hemos logrado reducir significativamente el tiempo de ejecución doblemente exponencial del método de fuerza bruta (aproximadamente es nuestro mejor límite hasta el momento) y, por lo tanto, todavía no hemos alcanzado nuestro objetivo original de alguna manera prediciendo la función detrás de$t$$n$$d$$3^{2^n}$$f$desde sus primeros valores. Tampoco hemos estudiado todos los comentarios de los subprocesos anteriores en detalle, por lo que algo de esto ya puede ser conocido: básicamente nos divertimos haciendo que nuestro código sea rápido y quería publicar nuestros resultados en algún lugar, si tuviera un entorno LaTeX que funcionara pon esto en el ArXiV.

Código (no es exactamente el código de producción ...): http://pastebin.com/bSetW8JS . Valores:

f(d=2, n)=2n-1 for n <= 6

f(d=3, n=3) = 6
{} {0} {01} {012} {12} {2}

f(d=4, n=4) = 8
f(d=3, n=4) = 8
{} {0} {01} {1,02,03} {2,13} {123} {23} {3}
{} {0} {01} {2,013} {1,02,03} {023} {23} {3}

f(d=5, n=5) = 11
f(d=4, n=5) = 11
f(d=3, n=5) = 11
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {012,3} {02,12,013,014} {13,023,04,124} {123,024} {23,24} {234} {34} {4}
{} {0} {01} {012,13} {02,12,013} {03,123,014,024} {023,124} {23,24} {234} {34} {4}

Decimos que la secuencia es convexa si (*) se mantiene. Nuestro enfoque construye secuencias convexas agregando familias a secuencias convexas más cortas, esencialmente usando eso si es convexo, entonces es convexo. Notamos que es convexo si y solo si para todo tenemos que es convexo. Decimos que es compatible con si${\cal F}_1, ..., {\cal F}_t$${\cal F}_1, ..., {\cal F}_t$${\cal F}_1, ..., {\cal F}_{t-1}$${\cal F}_1, ..., {\cal F}_t$$A \in {\cal F}_t$${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$$A$${\cal F}_1, ..., {\cal F}_{t-1}$${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$es convexo: ahorramos tiempo de cálculo al calcular los conjuntos que son compatibles con una secuencia y luego tomar los elementos de su conjunto de potencia como el nuevo , en lugar de determinar si es convexo directamente.${\cal F}_t$${\cal F}_1, ..., {\cal F}_t$

Nuestra próxima aceleración es esencialmente una programación dinámica. Intentamos encontrar una relación de equivalencia en secuencias convexas con las siguientes dos propiedades. Primero, si para dos secuencias convexas, entonces es compatible con si y solo si es compatible con . Segundo, si y es convexo, entonces$\sim$${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$$A$${\cal F}_1, ..., {\cal F}_t$${\cal F}'_1, ..., {\cal F}'_t$${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1} \sim {\cal F}'_1, ..., {\cal F}'_t, {\cal F}_{t+1}$. Además, nos gustaría poder determinar si un conjunto es compatible con elementos de una clase de equivalencia y determinar un representante de la clase de equivalencia de dado y un representante de la clase de equivalencia de . El algoritmo de programación dinámica resultante es entonces obvio. El número de clases de equivalencia (junto con el tiempo empleado por las dos operaciones anteriores) proporciona un límite en el tiempo de ejecución del algoritmo de programación dinámica obvio.${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$${\cal F}_{t+1}$${\cal F}_1, ..., {\cal F}_t$

Para la equivalencia que usamos para obtener nuestro límite, usamos una caracterización de convexidad que se basa en 'intervalos' de la siguiente manera. Dado un subconjunto de , decimos que es contiguo con respecto a una secuencia (no necesariamente convexa) si para algunos enteros . Decimos que es el intervalo para wrt esta secuencia. Se ve fácilmente que es convexo si y solo si todos los subconjuntos de$A$$\{ 1, \dots, n \}$$A$${\cal F}_1, ..., {\cal F}_t$$\{ k \mid \exists B \in {\cal F}_k : A \subseteq B \} = \{ i, \dots, j \}$$1 \leq i \leq j \leq n$$(i, j)$$A$${\cal F}_1, ..., {\cal F}_t$$\{ 1, \dots, n \}$ son contiguos con respecto a la secuencia.

Ahora, dada una secuencia convexa , marcamos todos los subconjuntos de como no tocados , no permitidos o activos de la siguiente manera: todos los elementos de están activos, todos los elementos de están prohibidos y todos los superconjuntos de los conjuntos cuyo intervalo con respecto a es con también están prohibidos. Es inmediato que un conjunto${\cal F}_1, ..., {\cal F}_t$$\{ 1, \dots, n \}$${\cal F}_t$${\cal F}_1, ..., {\cal F}_{t-1}$$B$$A$${\cal F}_1, ..., {\cal F}_{t-1}$$(i, j)$$j < t - 1$$A$es compatible con la secuencia si y solo si está marcado como no tocado. Definimos dos secuencias como equivalentes bajo si su marcado es igual. Se ve fácilmente que esta relación de equivalencia satisface nuestras dos propiedades. Para calcular si un conjunto debe ser rechazado por la condición de intervalo, podemos usar la condición equivalente 'existe un conjunto tal que para ningún conjunto , '. es un límite inmediato en el número de clases de equivalencia.$\sim$$B$$C \in {\cal F}_t$$D \in {\cal F}_{t+1}$$B \cap C \subseteq D$$3^{2^n}$

También utilizamos varias podas adicionales. Solo consideramos antichains para y requerimos que los elementos de sus elementos provengan de . Por último, utilizamos la optimización que para secuencias óptimamente largas (y similares para y ). Imaginamos que investigar el comportamiento de puede generar ahorros más drásticos.${\cal F}_{t+1}$${1, \dots, i}$${\cal F}_1 = \{ \{ 1 \} \}, {\cal F}_2 = \{ \{ 1, 2 \} \}$${\cal F}_{t-1}$${\cal F}_t$${\cal F}_3$