← All problems

Threshold existence conjectures for random NAE-k-SAT and hypergraph 2-colourability

For every integer k≥3k\ge 3, let Fk(n,m)F_k(n,m) be a random kk-NAE-SAT instance with nn variables and mm independently uniformly chosen clauses, and let Hk(n,m)H_k(n,m) be a uniformly random kk-uniform hypergraph with nn vertices and mm edges. The conjectures assert that there exist constants αkNAE,αk2−col>0\alpha_k^{\mathrm{NAE}},\alpha_k^{\mathrm{2-col}}>0 such that, for every ε>0\varepsilon>0,

lim⁡n→∞Pr⁡ ⁣(Fk ⁣(n,⌊(αkNAE−ε)n⌋) is NAE-satisfiable)=1,\lim_{n\to\infty}\Pr\!\left(F_k\!\left(n,\left\lfloor(\alpha_k^{\mathrm{NAE}}-\varepsilon)n\right\rfloor\right)\text{ is NAE-satisfiable}\right)=1, lim⁡n→∞Pr⁡ ⁣(Fk ⁣(n,⌊(αkNAE+ε)n⌋) is NAE-satisfiable)=0,\lim_{n\to\infty}\Pr\!\left(F_k\!\left(n,\left\lfloor(\alpha_k^{\mathrm{NAE}}+\varepsilon)n\right\rfloor\right)\text{ is NAE-satisfiable}\right)=0,

and

lim⁡n→∞Pr⁡ ⁣(Hk ⁣(n,⌊(αk2−col−ε)n⌋) is 2-colourable)=1,\lim_{n\to\infty}\Pr\!\left(H_k\!\left(n,\left\lfloor(\alpha_k^{\mathrm{2-col}}-\varepsilon)n\right\rfloor\right)\text{ is 2-colourable}\right)=1, lim⁡n→∞Pr⁡ ⁣(Hk ⁣(n,⌊(αk2−col+ε)n⌋) is 2-colourable)=0.\lim_{n\to\infty}\Pr\!\left(H_k\!\left(n,\left\lfloor(\alpha_k^{\mathrm{2-col}}+\varepsilon)n\right\rfloor\right)\text{ is 2-colourable}\right)=0.

Here, a NAE assignment is one in which every clause contains both truth values, and a hypergraph is 22-colourable if its vertices can be coloured with two colours so that no edge is monochromatic.

References

Progress summary

Refreshed
Open · solution reported

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-kk-SAT and random hypergraph 22-colourability. Achlioptas and Moore formulated these questions in 2006; the latest preprint claims an all-kk 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-kk-SAT for sufficiently large kk, a different model.
  • Chang, Kolhe, and Sohn (2024): obtained upper bounds for random regular hypergraph 22-colourability and regular NAE-kk-SAT.

October 2026 preprint

Pavel Zakharov’s preprint claims threshold existence for both standard random models for every kk, 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-kk resolution claim is unverified.

Sources

Solutions 0

No solutions have been posted yet.