Refutation and Spectrally Quiet Planting of Cuts and Colorings in Random Graphs
summary
Constructs a spectrally quiet planted model by taking random d-regular graphs as the null and sampling random lifts of a small k-colorable base so that the base graph’s eigenvalues lift but the remaining spectrum matches the null; requires K−1 dividing D in the paper and generalizes conjecturally to any k-colorable Ramanujan base. Shows Hoffman-style spectral refutation works when k ≲ √d/2, but for the lifted model the trivial BP fixed point is stable and low-degree/local-statistics SDPs fail to distinguish, though lifted eigenvectors still reveal the planting.
AI-written summary · about