Premium
The solution space geometry of random linear equations
Author(s) -
Achlioptas Dimitris,
Molloy Michael
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20494
Subject(s) - mathematics , hypergraph , combinatorics , sequence (biology) , vertex (graph theory) , random variable , space (punctuation) , hamming distance , discrete mathematics , randomness , graph , computer science , statistics , genetics , biology , operating system
We consider random systems of linear equations over GF(2) in which every equation binds k 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, n , grows: for every pair of solutions σ,τ , either there exists a sequence of solutions starting at σ and ending at τ such that successive solutions have Hamming distance O (log n ), or every sequence of solutions starting at σ and ending at τ contains a pair of successive solutions with distance Ω( n ). 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 r ‐core of a random k ‐uniform hypergraph can be removed by a sequence of O (log n ) steps, where each step amounts to removing one vertex of degree strictly less than r at the time of removal. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 197–231, 2015