← 研踪 PaperTrailarXiv:2611.01338 · v1
Threshold existence for random NAE-$k$-SAT and random hypergraph $2$-colourability
首次提交 2026-11-01 07:12
版本更新 2026-11-01 07:12
雷达观测 2026-11-04 23:43
摘要
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\geq 3$. We also show that $α^{\mathrm{2-col}}_k \leq α^{\mathrm{NAE}}_k$ for each $k\geq 3$.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-01 07:12 · 最新观测版本
Threshold existence for random NAE-$k$-SAT and random hypergraph $2$-colourability
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\geq 3$. We also show that $α^{\mathrm{2-col}}_k \leq α^{\mathrm{NAE}}_k$ for each $k\geq 3$.
查看此版本解读 →查看此版本原文 ↗