Inside the clustering threshold for random linear equations
arXiv:1309.6651
Abstract
We study a random system of linear equations over variables in GF(2), where each equation contains exactly variables; this is equivalent to -XORSAT. \cite{ikkm,amxor} determined the clustering threshold, : if $c=c^*_r+\e$ for any constant $\e>0$, then \aas the solutions partition into well-connected, well-separated {\em clusters} (with probability tending to 1 as ). This is part of a general clustering phenomenon which is hypothesized to arise in most of the commonly studied models of random constraint satisfaction problems, via sophisticated but mostly non-rigorous techniques from statistical physics. We extend that study to the range , showing that if $c=c^*_r+n^{-\d}, \d>0$, then the connectivity parameter of each -XORSAT cluster is $n^{Θ(\d)}$, as compared to when $c=c^*_r+\e$. This means that one can move between any two solutions in the same cluster via a sequence of solutions where consecutive solutions differ on at most $n^{Θ(\d)}$ variables; this is tight up to the implicit constant. In contrast, moving to a solution in another cluster requires that some pair of consecutive solutions differ in at least $n^{1-O(\d)}$ variables. Along the way, we prove that in a random -uniform hypergraph with edge-density $n^{-\d}$ above the -core threshold, \aas every vertex not in the -core can be removed by a sequence of $n^{Θ(\d)}$ vertex-deletions in which the deleted vertex has degree less than ; again, this is tight up to the implicit constant.