Threshold existence conjectures for random NAE-k-SAT and hypergraph 2-colourability
For every integer , let be a random -NAE-SAT instance with variables and independently uniformly chosen clauses, and let be a uniformly random -uniform hypergraph with vertices and edges. The conjectures assert that there exist constants such that, for every ,
and
Here, a NAE assignment is one in which every clause contains both truth values, and a hypergraph is -colourable if its vertices can be coloured with two colours so that no edge is monochromatic.
References
- Threshold existence for random NAE-k-SAT and random hypergraph 2-colourability — arXiv — Pavel Zakharov
Source: arXiv
Progress summary
A new preprint claims to settle both threshold questions for every constraint size, but the claim has not been independently checked.
The conjectures ask whether sharp limiting thresholds exist for random NAE--SAT and random hypergraph -colourability. Achlioptas and Moore formulated these questions in 2006; the latest preprint claims an all- resolution and an inequality between the two thresholds.
Known results
- Achlioptas and Moore (2006): formulated the threshold-existence conjectures and proved bounds, but not convergence.
- Ding, Sly, and Sun (2013; published 2015): established an exact threshold for random regular NAE--SAT for sufficiently large , a different model.
- Chang, Kolhe, and Sohn (2024): obtained upper bounds for random regular hypergraph -colourability and regular NAE--SAT.
October 2026 preprint
Pavel Zakharov’s preprint claims threshold existence for both standard random models for every , together with an inequality relating their thresholds. It remains an unrefereed claim without independent mathematical assessment.
Current status (as of November 2026): The standard-model threshold-existence questions remain open in the verified literature; Zakharov’s all- resolution claim is unverified.
Solutions 0
No solutions have been posted yet.