Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: How frequently is a system of 2-linear Boolean equations solvable? | How frequently is a system of 2-linear Boolean equations solvable Boris Pittel and Ji-A Yeum Ohio State University Columbus Ohio USA bgp@ yeum@ Submitted Sep 7 2009 Accepted Jun 19 2010 Published Jun 29 2010 Mathematics Subject Classifications 05C80 05C30 34E05 60C05 Abstract We consider a random system of equations xi Xj b i j mod 2 xu E 0 1 b u v b v u E 0 1 with the pairs i j from E a symmetric subset of n X n . E is chosen uniformly at random among all such subsets of a given cardinality m alternatively i j E E with a given probability p independently of all other pairs. Also given E Pr be 0 Pr be 1 for each e E E independently of all other be . It is well known that as m passes through n 2 p passes through 1 n resp. the underlying random graph G n edges m G n 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 n 2 p 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 An-1 3 p 1 An-1 3 n resp. A o n1 12 the system is solvable with probability asymptotic to c A n-1 12 for some explicit function c A 0. Mike Molloy noticed that the Boolean system with be 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 A o n1 12 the probability of 2-colorability is 2-1 4e1 8c A n-1 12 and asymptotic to 2-1 4e1 8c A n-1 12 at a critical phase A O 1 and for A TO. 1 Introduction A system of 2-linear equations over GF 2 with n Boolean variables x1 . xn E 0 1 is Xi Xj bij mod 2 bij bj i E 0 1 i j . Pittel s research supported in part by NSF Grants .
