Visualizando juegos únicos

19

¿Cómo diseñarías una imagen para ilustrar la conjetura de los juegos únicos?

Esto es para una presentación de "Eventos actuales" sobre juegos únicos en la próxima reunión conjunta de AMS y para el folleto que se producirá.

Ejemplos del tipo de ilustraciones producidas en el pasado están en

http://www.ams.org/meetings/lectures/current-events-bulletin

y si hace clic en la edición de 2006, puede ver la imagen que Madhu Sudán usó para ilustrar su charla en PCP.

He pensado en usar el gadget para reducir los juegos únicos al corte máximo, o el gráfico Khot-Vishnoi para un tamaño razonablemente pequeño. Una buena sugerencia que recibí fue dibujar el gráfico con etiqueta extendida de una instancia casi satisfactoria de juegos únicos, y resaltar en un color diferente los vértices correspondientes a una solución óptima.

¿Otras sugerencias?

Luca Trevisan
fuente
Dana Moshkovitz tuvo algunas diapositivas en la sesión grupal Barriers II. No sé si tendrían lo que necesitas, pero podrías preguntarle si puedes verlos.
Aaron Sterling

Respuestas:

4

Si fuera a ilustrar juegos únicos, haría algo con un gráfico con etiqueta extendida (similar a la sugerencia que mencionó).

Pero específicamente, contrastaría el gráfico de restricción original con el de etiqueta extendida. Por ejemplo, etiquete los bordes en el gráfico de restricción con la ecuación correspondiente de:

x1x2=0mod3

x2x3=0mod3

x3x1=1mod3

x1x3

Daniel Apon
fuente