Circle configurations and the hardness of promise graph and hypergraph coloring

Contributed by Yuwen Zhou ↗

Version 1 / Nov 19, 2026 / CC BY 4.0

Abstract

In 2017 Brakensiek and Guruswami conjectured that promise graph homomorphism is NP-hard for every non-bipartite source and loopless target admitting a homomorphism from the source. At CCC 2016 they conjectured hardness of properly coloring a uniform hypergraph promised a strong coloring with one more color than its uniformity. We prove both conjectures by a configuration theorem on the circle. For any fixed finite configuration of distinct rational phases, the theorem gives a reduction whose satisfiable instances place every edge near a translate of the configuration and whose unsatisfiable instances have arbitrarily small independence ratio. An antipodal pair gives hardness for every odd cycle against every fixed clique of size at least three. A regular hh-gon gives a strong (h+1)(h+1)-coloring and a rainbow (h−1)(h-1)-coloring of the same instance. A circle coloring built from single-coordinate changes gives hardness of PCSP(R,NAEh(d))\mathrm{PCSP}(R,\mathrm{NAE}_h^{(d)}) for every nonempty symmetric reconfigurable relation RR with R→NAEh(d)R\to\mathrm{NAE}_h^{(d)}, and the monochromatic-clique dichotomy of Banakh, Barsukov, and Nakajima without the Rich 22-to-11 Conjecture. For triples we obtain hardness of linearly ordered coloring for all fixed palettes 3≤c≤d3\le c\le d. The proof subtracts an average of translated distance functions to detect an independent set, then uses conditional mean zero and a finite Ramsey alignment argument to decode a Label Cover assignment.

Provenance statement

The proof presented in this paper was developed through an interactive dialogue with GPT-6.2 Astra (OpenAI) and Claude Opus 5.5 (Anthropic). The author used them to explore multiple possible proof strategies and directions, and the AI generated the initial draft under the author's guidance. The author then critically examined the generated proof, verified each step for correctness and rigor, and revised it where necessary. The author takes full responsibility for the final content. The author has checked and understood the statements of the main results and the outline of the proof in Section 1; the detailed proofs in the remaining sections were checked only by AI systems.

References

  1. https://arxiv.org/abs/1810.02784 P. Austrin, A. Bhangale, and A. Potukuchi. Improved inapproximability of rainbow coloring (https://arxiv.org/abs/1810.02784). arXiv:1810.02784, 2018.arXiv
  2. https://people.seas.harvard.edu/~madhusudan/papers/1992/almss-journ.pdf S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems (https://doi.org/10.1145/278298.278306). J. ACM 45 (1998), 501--555.DOI
  3. https://arxiv.org/pdf/1309.3315v4 https://link.springer.com/article/10.1007/s11856-015-1265-6 T. Austin. https://doi.org/10.1007/s11856-015-1265-6 On the failure of concentration for the ℓ∞\ell_\infty-ball . Israel J. Math. 211 (2016), 221--238. arXiv version 4 (https://arxiv.org/abs/1309.3315v4).DOI
  4. https://arxiv.org/pdf/2504.07592 S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner. https://doi.org/10.1145/3717823.3718154 Hardness of 4-colouring GG-colourable graphs . STOC 2025.DOI
  5. https://arxiv.org/abs/1811.00970 L. Barto, J. Bulín, A. Krokhin, and J. Opršal. Algebraic approach to promise constraint satisfaction (https://arxiv.org/abs/1811.00970). J. ACM 68 (2021), article 28.link
  6. https://drops.dagstuhl.de/storage/00lipics/lipics-vol380-lics2026/html/LIPIcs.LICS.2026.13/LIPIcs.LICS.2026.13.html https://arxiv.org/html/2605.09815v2 D. Banakh, A. Barsukov, and T.-V. Nakajima. Towards infinite PCSP: a dichotomy for monochromatic cliques (https://doi.org/10.4230/LIPIcs.LICS.2026.13). LICS 2026, LIPIcs 380, article 13. Full version (https://arxiv.org/html/2605.09815v2).DOI
  7. https://drops.dagstuhl.de/storage/00lipics/lipics-vol050-ccc2016/LIPIcs.CCC.2016.14/LIPIcs.CCC.2016.14.pdf J. Brakensiek and V. Guruswami. New hardness results for graph and hypergraph colorings (https://doi.org/10.4230/LIPIcs.CCC.2016.14). CCC 2016, LIPIcs 50, article 14.DOI
  8. https://eccc.weizmann.ac.il/report/2016/183/ https://arxiv.org/pdf/1704.01937v1 https://doi.org/10.1137/1.9781611975031.117 J. Brakensiek and V. Guruswami. Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy (https://eccc.weizmann.ac.il/report/2016/183/). ECCC TR16-183, 2016, revised 2017 and 2021. Conference version, Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy , SODA 2018.DOI
  9. https://drops.dagstuhl.de/storage/00lipics/lipics-vol081-approx-random2017/LIPIcs.APPROX-RANDOM.2017.4/LIPIcs.APPROX-RANDOM.2017.4.pdf J. Brakensiek and V. Guruswami. The quest for strong inapproximability results with perfect completeness (https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2017.4). APPROX/RANDOM 2017, LIPIcs 81, article 4.DOI
  10. https://arxiv.org/pdf/2110.10725v2 M. Braverman, S. Khot, N. Lifshitz, and D. Minzer. An invariance principle for the multi-slice, with applications (https://arxiv.org/abs/2110.10725v2). Full version, arXiv:2110.10725v2, 2025.arXiv
