Una curiosa asimetría en buenas caracterizaciones.

8

Existen bastantes teoremas, principalmente en teoría de grafos y optimización combinatoria, que a menudo se denominan buenas caracterizaciones. Por lo general, colocan una propiedad en , al mostrar que una propiedad se mantiene o hay algún obstáculo bien identificado que impide que se mantenga. A menudo se presentan como teoremas min-max, vea la pregunta anterior Problemas de optimización con buena caracterización, pero sin algoritmo de tiempo polinómicoNPcoNP

Aquí hay dos ejemplos clásicos de buenas caracterizaciones:

  1. Un gráfico bipartito tiene una coincidencia de tamaño , o bien hay menos de vértices que cubren todos los bordes. La existencia de tal cubierta es un obstáculo trivial que excluye la correspondencia. Si este obstáculo no está allí, la coincidencia debe existir, esta es la parte no trivial, conocida como el Teorema de Konig.kkk

  2. O bien hay una flujo de valor en un gráfico de flujo, o de lo contrario hay un corte con capacidad inferior a . Una vez más, la existencia de tal corte es un obstáculo trivial, ya que el flujo no puede pasar. La parte no trivial es que la ausencia del obstáculo ya garantiza la existencia del flujo de valor , que es equivalente al Teorema de corte mínimo de flujo máximo.F s - t F FstFstFF

Lo que encuentro una característica curiosa en estos (y muchos otros) resultados es que muestran una asimetría bien visible en la dureza de prueba entre las dos direcciones de la equivalencia. Por lo general, es fácil, o incluso trivial, demostrar que el obstáculo excluye la propiedad considerada. Por otro lado, es mucho más difícil demostrar que el obstáculo fácil / trivial es el único obstáculo, en el sentido de que una vez que no está allí, la propiedad debe mantenerse.

No conozco una buena explicación de por qué este tipo de asimetría es tan común. No parece a priori necesario. Nota: no se deje engañar por el hecho de que los ejemplos anteriores son casos especiales de dualidad de programación lineal. Hay otros ejemplos que no tienen nada que ver con la programación lineal.

Pregunta: ¿Conoces alguna buena caracterización que no se encuentre en esta categoría? (Es cierto que está vagamente definido, pero tal vez la idea se hizo realidad). En otras palabras, estoy buscando un teorema que ponga una propiedad en , al capturar todos los posibles obstáculos de la propiedad, pero son No todos los obstáculos fáciles / triviales.NPcoNP

Andras Farago
fuente
44
¿Me gustaría ver estos ejemplos que no son casos especiales de dualidad? Porque con sus ejemplos, las direcciones fáciles son la dualidad débil, que siempre es trivial de probar, y las direcciones difíciles son la dualidad fuerte, lo cual es un hecho más profundo.
Sasho Nikolov
¿Cuál sería un ejemplo de un obstáculo "no trivial"?
András Salamon
Aquí hay un ejemplo de un obstáculo no trivial para una propiedad: un gráfico no puede tener un número cromático si no contiene un subgrafo -construible, vea la construcción de Hajos [ en.wikipedia.org/wiki/Hajós_construction] . Aunque el número cromático no está en (a menos que ), todavía muestra un ejemplo de lo que podría ser un obstáculo no trivial. También publicaré ejemplos que no son casos especiales de dualidad LP, pero no caben en un comentario. k N P c o - N P N P = c o - N PkkNPcoNPNP=coNP
Andras Farago
44
Creo que esto bien podría ser una consecuencia de las pruebas realizadas por personas. Encontramos una (fácil) desigualdad o implicación, y preguntamos si la otra dirección (o desigualdad) también es verdadera. Por lo que sabemos, podría haber muchas implicaciones que son difíciles en ambos sentidos, pero simplemente no podemos encontrarlas :)
daniello

Respuestas:

5

(Esto es para responder el comentario de Sasho Nikolov, pero es demasiado largo para el campo de comentarios, así que lo publico como respuesta).

Los dos ejemplos en la pregunta original son casos especiales de dualidad LP. Hay muchos ejemplos similares, pero uno puede argumentar que todos heredan la asimetría de la dualidad LP. La dualidad débil de LP es fácil de probar (proporciona el "obstáculo trivial"), mientras que la dualidad fuerte es más profunda, lo que demuestra que el obstáculo trivial es el único obstáculo. En este sentido, se puede ver que los ejemplos que son "hijos de LP" son solo encarnaciones diferentes del mismo ejemplo central.

Aquí hay, sin embargo, algunos otros casos que (que yo sepa) no están relacionados con LP. Los ejemplos a continuación son todos de la teoría de grafos, pero otros campos probablemente también contienen patrones similares.

  1. Deje ser enteros positivos. Luego hay un gráfico simple con conectividad de vértice , conectividad de borde y grado mínimo , si y solo sik,l,dkldkld. Como es (casi) trivial demostrar que estos parámetros siempre satisfacen las desigualdades, la violación de al menos una desigualdad es un obstáculo trivial para que exista dicho gráfico. La otra dirección, que tal gráfico siempre existe es no trivial. (Ver el libro de Bollobas "Extremal Graph Theory," Theorem 1.5. Nota: la forma en que se presenta allí es algo más complicada, usando más desigualdades, porque también usa otro parámetro, el número de vértices. Pero esta versión más simple puede ser extraído de él, para mostrar la naturaleza esencial de que aquí nuevamente el obstáculo trivial es el único obstáculo).

  2. Dado un gráfico simple no dirigido, ¿tiene dos circuitos vértices disjuntos? Esto se responde con el siguiente teorema de Lovasz y Dirac: si un gráfico simple con un grado mínimo no tiene dos circuitos de vértice disjunto, entonces el gráfico solo puede ser uno de los siguientes tres tipos: (1) , ( 2) un gráfico de rueda, (3) , con posiblemente cualquier borde agregado a la clase de 3 vértices. Aquí el obstáculo trivial es que el gráfico cae en uno de estos tipos, ya que se ve fácilmente que estos tipos no contienen 2 circuitos separados de vértices. Si el obstáculo trivial está ausente, el gráfico siempre tiene la propiedad (pero es bastante no trivial probarlo).3K5K3,n3

  3. Dada una secuencia de enteros, y un entero , ¿existe un gráfico simple conectado que tenga como secuencia de grados? Un resultado de Edmonds de 1964 responde a la pregunta: tal gráfico existe si y solo si se cumplen dos condiciones: (a) la secuencia es gráfica (es decir, hay un gráfico que lo implementa como una secuencia de grados, lo cual es trivialmente necesario, y puede verificarse mediante el Teorema de Erdos-Gallai), y (b) , que también es trivialmente necesario, ya que la conectividad de borde está limitada desde arriba por el grado mínimo. Una vez que se cumplen estas condiciones necesarias esencialmente triviales, siempre existe el gráfico deseado.d1dnk2kd1dndnk

  4. Dado un gráfico completo y un gráfico fijo , ¿pueden dividirse los bordes de en copias disjuntas de ? Un teorema de Wilson de 1976 demuestra que si es lo suficientemente grande, entonces el único obstáculo para que exista tal partición es la violación de una de las siguientes condiciones de divisibilidad trivialmente necesarias: (a)es un divisor de, (b) si es el máximo común divisor de los grados de , entonces es un divisor de .H G H G | E ( H ) | El | E ( G ) | g H g | V ( G ) | - 1GHGHG|E(H)||E(G)|gHg|V(G)|1

Andras Farago
fuente