Visualizando Jogos Exclusivos

19

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?

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:

4

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:

x1x2=0mod3

x2x3=0mod3

x3x1=1mod3

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.x1x3

Daniel Apon
fonte