WorksMathematics
Threshold existence for random NAE--SAT and random hypergraph -colourability
Abstract
The existence of limiting threshold densities for random hypergraph -colourability and random NAE--SAT was conjectured in earlier work, including Achlioptas and Moore [RANDOM 2002] and Coja-Oghlan and Panagiotou [STOC 2012]. We prove these conjectures for all . We also show that for each .
Introduction
For the study of random constraint satisfaction problems (CSPs), one of the starting points was the question of Erdős and Rényi about the chromatic number of a random graph [16]. In the language of random CSPs, fixing the number of colours leads to the question of the -colourability threshold. Estimates of the chromatic number are known in many regimes [6, 12, 19], but the existence of a limiting colourability threshold remains open for general . One of the explanations regarding why the problem is so difficult comes from statistical mechanics. A heuristic called the cavity method predicts that before the satisfiability threshold, the solution set of a random CSP can undergo several other phase transitions, such as clustering and condensation [20]. Among other things, these transitions help explain the limitations of the second moment method [13, 14], one of the main tools for estimating thresholds in random structures.
A related question is the satisfiability conjecture for random -SAT [11]. Here a formula consists of independently sampled clauses, each being a disjunction of distinct uniformly chosen variables with independent uniform signs, and an assignment satisfies the formula if it makes at least one literal in every clause true. The conjecture asserts that for each fixed there is a constant clause density below which such a formula is satisfiable with high probability (whp) and above which it is unsatisfiable whp.
Friedgut’s sharp threshold theorem [17] establishes the existence of a threshold sequence, but does not establish its convergence. Writing for the random -SAT formula described above, for every fixed there is a sequence such that for every fixed and every sequence ,
as goes to infinity, provided the corresponding inequality holds for all sufficiently large . Similar sharp threshold results also hold for graph colourability [3] and for hypergraph 2-colourability and NAE--SAT [18]. However, sharpness alone does not imply that the threshold sequences converge as .
For random 2-SAT the threshold density is known to be [11]. For larger clause sizes, Ding, Sly and Sun [15] proved the satisfiability conjecture for all sufficiently large and identified the threshold with the value predicted by the cavity method. Recently, Carenini established an scaling window [9], and then improved it to [10]. These bounds count the number of random clauses one needs to add to decrease the satisfiability probability from to for any fixed . Combined with the Abbe–Montanari interpolation criterion [1], the latter estimate proves the existence of a limiting threshold for every fixed without identifying its value. An alternative proof later appeared in a manuscript by OpenAI [21]. It combines polynomial concentration for the last satisfiable index with an interpolation method to prove convergence directly, without using the Abbe–Montanari criterion.
For random hypergraph 2-colourability and random NAE--SAT, the existence of limiting threshold densities was conjectured in [4, 13]. Let and denote the corresponding sharp threshold sequences. For all sufficiently large and , the bound of Coja-Oghlan and Zdeborová [14] and the first moment method give
For NAE--SAT, Coja-Oghlan and Panagiotou [13] obtained the sharper estimate
Here the errors tend to zero as uniformly for sufficiently large , but these estimates do not establish convergence in for any fixed . Coja-Oghlan and Panagiotou also observe that the results of [14] carry over to NAE--SAT, and it is natural to expect the same asymptotic threshold for hypergraph 2-colourability. More recently, Carenini [9] proved scaling windows for both models, again leaving the convergence question open.
In this paper we prove that the limiting densities exist in both models for every fixed . For , let be the random -uniform hypergraph obtained by sampling edges independently and uniformly with replacement from the -subsets of its vertex set. A NAE-clause is satisfied if its literal values are not all equal. We represent by a NAE-formula with all signs positive, so the formula is satisfiable precisely when the hypergraph is 2-colourable. Let be the corresponding random NAE--SAT formula with independent uniform signs. Vertices correspond to variables, edges to clauses and colourings to assignments. In particular, variables within each clause are distinct, while clauses may repeat. We write SAT for the set of satisfiable NAE-formulas, and in statements concerning both models, denotes for and for .
Theorem 1.1. For every fixed there exist constants and such that for each and ,
Our second result compares the two thresholds for every clause size.
Theorem 1.2. In the setup of Theorem 1.1, .
Combining Theorem 1.2 with Eq. (1) gives the following upper bound for the random hypergraph 2-colourability threshold.
Corollary 1.3.
The proof of Theorem 1.1 follows the approach developed for random -SAT in [21]. For , add corresponding clauses one by one, and let
Thus is the last satisfiable index, capped at .
We first show that for , is within of its expectation with probability polynomially close to 1. A Poisson interpolation then compares satisfiability probabilities of the random formula on disjoint sets of variables with the random formula on their union, which is similar to the approach of Bayati, Gamarnik and Tetali [7]. Together, these estimates imply that converges.
The main novelty concerns the symmetry of the considered CSPs. For NAE-satisfiability, flipping all variable values preserves a solution. Thus no variable has the same value in all solutions, and the argument based on frozen variables does not apply directly. Instead, we group variables according to whether their relative values are fixed across all solutions. These equivalence classes are used to determine exactly the probability that an additional clause destroys every solution, which yields both the clause replacement estimate needed for concentration, and the convexity inequality needed for the interpolation. Interpolating between models with positive and randomly signed clauses also gives Theorem 1.2.
Declaration of AI use
Declaration of AI use. ChatGPT was used to assist with proofreading, presentation and checking proofs. It also suggested using a similar interpolation argument to establish Theorem 1.2.
Preliminaries
Throughout, the clauses are sampled independently with replacement. Within each proper clause, variables are distinct and uniformly sampled, and assignments take values in . A clause is satisfied if its literal values are not all equal.
Equivalence classes and clause addition
Let be any satisfiable NAE-formula on a variable set of size , with arbitrary signs and clause lengths. Write for its set of satisfying assignments. Define
Transitivity follows from , and reflexivity and symmetry are immediate. Denote its equivalence classes by . Fix and put
Within each part of one class the variables are equal in every solution, and variables in opposite parts of one class are opposite in every solution. Choosing another can only interchange the two parts of each class. For , let and be the probabilities that adding a uniformly random -clause on distinct variables makes unsatisfiable, with all signs being positive or independent and uniformly random respectively. Write and when the variables are instead sampled independently with replacement. For an unsatisfiable we set all four quantities to zero.
Lemma 2.1. For satisfiable and ,
For sampling with replacement and ,
Here .
Proof. A new clause destroys every solution precisely when its literal values are equal in every solution. For random signs this requires all its variables to lie in one class , and conditional on such a choice of variables, exactly two of the sign configurations have this property. This remains true with repeated variables, since signs are sampled independently for each literal. For positive signs the variables must all lie in one part of one class. □
The next lemma compares the probabilities of destroying all solutions by clauses of consecutive lengths.
Lemma 2.2. Let and let be a satisfiable NAE-formula on variables, with arbitrary signs and clause lengths. For put . Then
Proof. For , let , with . For , let , where ranges over the pairs in . Put and . By Lemma 2.1,
Set for , and for . Then
For we have , and for we have . Thus, in either case,
Applying convexity of and using (4)–(5) yields
where the last step uses and .
Forced variables
We call a variable forced if is satisfiable and flipping in any satisfying assignment makes that assignment unsatisfying. Let be the number of forced variables, with for unsatisfiable . Every variable in a class of size at least two is forced. Consequently, for and Lemma 2.1 implies
Finally, the following bounds keep the expected last satisfiable index away from zero and the cap.
Proposition 2.3. For every fixed , as ,
Proof. For either model, a fixed assignment violates a random clause with probability at least . Thus the first moment bound gives
Since , this implies the upper bounds. For the lower bounds, extending each clause of a random NAE-3-SAT formula by uniformly chosen distinct variables outside the original clause, with independent uniform signs, preserves satisfiability and produces the NAE--SAT formula. The same construction with positive signs applies to hypergraph 2-colourability. The bounds therefore follow from the results for NAE-3-SAT [2] and 3-uniform hypergraph 2-colourability [5]$. □
Variance and concentration
We begin with the NAE version of the clause replacement argument from [21 Lemma 2.1]. We use the equivalence classes from § 2.1, rather than frozen variables of ordinary SAT.
Proposition 3.1. Fix . There is such that the following holds for every . Let be any NAE-formula on variables, with arbitrary signs and clause lengths. For , let be a uniformly random -clause and let be independent uniformly random -clauses, all on distinct variables within each clause, with signs of type , independent of one another. Then
where , .
Proof. The assertion is immediate if is unsatisfiable. Otherwise put . It suffices to consider . By Lemma 2.2, . Since , for all sufficiently large , uniformly in ,
Independence of the new clauses implies
If , then , which proves the claim. If , Lemma 2.2 bounds away from zero uniformly in . Thus for sufficiently large , which gives a probability at least . □
Using Proposition 3.1 we control the total expected number of forced variables along the clause process.
Proposition 3.2. Fix and . For every integer and either ,
Proof. By symmetry, the -th summand is the probability that is satisfiable and is forced. The number of clauses containing has distribution . Delete these clauses to obtain , and erase the literal on from each deleted clause to obtain . Conditional on the incidence positions, consists of independent uniform -clauses on the remaining variables. The are independent uniform -clauses on these variables, independent of , with signs of type . If is forced, then
Put and use and from Proposition 3.1. Conditional on and the incidence positions, replace each by fresh -clauses. At each replacement, condition on all other clauses and apply Proposition 3.1. The total error is at most , and subtracting the probability that is itself unsatisfiable gives
For , we have , and
where the sum telescopes and is nonincreasing. Averaging the error with , we obtain
Fix an integer and . Write for the independent clauses of and set
For , let be the formula with the clause at position removed if . Set
In particular, , and is independent of .
Proposition 3.3. For ,
Proof. Apply Eq. (3.6) with and .
Proposition 3.4. For every and either ,
Proof. The proof of [21 Lemma 3.2] applies with killing probability , as it only uses independence of the clauses and monotonicity of satisfiability under clause addition.
Lemma 3.5. For fixed , , integers and ,
Proof. By (6),
For , has the same distribution as . Thus Propositions 3.2–3.4 yield
Corollary 3.6. Under the assumptions of Lemma 3.5, for either ,
Proof. Apply Chebyshev’s inequality and use for . □
From concentration to convergence
We now use the concentration bound to prove that the normalized expectations converge. For and , put
Thus , and .
Theorem 4.1. Fix an integer , and . Suppose there exist
such that for all sufficiently large ,
Then converges to , and
Poissonian model
Fix . For and , let be the NAE-formula with independent positive clauses, each formed by sampling variables independently and uniformly from the variables. Thus repetitions within clauses are allowed. Define in the same way, with independent uniform signs for each literal. For , write .
Lemma 4.2. For any , , and ,
Proof. We use a Poisson version of the combinatorial interpolation of [7 Proposition 2], as in [21 Lemma 5.2], with the killing probabilities from Lemma 2.1. Fix and partition the variable set into of sizes . At time , sample independent numbers of global and local clauses
Each clause has independently chosen variables from , or respectively, and signs of type . Let be their union and . Then
For each satisfiable realization of , take the classes and parts from § 2.1. A clause confined to therefore uses the intersections (or ) for . The Poisson add-one identity says that differentiation with respect to a clause family’s mean gives the expected change in the satisfiability indicator upon adding one clause, and this change is minus its killing probability. Therefore, Lemma 2.1 gives
Indeed, due to convexity,
For positive clauses, Lemma 2.1 gives
Integrating over proves both inequalities. □
From the Poisson model to proper clauses
We next transfer the concentration bounds to the Poisson model. Fix and parameters from the hypothesis of Theorem 4.1.
Lemma 4.3. Fix and . For and , put and let . For either ,
Moreover, and . All bounds are uniform over .
Proof. Apply the marked Poisson thinning argument of [21 Lemma 5.3]. The numbers of clauses with distinct variables and with a repetition are independent with laws
Conditional on and , the two clause families are independent, and any clause with distinct variables is a uniformly random set of size with signs of type . Thus the proper family has the law in either model. With denoting the full formula,
Independence and give the two inequalities. The moment bounds follow from . □
Lemma 4.4. Assume (8)–(9) and fix . For all sufficiently large , uniformly over ,
Proof. Take from Lemma 4.3 independently of the randomness inside clauses. By Chebyshev’s inequality and (9),
except on an event of probability uniformly for . If , these inequalities yield
Thus is satisfiable outside the exceptional event, and (10) implies (12) for large enough.
Conversely, if , then
with probability . Outside the exceptional event, for large , hence , so is unsatisfiable. The upper bound in (10) now yields (13).
Fix . The next lemma compares the expected threshold locations at different sizes.
Lemma 4.5. For all sufficiently large ,
Proof. Choose . For large it lies in . By (12) and Lemma 4.2,
(13) therefore implies for large , proving (14).
For (15), take . The one-variable formula is empty with probability , so . Thus Lemma 4.2 and (12) imply that , which is bounded away from zero. Applying (13) once more yields .
Convergence
Lemma 4.6. Let be a bounded real-valued sequence. Suppose there exist and , such that for large enough with ,
Then converges.
Proof. This is [21], Lemma 5.4.
Proof of Theorem 4.1
Proof of Theorem 4.1. Apply Lemma 4.6 to the sequence from Lemma 4.5, with and . This gives . For fixed , the gap is bounded away from zero for large , so (9) implies whp. For fixed , (9) instead gives , completing the proof.
Proof of Theorem 1.1
Proof of Theorem 1.1. Take . By Proposition 2.3, condition (8) holds with and . Corollary 3.6 gives (9) with and , thus Theorem 4.1 can be applied. For and large , the events and coincide, and for we use monotonicity of the property .
Threshold comparison
In this section we prove Theorem 1.2. For and , let be the random formula consisting of positive clauses and signed clauses, with and being independent. Each clause samples its variables independently and uniformly, with repetitions allowed, and signs in all clauses are independent and uniformly random.
For each satisfiable , use the classes and parts from Section 2.1. By Lemma 2.1,
and convexity implies for .
Writing , the same Poisson add-one identity as in Lemma 4.2 yields
Hence for every and . Suppose that for some , . Theorem 1.1, Poisson concentration and monotonicity imply that the distinct-variable formula with positive clauses is satisfiable with probability tending to one, while the corresponding signed formula is satisfiable with probability tending to zero. Here and converges in probability to . Furthermore, the coupling from Lemma 4.3 implies that is bounded away from zero, and that , which leads to a contradiction. Thus .
Pavel Zakharov, [email protected], Bielefeld University, Faculty of Mathematics, Universitätsstrasse 25, 33615 Bielefeld, Germany.
References
- [1]E. Abbe, A. Montanari: On the Concentration of the Number of Solutions of Random Satisfiability Formulas. Random Structures & Algorithms 45 (2014) 362–382.arxiv.org/abs/1006.3786
- [2]D. Achlioptas, A. Chvátal, G. Istrate, C. Moore: The Phase Transition in 1-in-k SAT and NAE 3-SAT. Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (2001) 721–722.DOI
- [3]D. Achlioptas, E. Friedgut: A Sharp Threshold for k-Colorability. Random Structures & Algorithms 14 (1999) 63–70.
- [4]D. Achlioptas, C. Moore: On the 2-Colorability of Random Hypergraphs. Randomization and Approximation Techniques in Computer Science (2002) 78–90.arxiv.org/abs/2011.04809
- [5]D. Achlioptas, C. Moore: Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold. SIAM Journal on Computing 36 (2006) 740–762.
- [6]D. Achlioptas, A. Naor: The Two Possible Values of the Chromatic Number of a Random Graph. Annals of Mathematics 162 (2005) 1335–1351.
- [7]M. Bayati, D. Gamarnik, P. Tetali: Combinatorial Approach to the Interpolation Method and Scaling Limits in Sparse Random Graphs. Annals of Probability 41 (2013) 4080–4115.
- [9]G. Carenini: The Scaling Window of Random k-SAT. arXiv:2609.26222 (2026).
- [10]G. Carenini: A Polynomial Scaling Window for Random k-SAT and a Proof of the Satisfiability Conjecture. Electronic Colloquium on Computational Complexity, Report No. 229 (2026).
- [11]V. Chvátal, B. Reed: Mick Gets Some (the Odds Are on His Side). Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (1992) 620–627.
- [12]A. Coja-Oghlan, M. Isaev, M. Kang, P. Zakharov: The Chromatic Number of a Random Graph with o(n^{3/2}) Edges. arXiv:2610.33678 (2026).
- [13]A. Coja-Oghlan, K. Panagiotou: Catching the k-NAESAT Threshold. Proceedings of the 44th Annual ACM Symposium on the Theory of Computing (2012) 899–908.
- [14]A. Coja-Oghlan, L. Zdeborová: The Condensation Transition in Random Hypergraph 2-Coloring. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (2012) 241–250.
- [15]J. Ding, A. Sly, N. Sun: Proof of the Satisfiability Conjecture for Large k. Annals of Mathematics 196 (2022) 1–388.
- [16]P. Erdős, A. Rényi: On the Evolution of Random Graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5 (1960) 17–61.
- [17]E. Friedgut, with an appendix by J. Bourgain: Sharp Thresholds of Graph Properties, and the k-SAT Problem. Journal of the American Mathematical Society 12 (1999) 1017–1054.DOI
- [18]E. Friedgut: Hunting for Sharp Thresholds. Random Structures & Algorithms 26 (2005) 37–51.DOI
- [19]A. Heckel: The Chromatic Number of Dense Random Graphs. Random Structures & Algorithms 53 (2018) 140–182.DOI
- [20]F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, L. Zdeborová: Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems. Proceedings of the National Academy of Sciences 104 (2007) 10318–10323.pubmed.ncbi.nlm.nih.gov/17567754
- [21]OpenAI: A Limiting Satisfiability Threshold for Every Fixed Clause Size. preprint (2026).DOI