2012/12/16 by Pittel, Boris, Sorkin, Gregory B.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1212.3822
We consider "unconstrained" random k-XORSAT, which is a uniformly random system of m linear non-homogeneous equations in \mathbbF2 over n variables, each equation containing k ≥ 3 variables, and also consider a "constrained" model where every variable appears in at least two equations. Dubois and Mandler proved that m/n=1 is a sharp threshold for satisfiability of constrained 3-XORSAT, and analyzed the 2-core of a random 3-uniform hypergraph to extend this result to find the threshold for unconstrained 3-XORSAT. We show that m/n=1 remains a sharp threshold for satisfiability of constrained k-XORSAT for every k ≥ 3, and we use standard results on the 2-core of a random k-uniform hypergraph to extend this result to find the threshold for unconstrained k-XORSAT. For constrained k-XORSAT we narrow the phase transition window, showing that n-m → ∞ implies almost-sure satisfiability, while m-n → ∞ implies almost-sure unsatisfiability.