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
- Yuwen Zhou
Institutions
- University of British Columbia (CA)
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