Brakensiek–Guruswami's approximate graph homomorphism hardness conjecture
Brakensiek–Guruswami's approximate graph homomorphism hardness conjecture
Let and be non-bipartite loopless undirected graphs such that . The Brakensiek–Guruswami conjecture asserts that
is -hard. Here is the approximate graph homomorphism problem distinguishing instances homomorphic to from instances not homomorphic to . This is presented as a stronger conjecture than the approximate graph-colouring conjecture; the source identifies graphs with loops or bipartite graphs as trivial or reducible to -colouring, while the stated non-bipartite loopless case remains open.
Sources & referencesView supporting material
Primary source
Lorenzo Ciardo and Stanislav Živný, “Semidefinite programming and linear equations vs. homomorphism problems”, arXiv:2311.00882 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.