Visualizando Jogos Exclusivos

Como você projetaria uma imagem para ilustrar a conjectura exclusiva dos jogos?

Isto é para uma apresentação dos "Eventos Atuais" sobre jogos exclusivos na próxima Reunião Conjunta da AMS e para o livreto que será produzido.

Exemplos do tipo de ilustrações produzidas no passado estão em

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

e se você clicar na edição de 2006, poderá ver a imagem que Madhu Sudan usou para ilustrar sua palestra no PCP.

Pensei em usar o gadget para reduzir jogos únicos ao corte máximo, ou no gráfico Khot-Vishnoi para um tamanho razoavelmente pequeno. Uma boa sugestão que recebi foi desenhar o gráfico estendido para rótulos de uma instância quase satisfatória de jogos únicos e destacar em uma cor diferente os vértices correspondentes a uma solução ideal.

Outras sugestões?

cc.complexity-theory unique-games-conjecture Luca Trevisan
fonte

Dana Moshkovitz teve alguns slides na sessão de garupa do Barriers II. Não sei se eles teriam o que você precisa, mas você pode perguntar se pode vê-los.

Aaron Sterling

Respostas:

Para ilustrar jogos únicos, eu faria algo com um gráfico estendido para rótulos (semelhante à sugestão que você mencionou).

Mas, especificamente, eu contrastaria o gráfico de restrição original com o estendido pela etiqueta. Por exemplo, rotule as arestas no gráfico de restrição com a equação correspondente dentre:

$x_1 - x_2 = 0\mod 3$

$x_2 - x_3 = 0\mod 3$

$x_3 - x_1 = 1\mod 3$

Depois, haverá uma "torção" (esperançosamente atraente para o visual) entre as nuvens de vértices e no gráfico estendido do rótulo. $x_1$ $x_3$

Daniel Apon
fonte