{"id":"arxiv/2606.08597","url":"https://arxiv.org/abs/2606.08597","tags":["cs.DS","math.CO"],"score":0,"title":"Kikuchi Graphs of Random Hypergraphs are Approximately Johnson","domain":"cs.DS","source":"arxiv","authors":["Pravesh K. Kothari"],"reviews":0,"subject":"cs.DS","summary":"We prove that level-$\\ell$ Kikuchi graphs of random $2r$-uniform hypergraphs spectrally approximate the Kikuchi graph of the complete $2r$-uniform hypergraph at a sampling rate that is sharp up to a logarithmic factor, in the regime $r\\leq \\ell \\leq n/2$. Our proof is based on the matrix Bernstein inequality, but, unlike prior works, we apply it to an appropriate collection of blocks of Johnson eigenspaces. Our analysis relies on a new, simple band-locality property for arbitrary Kikuchi graphs. As an application, we prove that the natural degree-$2\\ell$ sum-of-squares relaxation for the Max…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-07","reactions":{}}