Probabilities of first-order sentences on sparse random relational structures: An application to definability on random CNF formulas

We extend the convergence law for sparse random graphs proven by Lynch to arbitrary relational languages. We consider a finite relational vocabulary s and a first-order theory T for s composed of symmetry and anti-reflexivity axioms. We define a binomial random model of finite s-structures that satisfy T and show that first-order properties have well defined asymptotic probabilities when the expected number of tuples satisfying each relation in s is linear. It is also shown that these limit probabilities are well behaved with respect to several parameters that represent the density of tuples in each relation R in the vocabulary s¿. An application of these results to the problem of random Boolean satisfiability is presented. We show that in a random k-CNF formula on n variables, where each possible clause occurs with probability ~c/nk-1¿, independently any first-order property of k-CNF formulas that implies unsatisfiability does almost surely not hold as n tends to infinity.Peer ReviewedPostprint (published version