Circle configurations and the hardness of promise graph and hypergraph coloring
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 -gon gives a strong -coloring and a rainbow -coloring of the same instance. A circle coloring built from single-coordinate changes gives hardness of for every nonempty symmetric reconfigurable relation with , and the monochromatic-clique dichotomy of Banakh, Barsukov, and Nakajima without the Rich -to- Conjecture. For triples we obtain hardness of linearly ordered coloring for all fixed palettes . 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
References
- 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
- 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
- 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 -ball . Israel J. Math. 211 (2016), 221--238. arXiv version 4 (https://arxiv.org/abs/1309.3315v4).DOI
- 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 -colourable graphs . STOC 2025.DOI
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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 -to- games conjecture? Theory of Computing 21 (2025), article 11.link
- 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
- 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
- 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
- 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
- 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 -to- games with perfect completeness . ECCC TR26-179, September 14, 2026. arXiv:2610.12378v2 (https://arxiv.org/html/2610.12378v2).arXiv
- 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
- 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
- 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
- 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
- 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 -to- hardness of coloring 3-colorable graphs with colors . ICALP 2020, article 62.DOI
- 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
- 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 -coloring . J. Combin. Theory Ser. B 48 (1990), 92--110.DOI
- 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
- 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
- https://arxiv.org/abs/1904.03214 A. Krokhin and J. Opršal. https://arxiv.org/abs/1904.03214 The complexity of 3-colouring -colourable graphs . FOCS 2019, 1227--1239.link
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- https://arxiv.org/abs/1907.00872 M. Wrochna and S. Živný. https://arxiv.org/abs/1907.00872 Improved hardness for -colourings of -colourable graphs . SODA 2020, 1426--1435.link
Version history
- v1 · 25 pagesSubmitted by Yuwen ZhouInitial depositCurrentNov 18, 2026