Seguí el enlace en la pregunta, y la reducción allí en realidad produce gráficos cuyos bordes tienen una coloración natural de modo que cada Knorte presente en el gráfico es un "arco iris Knorte " (tiene exactamente un borde de cada color). En otras palabras, podemos ajustar fácilmente la reducción en la que el papel de manera que se reduce a su problema en lugar de reducir a la partición en Knorte problema s: simplemente asignar a cada borde un color de acuerdo con este colorante natural y entonces la gráfica se puede dividir en "arco iris Knorte s" si y solo si podría dividirse en Knorte s.
La estructura básica de la reducción en ese papel se puede lograr con los siguientes 3 pasos:
- Crear muchas copias de un gráfico particular Hn , p .
- Identifique ciertas piezas de algunas copias de Hn , p entre sí (es decir, combine vértices / bordes entre múltiples copias diferentes de Hn , p ).
- Eliminar ciertos vértices / bordes de algunas copias.
El gráfico Hn , p tiene como vértices el conjunto de vectores de longitud norte módulo pags para el cual los componentes se suman a 0 0 mod pags . Los bordes conectan cada dos vértices que difieren en solo dos componentes con diferencias de + 1 y - 1 en esos dos componentes.
Propongo el siguiente color para este gráfico: asigne un color a cada borde de acuerdo con su dirección. Si X e y son vértices adyacentes, entonces x - y es un vector con n - 2 componentes iguales a 0 0 , un componente igual a 1 y un componente igual a - 1 . En otras palabras, para cada borde ( x , y) hay opciones para qué componentes de( n2)x - yson distintos de cero Si asignamos un color único a cada una de estas opciones, entonces tenemos un color para todos los bordes, de modo que cada borde en la misma dirección tenga el mismo color. Es bastante fácil verificar que no haya dos aristas en una en en la misma dirección. Por lo tanto, cada en es un arcoíris bajo este color.KnorteHn , pKnorteHn , pKnorte
Cuando seguimos la reducción, usamos este color para cada copia de . Por lo tanto, al final del paso 1 en la lista anterior, cada en el gráfico es un arco iris .Hn , pKnorteKnorte
En el paso 2 de la lista anterior, identificamos algunos vértices / aristas entre sí. En particular, en la reducción siempre identificamos una con otra . Pero en esta situación (donde todos los s son de una copia de ), cada es una traducción del " estándar " que el documento llama o una traducción de . Por lo tanto, estamos identificando dos s paralelas o dos s que son "volteretas" entre sí. En cualquier caso, los bordes que se identifican a través de los dosKnorteKnorteKnorteHn , pKnorteKnorteK- KKnorteKnorteKnorteK n K n K ns son paralelas y, por lo tanto, son del mismo color. Por ejemplo, vea la Figura 2 en el documento; Las aristas identificadas son siempre paralelas. Por lo tanto, dado que nunca intentamos identificar dos bordes de diferentes colores, la coloración al final del paso 1 en la lista anterior se puede extender naturalmente a una coloración al final del paso 2. Identificar ciertos vértices / bordes juntos no crea cualquier s nuevo , por lo que sigue siendo el caso al final de este paso que cada es un arcoíris .KnorteKnorteKnorte
Finalmente, en el paso 3 eliminamos algunos vértices / bordes, que tampoco crean nuevos s. Por lo tanto, tenemos nuestra propiedad deseada: bajo el color que proporcioné, cada en el gráfico generado por esta reducción es un arco iris .KnorteKnKn