The solution space geometry of random linear equations. Issue 2 (12th April 2013)

• Record Type: Journal Article
• Authors: Achlioptas, Dimitris; Molloy, Michael
• Is Part Of: Random structures & algorithms. Volume 46:Issue 2(2015)
• Page Start: 197
• Page End: 231
• Publication Date: 2013-04-12
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20494
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>We consider random systems of linear equations over GF(2) in which every equation binds <italic>k</italic> variables. We obtain a precise description of the clustering of solutions in such systems. In particular, we prove that with probability that tends to 1 as the number of variables, <italic>n</italic>, grows: for every pair of solutions <italic>σ, τ</italic>, either there exists a sequence of solutions starting at <italic>σ</italic> and ending at <italic>τ</italic> such that successive solutions have Hamming distance <italic>O</italic>(log <italic>n</italic>), or every sequence of solutions starting at <italic>σ</italic> and ending at <italic>τ</italic> contains a pair of successive solutions with distance Ω(<italic>n</italic>). Furthermore, we determine precisely which pairs of solutions are in each category. Key to our results is establishing the following high probability property of cores of random hypergraphs which is of independent interest. Every vertex not in the <italic>r</italic>‐core of a random <italic>k</italic>‐uniform hypergraph can be removed by a sequence of <italic>O</italic>(log <italic>n</italic>) steps, where each step amounts to removing one vertex of degree strictly less than <italic>r</italic> at the time of removal. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 197–231, 2015</p> </abstract>