Finite size scaling of random XORSAT

Abstract

We consider a "configuration model" for random XORSAT which is a random system of $n$ equations over $m$ variables in ${\mathbb{F}}_2$. Each equation is of the form $y_1+y_2+\cdots +y_k=b$ where $k\ge 3$ is fixed, $y_1,y_2,\cdots$ are variables (not necessarily distinct) and $b\in {\mathbb{F}}_2$. The equations are chosen independently and uniformly at random with replacement. It is known \cite{Dubois02, Dietzfelbinger10, pittel2016} that there exists ${\rho }_k$ such that $m/n={\rho }_k$ is a sharp threshold for the satisfiability of this system. In this note we show that for the configuration model, the width of SAT-UNSAT transition window for random $k$-XORSAT is $\Theta (n^{-1/2})$ and also derive the exact scaling function.

15 pags

References in corpus (1)

• Finite size scaling for the core of large random hypergraphs