How would you design a picture to illustrate the unique games conjecture?

This is for a "Current Events" presentation on unique games at the next AMS Joint Meeting and for the booklet that will be produced.

Example of the kind of illustrations produced in the past are at


and if you click on the 2006 edition you can see the picture that Madhu Sudan used to illustrate his talk on PCP.

I have thought about using the gadget reducing unique games to max cut, or the Khot-Vishnoi graph for reasonably small size. A good suggestion I received was to draw the label-extended graph of a nearly-satisfiable instance of unique games, and highlight in a different color the vertices corresponding to an optimal solution.

Other suggestions?

  • $\begingroup$ Dana Moshkovitz had a few slides at the Barriers II rump session. I don't know if they'd have what you need, but you might ask her if you could see them. $\endgroup$ Sep 13 '10 at 13:11

If I were going to illustrate unique games, I'd do something with a label-extended graph (similar to the suggestion you mentioned).

But specifically, I'd contrast the original constraint graph with the label-extended one. For instance, label edges in the constraint graph with the corresponding equation out of:

$x_1 - x_2 = 0\mod 3$

$x_2 - x_3 = 0\mod 3$

$x_3 - x_1 = 1\mod 3$

Then there will be a (hopefully visually appealing) "twist" between the $x_1$ and $x_3$ vertex clouds in the label-extended graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.