A Finite De Bruijn Certificate Improving the Upper Bound for One-Round Randomized 2-Coloring of Cycles

We give a finite, machine-checkable upper-bound certificate for one-round randomized 2-coloring of directed cycles within the De Bruijn-graph framework of Flin et al. On the normal De Bruijn graph of order 497, the certified cut has 46,298,451,764 bichromatic edges out of 61,013,446,081 total edges, leaving 14,714,994,317 monochromatic edges. This yields p* ≤ 14,714,994,317 / 61,013,446,081= 0.2411762531404098… which strictly improves the previously published upper bound 94,835 / 393,216. The certificate is obtained by midpoint discretization of the published three-parameter randomized rule followed by 4,750 explicitly recorded vertex flips. All reported comparisons are verified using exact integer arithmetic; in particular, the strict improvement is certified by an exact cross-product comparison. The contribution is deliberately narrow. We claim a finite, reproducible upper-bound certificate within the existing De Bruijn reduction. We do not claim a new general framework, a new lower bound, or optimality of the displayed finite cut. This record is a preprint and has not been peer reviewed.