Inside the clustering window for random linear equations

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. Previous work has established a clustering threshold,c r ∗for this model: if c = c r ∗ − ϵ for any constant ϵ > 0 then with high probability all solutions form a well‐connected cluster; whereas if c = c r ∗ + ϵ , then with high probability 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 nonrigorous techniques from statistical physics. We extend that study to the range c = c r ∗ + o ( 1 ) , and prove that the connectivity parameters of the r ‐XORSAT clusters undergo a smooth transition around the clustering threshold.