Inside the clustering threshold for random linear equations

Original · EN

We study a random system of cn linear equations over n variables in GF(2), where each equation contains exactly r variables; this is equivalent to r-XORSAT. ikkm,amxor determined the clustering threshold, c*ᵣ: if c=c*ᵣ+ for any constant >0, then the solutions partition into well-connected, well-separated clusters (with probability tending to 1 as n→∞). 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 c=c*ᵣ+o(1), showing that if c=c*ᵣ+n⁻, >0, then the connectivity parameter of each r-XORSAT cluster is nΘ⁽⁾, as compared to O(n) when c=c*ᵣ+. 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Θ⁽⁾ 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¹⁻ᵒ⁽⁾ variables. Along the way, we prove that in a random r-uniform hypergraph with edge-density n⁻ above the k-core threshold, every vertex not in the k-core can be removed by a sequence of nΘ⁽⁾ vertex-deletions in which the deleted vertex has degree less than k; again, this is tight up to the implicit constant.