On the Critical Window for Adaptable 2-Colorability

Abstract

We determine a sharp threshold for the adaptable 2-colorability of a random graph equipped with a uniformly random, not necessarily proper, red/blue coloring of the edges. To accomplish this, we characterize a family of subgraphs along with edge colorings whose inclusion or exclusion determines adaptable $2$-colorability. We further show that above the threshold, a long path with alternating edge colors is formed. We use this path to prove the existence of such a subgraph in the supercritical regime. We then provide and prove symmetric bounds on the critical window for $2$-adaptable colorability. Particularly, we prove bounds matching that of the critical windows for the giant component in the Erdős-Rényi random graph model as well as the satisfiability of a random $2$-SAT instance. Finally, we show that below the critical window, the solution space of adaptable $2$-colorings remains connected, that is one can travel from one adaptable $2$-coloring to another by a sequence of $2$-colorings which differ on O(logn) many vertices.

Maximum of the Two-Dimensional Directed Polymer in the Critical Window
Clement Cosco, Shuta Nakajima, Ofer Zeitouni
arXiv30 Oct 2026PreprintCC BY 4.0Full textProbabilityarXiv
Critical-Window Fluctuations and Disorder Universality for the Sherrington--Kirkpatrick Model
Yu Cheng, Song-Hao Liu, Qi-Man Shao +1
arXiv7 Sep 2026PreprintarXiv licenceFull textProbabilityarXiv
Adaptable High-Dimensional Change Point Detection via Ridge Regularization
Haoran Li, Haotian Xu
arXiv30 Aug 2026PreprintCC BY 4.0Full textStatisticsarXiv
Diverse and Adaptable Arm Coordination for Octopus-Crawling via Diffusion-Based Uncertainty-Aware Optimization
Seung Hyun Kim, Heng-Sheng Chang, Kimia Kazemi +2
arXiv17 Sep 2026PreprintCC BY-NC-SA 4.0Full textOptimisation & controlarXiv
Super adaptable graphs and the realization problem
Pere Ara, Joan Bosa, Laurent Cantier +2
arXiv18 Sep 2026PreprintarXiv licenceFull textAlgebra & number theory Analysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{snow2026critical,
  title = {{On the Critical Window for Adaptable 2-Colorability}},
  author = {Thomas Snow},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.12214},
  eprint = {2609.12214},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.12214},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - On the Critical Window for Adaptable 2-Colorability
AU  - Thomas Snow
PY  - 2026
DA  - 2026/09/17
PB  - arXiv
DO  - 10.48550/arxiv.2609.12214
UR  - https://arxiv.org/abs/2609.12214
AB  - We determine a sharp threshold for the adaptable 2-colorability of a random graph equipped with a uniformly random, not necessarily proper, red/blue coloring of the edges. To accomplish this, we characterize a family of subgraphs along with edge colorings whose inclusion or exclusion determines adaptable $2$-colorability. We further show that above the threshold, a long path with alternating edge colors is formed. We use this path to prove the existence of such a subgraph in the supercritical regime. We then provide and prove symmetric bounds on the critical window for $2$-adaptable colorability. Particularly, we prove bounds matching that of the critical windows for the giant component in the Erdős-Rényi random graph model as well as the satisfiability of a random $2$-SAT instance. Finally, we show that below the critical window, the solution space of adaptable $2$-colorings remains connected, that is one can travel from one adaptable $2$-coloring to another by a sequence of $2$-colorings which differ on O(logn) many vertices.
ER  -

Abstract

Related

Cite