Talk:Unique games conjecture

Failed to Parse

When I load this page, there's a big red "Failed to Parse" on it at the bottom of the "Unique Label Cover" section. Can someone (who knows more about the UGC) take a look at that? — Preceding unsigned comment added by 142.244.222.54 (talk) 18:40, 9 February 2014 (UTC)

Missing

This page is missing any substantial discussion of why the UGC is important. Also missing are equivalent forms of the conjecture, e.g., 2LIN(q). 131.215.48.236 (talk) 22:29, 29 May 2008 (UTC)

Clarify for non-experts

I've added another reference that is good for non-experts, and made another one more prominent. We should mine them for insights to improve this important article, helping make it more accessible.★NealMcB★ (talk) 01:08, 30 October 2012 (UTC)

The UGC bound for Max-2-SAT

In this reference, the bound β achieved on Max-2-SAT in Theorem 3 is .943943... which is larger than .940... Is this an error, or does another paper prove the tight bound? --125.34.6.194 (talk) 02:38, 27 October 2013 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Unique games conjecture. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive http://web.archive.org/web/20120610155513/http://www.cs.princeton.edu:80/~dsteurer/subexpug.pdf to http://www.cs.princeton.edu/~dsteurer/subexpug.pdf

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 20:04, 20 July 2016 (UTC)

Unique label cover

For each edge, the colors on the two vertices are restricted to some particular ordered pairs Do you mean to say that there are k ordered pairs and each color appears at each vertex exactly once? (otherwise I don't see how you would get uniqueness) This means that an instance of label cover with unique constraints over an alphabet of size k can be represented as a directed graph together with a collection of permutations πe: [k] → [k], one for each edge e of the graph Such instances are strongly constrained in the sense that the colour of a vertex uniquely defines the colours of its neighbours

That is what it usually means, yes. It isn't a very interesting problem if you're asking for all the constraints to be satisfied (just pick a color for one vertex and propagate) but the problem is, for cases that can't all be satisfied, to satisfy approximately as many constraints as possible. —David Eppstein (talk) 20:52, 26 October 2018 (UTC)

which English to use

because there are uses of the different colour/color Awesomecat713 (talk) 16:28, 25 June 2021 (UTC)

Khot 2002 uses "color" so I think as the foundational document for this topic that is what we should follow. Our article was created in 2005 but the "colour" spelling appears to have been added in 2010, much later. —David Eppstein (talk) 16:50, 25 June 2021 (UTC)