Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is concerned about the paper "The 3-XORSAT threshold" by O. Dubois, J.Mandler. Here is the link: http://dx.doi.org/10.1016/S1631-073X(02)02563-3

Basically one would like to know when is a random system of linear equations $A x = b$ in $F_2$ admit a solution. the system A is a uniformly random 0/1 matrix, with exactly 3 1's per row. And $b$ is a random vector in $F_2^m$.

The idea is to reduce the matrix $A$ to a smaller matrix in which every column has at least two $1$'s, the so-called $2$-core of the matrix. Then one can show that if the $2$ core $A'$ has dimension $m \times n$, and if $m < n$, then the random linear equation has solution with high probability as $n$ goes to infinity; this is the easy direction. On the other hand, if $m > n$, then it has no solution with high probability, this is the direction I don't understand. So the ratio $m/n = 1$ is a threshold for satisfiability of the random system of equations.

The main proof of the hard direction is succinctly contained in theorem 1. There are several phrases in the proof that I don't follows:

  1. "providing we impose as a compatibility condition that each equation comprises either 3 variables ..", in the middle of first paragraph of page 964. Why can we impose such a condition?

  2. Why is "the total number of formulae in $\Psi_{m,n}$" equal to $2^m S(3m,n,2)n!$? Here $\Psi_{m,n}$ is the set of all 2-core matrices with 3 1's per row of dimension $m \times n$, and $S(3m,n,2)$ is the stirling number of second kind at level 2. I tried to think in terms of configuration model, but it still makes no sense, especially the $2^m$ factor.

That's it for now. I might have more questions down the road. But any suggestions or answers to the above two questions will be appreciated!

share|improve this question
    
Thanks for adding the right link to the paper! –  John Jiang May 3 '10 at 17:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.