How frequently is a system of 2-linear Boolean equations solvable? (Q986694)

Summary: We consider a random system of equations \(x_i+x_j= b_{(i,j)}\pmod 2\), \((x_u\in\{0,1\}\), \(b_{(v,u)}\in\{0,1\})\), with the pairs \((i,j)\) from \(E\), a symmetric subset of \([n]\times [n]\). \(E\) is chosen uniformly at random among all such subsets of a given cardinality \(m\); alternatively \((i,j)\in E\) with a given probability \(p\), independently of all other pairs. Also, given \(E\), \(\text{Pr}\{b_e=0\}= \text{Pr}\{b_e=1\}\) for each \(e\in E\), independently of all other \(b_{e'}\). It is well known that, as m passes through \(n/2\) (\(p\) passes through \(1/n\), resp.), the underlying random graph \(G(n,\# \text{edges}=m)\), \((G(n, \text{Pr(edge)}=p)\), resp.) undergoes a rapid transition, from essentially a forest of many small trees to a graph with one large, multicyclic, component in a sea of small tree components. We should expect then that the solvability probability decreases precipitously in the vicinity of \(m\sim n/2\) \((p\sim 1/n)\), and indeed this probability is of order \((1-2m/n)^{1/4}\), for \(m<n/2 ((1-pn)^{1/4}\), for \(p<1/n\), resp.). We show that in a near-critical phase \(m=(n/2)(1+\lambda n^{-1/3})\) \((p= (1+\lambda n^{-1/3})/n\), resp.), \(\lambda= o(n^{1/12})\), the system is solvable with probability asymptotic to \(c(\lambda)n^{-1/12}\), for some explicit function \(c(\lambda)>0\). Mike Molloy noticed that the Boolean system with \(b_e\equiv 1\) is solvable iff the underlying graph is 2-colorable, and asked whether this connection might be used to determine an order of probability of 2-colorability in the near-critical case. We answer Molloy's question affirmatively and show that, for \(\lambda= o(n^{1/12})\), the probability of 2-colorability is \(\lesssim 2^{-1/4}e^{1/8}c(\lambda) n^{-1/12}\), and asymptotic to \(2^{-1/4}e^{1/8} c(\lambda)n^{-1/12}\) at a critical phase \(\lambda= O(1)\), and for \(\lambda\to-\infty\).