Visualiser des jeux uniques

Comment concevriez-vous une image pour illustrer la conjecture des jeux uniques?

Ceci est pour une présentation "Current Events" sur des jeux uniques lors de la prochaine réunion conjointe AMS et pour le livret qui sera produit.

Des exemples du type d'illustrations produites dans le passé

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

et si vous cliquez sur l'édition 2006, vous pouvez voir l'image que Madhu Soudan a utilisée pour illustrer son discours sur le PCP.

J'ai pensé à utiliser le gadget pour réduire les jeux uniques au maximum, ou le graphique de Khot-Vishnoi pour une taille raisonnablement petite. Une bonne suggestion que j'ai reçue était de dessiner le graphique étendu d'une étiquette d'une instance presque satisfaisante de jeux uniques, et de mettre en évidence dans une couleur différente les sommets correspondant à une solution optimale.

D'autres suggestions?

cc.complexity-theory unique-games-conjecture Luca Trevisan
la source

Dana Moshkovitz a eu quelques diapositives lors de la séance de croupe de Barriers II. Je ne sais pas s'ils auraient ce dont vous avez besoin, mais vous pourriez lui demander si vous pouvez les voir.

Aaron Sterling

Réponses:

Si j'allais illustrer des jeux uniques, je ferais quelque chose avec un graphique étendu par étiquette (similaire à la suggestion que vous avez mentionnée).

Mais en particulier, je comparerais le graphique de contraintes d'origine avec celui étendu par étiquette. Par exemple, étiquetez les bords dans le graphique de contraintes avec l'équation correspondante parmi:

$x_1 - x_2 = 0\mod 3$

$x_2 - x_3 = 0\mod 3$

$x_3 - x_1 = 1\mod 3$

Ensuite, il y aura une "torsion", espérons-le visuellement attrayante, entre les nuages de sommets et dans le graphique étendu. $x_1$ $x_3$

Daniel Apon
la source