Show all 37 referencesShow fewer references
  1. https://andreikrokhin.webspace.durham.ac.uk/wp-content/uploads/sites/78/2021/04/STOC19__Algebraic_approach_to_promise_constraint_satisfaction.pdf J. Bulín, A. Krokhin, and J. Opršal. Algebraic approach to promise constraint satisfaction (https://doi.org/10.1145/3313276.3316300). STOC 2019.DOI
  2. https://raw.githubusercontent.com/KokunoYumeto/open-math-courses-public/75db3c5582e4891f918c5ca00e5444f22078a83f/docs/courses/large-independent-sets-in-three-colorable-graphs/src/label-cover-and-the-graph-of-the-reduction.md Open Mathematics Courses. Large independent sets in three-colorable graphs: Label Cover and the graph of the reduction (https://github.com/KokunoYumeto/open-math-courses-public/blob/75db3c5582e4891f918c5ca00e5444f22078a83f/docs/courses/large-independent-sets-in-three-colorable-graphs/src/label-cover-and-the-graph-of-the-reduction.md). Exercise 6.5, October 13, 2026.link
  3. https://theoryofcomputing.org/articles/v021a011/v021a011.pdf I. Dinur, S. Khot, G. Kindler, D. Minzer, and M. Safra. https://theoryofcomputing.org/articles/v021a011/ Towards a proof of the 22-to-11 games conjecture? Theory of Computing 21 (2025), article 11.link
  4. https://doi.org/10.1137/07068062X I. Dinur, E. Mossel, and O. Regev. Conditional hardness for approximate coloring (https://doi.org/10.1137/07068062X). SIAM J. Comput. 39 (2009), 843--873.DOI
  5. https://weizmann.elsevierpure.com/en/publications/the-hardness-of-3-uniform-hypergraph-coloring/ I. Dinur, O. Regev, and C. Smyth. The hardness of 3-uniform hypergraph coloring (https://doi.org/10.1007/s00493-005-0032-4). Combinatorica 25 (2005), 519--535.DOI
  6. https://arxiv.org/abs/1305.1979 I. Dinur and D. Steurer. Analytical approach to parallel repetition (https://arxiv.org/abs/1305.1979). STOC 2014, 624--633.link
  7. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.34 M. Filakovský, T.-V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs (https://doi.org/10.4230/LIPIcs.STACS.2024.34). STACS 2024, LIPIcs 289, article 34.DOI
  8. https://eccc.weizmann.ac.il/report/2026/179/ https://arxiv.org/html/2610.12378v2 Y. Fei, D. Minzer, and S. Wang. https://eccc.weizmann.ac.il/report/2026/179/ On the hardness of 44-to-11 games with perfect completeness . ECCC TR26-179, September 14, 2026. arXiv:2610.12378v2 (https://arxiv.org/html/2610.12378v2).arXiv
  9. https://github.com/openai/math/blob/main/preprints/Perfect-completeness-for-2-to-1-games-September-23-2026/paper.pdf OpenAI. Perfect completeness for 2-to-1 games (https://github.com/openai/math/blob/main/preprints/Perfect-completeness-for-2-to-1-games-September-23-2026/paper.pdf). OpenAI Math Release, item 105, September 23, 2026.link
  10. https://projects.csail.mit.edu/jacm/jacm76.html M. R. Garey and D. S. Johnson. The complexity of near-optimal graph coloring (https://doi.org/10.1145/321921.321926). J. ACM 23 (1976), 43--49.DOI
  11. https://doi.org/10.1137/S0895480100376794 V. Guruswami and S. Khanna. On the hardness of 4-coloring a 3-colorable graph (https://doi.org/10.1137/S0895480100376794). SIAM J. Discrete Math. 18 (2004), 30--40.DOI
  12. https://eccc.weizmann.ac.il/report/2014/043/ V. Guruswami and E. Lee. Strong inapproximability results on balanced rainbow-colorable hypergraphs (https://eccc.weizmann.ac.il/report/2014/043/). ECCC TR14-043, 2014.link
  13. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.62 V. Guruswami and S. Sandeep. https://doi.org/10.4230/LIPIcs.ICALP.2020.62 dd-to-11 hardness of coloring 3-colorable graphs with O(1)O(1) colors . ICALP 2020, article 62.DOI
  14. https://eccc.weizmann.ac.il/report/2019/094/ https://doi.org/10.1137/19M127731X V. Guruswami and S. Sandeep. Rainbow coloring hardness via low sensitivity polymorphisms (https://doi.org/10.1137/19M127731X). SIAM J. Discrete Math. 34 (2020), 520--537.DOI
  15. https://iuuk.mff.cuni.cz/~nesetril/src/biblio.html P. Hell and J. Nešetřil. https://doi.org/10.1016/0095-8956(90)90132-J On the complexity of HH-coloring . J. Combin. Theory Ser. B 48 (1990), 92--110.DOI
  16. https://raw.githubusercontent.com/openai/math/main/preprints/Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026/build/source/main.tex OpenAI. Hardness of finding large independent sets in three-colorable graphs (https://github.com/openai/math/tree/main/preprints/Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026). OpenAI Math Release, item 106, September 24, 2026.link
  17. https://link.springer.com/article/10.1007/s004930070013 S. Khanna, N. Linial, and S. Safra. On the hardness of approximating the chromatic number (https://doi.org/10.1007/s004930070013). Combinatorica 20 (2000), 393--415.DOI
  18. https://arxiv.org/abs/1904.03214 A. Krokhin and J. Opršal. https://arxiv.org/abs/1904.03214 The complexity of 3-colouring HH-colourable graphs . FOCS 2019, 1227--1239.link
  19. https://arxiv.org/pdf/2003.11351 A. Krokhin, J. Opršal, M. Wrochna, and S. Živný. Topology and adjunction in promise constraint satisfaction (https://arxiv.org/abs/2003.11351). SIAM J. Comput. 52 (2023), 38--79.link
  20. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.184 A. Krokhin and D. Vagnozzi. Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard (https://doi.org/10.4230/LIPIcs.ICALP.2026.184). ICALP 2026, LIPIcs 374, article 184.DOI
  21. https://raw.githubusercontent.com/openai/math/main/lean/docs/106.md OpenAI. Hardness of coloring three-colorable graphs (https://github.com/openai/math/blob/main/lean/docs/106.md). OpenAI Math Release, Lean formalization scope.link
  22. https://doi.org/10.1090/S0002-9904-1934-05978-0 E. J. McShane. Extension of range of functions (https://doi.org/10.1090/S0002-9904-1934-05978-0). Bull. Amer. Math. Soc. 40 (1934), 837--842.DOI
  23. https://arxiv.org/pdf/2501.12062 T.-V. Nakajima, Z. Verwimp, M. Wrochna, and S. Živný. Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings (https://arxiv.org/abs/2501.12062). arXiv:2501.12062, 2025.arXiv
  24. https://www.cs.ox.ac.uk/Stanislav.Zivny/publications/nz23toct-preprint.pdf https://www.cs.ox.ac.uk/publications/publication15828-abstract.html T.-V. Nakajima and S. Živný. Linearly ordered colourings of hypergraphs (https://doi.org/10.1145/3570909). ACM Trans. Comput. Theory 14, nos. 3--4 (2023).DOI
  25. https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-30.1.264 F. P. Ramsey. On a problem of formal logic (https://doi.org/10.1112/plms/s2-30.1.264). Proc. London Math. Soc. (2) 30 (1930), 264--286.DOI
  26. https://doi.org/10.1137/S0097539795280895 R. Raz. A parallel repetition theorem (https://doi.org/10.1137/S0097539795280895). SIAM J. Comput. 27 (1998), 763--803.DOI
  27. https://arxiv.org/abs/1907.00872 M. Wrochna and S. Živný. https://arxiv.org/abs/1907.00872 Improved hardness for HH-colourings of GG-colourable graphs . SODA 2020, 1426--1435.link

Version history

  1. v1 · 25 pagesSubmitted by Yuwen ZhouInitial depositCurrentNov 18, 2026