Random graphs show sharp tipping point for adaptable 2-color edge patterns
On the Critical Window for Adaptable 2-Colorability
Discrete Mathematics
Summary
The paper studies when a network with edges colored red or blue can be recolored to avoid conflicts in a special way called adaptable 2-colorability. The authors find a precise tipping point where this property suddenly becomes likely in random graphs. They also identify key subgraphs and color patterns that determine if such recoloring is possible. Below this tipping point, all solutions are connected in a simple way, and above it, certain long alternating color paths appear.
What this means in practice
- •For network engineers: Predict when network link colorings can be adaptively adjusted to avoid conflicts as the network grows randomly.
- •For software testers: Guide the design of test cases for configurations where properties similar to 2-color satisfiability change abruptly, ensuring coverage near critical thresholds.
A theory result. No direct application yet.
Authors
Thomas Snow
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(\log{n})$ many vertices.