PreprintCC BY-NC-SA 4.0arXiv
The Scaling Window of Random k-SAT
Abstract
We prove a general upper bound for scaling windows of sparse monotone covering problems. From that, we deduce that for every fixed value k≥ 3, the window of random k-SAT is O(n/log n), improving the Friedgut-Bourgain bound of O(n/loglog n). We also show that random signed Not-All-Equal-k-SAT and hypergraph non-two-colourability (Property B) have windows of the same order. Our upper bound for scaling windows of sparse monotone covering problems follows from a general strategy combining the strengthening of Bourgain's sharp threshold theorem by Keevash, Lifshitz, Long, and Minzer with a local-to-random replacement principle. This provides a systematic method for proving scaling-window bounds, addressing a question of Perkins.
Related
- Characterization and scaling limit of three-dimensional loop-erased random walk and random-walk loop-catchers
- The threshold for fractional clique decompositions of random hypergraphs, via matrix scaling
- Scaling limit of the collision measure for two-dimensional random walks
- Scaling limits of critical branching random walks and their snakes
- Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling
BibTeX
@misc{carenini2026scaling,
title = {{The Scaling Window of Random $k$-SAT}},
author = {Gaia Carenini},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26222},
eprint = {2609.26222},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26222},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - The Scaling Window of Random k-SAT
AU - Gaia Carenini
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.26222
UR - https://arxiv.org/abs/2609.26222
AB - We prove a general upper bound for scaling windows of sparse monotone covering problems. From that, we deduce that for every fixed value k≥ 3, the window of random k-SAT is O(n/log n), improving the Friedgut-Bourgain bound of O(n/loglog n). We also show that random signed Not-All-Equal-k-SAT and hypergraph non-two-colourability (Property B) have windows of the same order. Our upper bound for scaling windows of sparse monotone covering problems follows from a general strategy combining the strengthening of Bourgain's sharp threshold theorem by Keevash, Lifshitz, Long, and Minzer with a local-to-random replacement principle. This provides a systematic method for proving scaling-window bounds, addressing a question of Perkins.
ER -