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

<p>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:</p>

<p>$x_1 - x_2 = 0\mod 3$</p>

<p>$x_2 - x_3 = 0\mod 3$</p>

<p>$x_3 - x_1 = 1\mod 3$</p>

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

CC BY-SA 2.5
2010-09-13T09:52:56.500Z
2010-09-13T09:52:56.500Z
Daniel Apon
<p>How would you design a picture to illustrate the unique games conjecture?</p>

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

<p>Example of the kind of illustrations produced in the past are at</p>

<p><a href="http://www.ams.org/meetings/lectures/current-events-bulletin">http://www.ams.org/meetings/lectures/current-events-bulletin</a></p>

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

<p>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.</p>

<p>Other suggestions?</p>

CC BY-SA 2.5
2010-09-13T13:11:58.000Z
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.
Aaron Sterling
<cc.complexity-theory><unique-games-conjecture>
Visualizing Unique Games
Luca Trevisan
# Visualizing Unique Games

(Asked by: username_0 on 2010-09-13)

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

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

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?

**Tags:** cc.complexity-theory, unique-games-conjecture

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2010-09-13. Score: 4 | Accepted answer

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.


---

