Circle configurations and the hardness of promise graph and hypergraph coloring

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 h-gon gives a strong (h+1)-coloring and a rainbow (h−1)-coloring of the same instance. A circle coloring built from single-coordinate changes gives hardness of PCSP(R, NAEh(d)) for every nonempty symmetric reconfigurable relation R with R → NAEh(d), and the monochromatic-clique dichotomy of Banakh, Barsukov, and Nakajima without the Rich 2-to-1 Conjecture. For triples we obtain hardness of linearly ordered coloring for all fixed palettes 3 ≤ c ≤ 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. Use of AI. The proof was developed through an interactive dialogue with GPT-6.2 Astra (OpenAI) and Claude Opus 5.5 (Anthropic); the AI generated the initial draft under the author's guidance, and the author takes full responsibility for the final content.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-18
DOI
https://doi.org/10.5281/zenodo.24355968
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Circle configurations and the hardness of promise graph and hypergraph coloring

Yuwen Zhou
1 links
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

Circle configurations and the hardness of promise graph and hypergraph coloring

Yuwen Zhou
preprint en

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 h-gon gives a strong (h+1)-coloring and a rainbow (h−1)-coloring of the same instance. A circle coloring built from single-coordinate changes gives hardness of PCSP(R, NAEh(d)) for every nonempty symmetric reconfigurable relation R with R → NAEh(d), and the monochromatic-clique dichotomy of Banakh, Barsukov, and Nakajima without the Rich 2-to-1 Conjecture. For triples we obtain hardness of linearly ordered coloring for all fixed palettes 3 ≤ c ≤ 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. Use of AI. The proof was developed through an interactive dialogue with GPT-6.2 Astra (OpenAI) and Claude Opus 5.5 (Anthropic); the AI generated the initial draft under the author's guidance, and the author takes full responsibility for the final content.

Zenodo (CERN European Organization for Nuclear Research)
University of British Columbia (CA)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon