2021/07/13 by Coja-Oghlan, Amin, Cooley, Oliver, Kang, Mihyun +2 · 1 citation
#05C80 #60B20 #94B05 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2107.06123
Let A be an n× n-matrix over \mathbbF2 whose every entry equals 1 with probability d/n independently for a fixed d>0. Draw a vector y randomly from the column space of A. It is a simple observation that the entries of a random solution x to A x=y are asymptotically pairwise independent, i.e., ∑_ie the overlap concentrates on a single value once we condition on the matrix A, while over the probability space of A its conditional expectation vacillates between two different values α_*(d)<α^*(d), either of which occurs with probability 1/2+o(1). This bifurcated non-concentration result provides an instructive contribution to both the theory of random constraint satisfaction problems and of inference problems on random structures.