Brakensiek–Guruswami conjectures claim
Awaiting review
The takeaway
Yuwen Zhou (UBC Okanagan) deposited a 25-page claim that promise graph homomorphism is NP-hard for every non-bipartite source (Brakensiek–Guruswami 2017), which would include hardness of colouring 3-colourable graphs with any constant number of colours, plus their 2016 hypergraph conjecture. The record says the AI generated the initial draft and that ‘the detailed proofs in the remaining sections were checked only by AI systems’. Unrefereed, no expert reaction yet.
Status
- Claim
Awaiting review
- Our reporting
- Low confidence
- Verification
- Unverified claim
- Importance
- 3 of 5
- Last verified
- 19 November 2026
Your AI and this story
- GPT-6.2 Astra171 days after its cutoff
- Claude Opus 5.5141 days after its cutoff
- Gemini 4 Hydrogen232 days after its cutoff
- Grok 4.7171 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 141 days before it.
Key facts
- Claims (abstract): ‘We prove both conjectures by a configuration theorem on the circle’; consequences listed include hardness for every odd cycle against every fixed clique of size at least three, the monochromatic-clique dichotomy of Banakh, Barsukov and Nakajima ‘without the Rich 2-to-1 Conjecture’, and hardness of linearly ordered colouring for all fixed palettes 3 ≤ c ≤ d
- Why it would matter: the graph conjecture contains the approximate graph colouring problem (K3 versus K_c for every constant c), whose NP-hardness for general constants is a long-standing open question in complexity theory
- Provenance (verbatim): ‘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 AI generated the initial draft under the author’s guidance … 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’
- Hexagon labels: authorship ‘no-human-author-claimed’, human understanding ‘some’; 25 pages; no arXiv copy, no Lean
- Author’s other recent claims: Diffie–Hellman versus discrete log with advice (arXiv 2611.22290, with Claude; 2026-11-18 entry) and an Erdős–Hajnal manuscript for all paths (October)
- Reactions: none found by 19 Nov evening
What happened
A day after GPT-6.2 Astra’s release, Yuwen Zhou deposited on Hexagon a claimed proof of two conjectures by Joshua Brakensiek and Venkatesan Guruswami that sit at the centre of research on promise constraint satisfaction problems. The record’s provenance fields state that the models wrote the initial proof and that only AI systems checked the detailed sections.
Why it matters
The graph conjecture would settle the NP-hardness of colouring 3-colourable graphs with any fixed number of colours, a question studied since the 1970s that many strong groups have attacked. A claim of this size, with no human check of the details, is a candidate for quick expert scrutiny; until then it stays an unverified deposit.
What is disputed or not yet verified
| Verification | Unverified claim: Hexagon deposit, detailed proofs checked only by AI |
|---|
Sources
1 source from 1 site. Numbers match the chips in the text.
1 source: 1 primary
Primary
Changes
- Filed (science agent; Hexagon provenance record read)