Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 39 min ago
PreprintCC BY 4.0arXiv

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

  • Pavel Zakharov
Open at sourcePDFDOICite

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≥ 3. We also show that α2−colk ≤ αNAEk for each k≥ 3.

Related

  1. The terminal leave in random greedy hypergraph matching
    Peter Keevash
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Hitting time for loose Hamilton cycles in the random hypergraph process
    Jared León, Xizhi Liu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Hypergraph Representation Learning with Hyperlink Random Effects
    Zimeng Li, Shihao Wu, Gongjun Xu +1
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  4. Threshold for the existence of scattering states for inhomogeneous nonlinear Schrödinger equations without gauge invariance
    Mourad Grira, Hayato Miyazaki, Slim Tayachi
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv
  5. An Exact Mass Threshold for Global Existence and Blow-up in Semilinear Anti-de Sitter Equations
    Wanderley Nunes do Nascimento, Michael Reissig
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{zakharov2026threshold,
  title = {{Threshold existence for random NAE-$k$-SAT and random hypergraph $2$-colourability}},
  author = {Pavel Zakharov},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.01338},
  eprint = {2611.01338},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01338},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Threshold existence for random NAE-k-SAT and random hypergraph $2$-colourability
AU  - Pavel Zakharov
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.01338
UR  - https://arxiv.org/abs/2611.01338
AB  - 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≥ 3. We also show that α^2−col_k ≤ α^NAE_k for each k≥ 3.
ER  -