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 sigma and a first-order theory T for sigma composed of symmetry and anti-reflexivity axioms. We define a binomial random model of finite sigma-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 sigma 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 sigma. 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 similar to c/n(k-1), independently any first-order property of k-CNF formulas that implies unsatisfiability does almost surely not hold as n tends to infinity.