### Abstract

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*for this model: if^{∗}_{r}*c*=*c*− for any constant > 0 then with high probability all solutions form a well-connected cluster; whereas if^{∗}_{r }*c*=*c*+, then with high probability the solutions partition into well-connected, well-separated clusters (with probability tending to 1 as^{∗}_{r }*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.Original language | English |
---|---|

Pages (from-to) | 197-218 |

Number of pages | 22 |

Journal | Random Structures & Algorithms |

Volume | 52 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1 Mar 2018 |

### Keywords

- clustering threshold
- critical window
- phase transition
- random XORSAT
- solution geometry

## Cite this

Gao, P., & Molloy, M. (2018). Inside the clustering window for random linear equations.

*Random Structures & Algorithms*,*52*(2), 197-218. https://doi.org/10.1002/rsa.20740