Inside the clustering window for random linear equations. Issue 2 (20th November 2017)

• Record Type: Journal Article
• Authors: Gao, Pu; Molloy, Michael
• Is Part Of: Random structures & algorithms. Volume 52:Issue 2(2018)
• Page Start: 197
• Page End: 218
• Publication Date: 2017-11-20
• Subjects: clustering threshold -- critical window -- phase transition -- random XORSAT -- solution geometry; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20740
• Languages: English
• ISSNs: 1042-9832

Abstract

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 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.