Threshold existence for random NAE- k-SAT and random hypergraph 2-colourability
math.CO, cs.DM
Submitted: 2026-10-31
Updated: 2026-10-31
License: http://creativecommons.org/licenses/by/4.0/
The gist: The existence of limiting threshold densities for random hypergraph 2-colourability and random NAE- k-SAT was conjectured in earlier work…
Terminology
Abstract
The existence of limiting threshold densities for random hypergraph 2-colourability and random NAE- k-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 k at least 3. We also show that α 2-col k at most α NAE k for each k at least 3.
Sources
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality