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

2020/06/10 by Lázaro Alberto Larrauri, Larrauri, Lázaro Alberto
Computer Science · #Advanced Algebra and Logic #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2006.06099

openalex publication_date 2020/06/10 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28

Abstract

We extend the convergence law for sparse random graphs proven by Lynch to\narbitrary relational languages. We consider a finite relational vocabulary\n\σ and a first order theory T for \σ composed of symmetry and\nanti-reflexivity axioms. We define a binomial random model of finite\n\σ-structures that satisfy T and show that first order properties have\nwell defined asymptotic probabilities when the expected number of tuples\nsatisfying each relation in \σ is linear. It is also shown that these\nlimit probabilities are well-behaved with respect to several parameters that\nrepresent the density of tuples in each relation R in the vocabulary\n\σ. An application of these results to the problem of random Boolean\nsatisfiability is presented. We show that in a random k-CNF formula on n\nvariables, where each possible clause occurs with probability \∼ c/n^k-1,\nindependently any first order property of k-CNF formulas that implies\nunsatisfiability does almost surely not hold as n tends to infinity.\n

Related

• First order complexity of finite random structures
• Limiting probabilities of first order properties of random sparse graphs\n and hypergraphs
• Random expansions of finite structures with bounded degree
• Monadic second-order properties of very sparse random graphs
• First Order Logic of Sparse Graphs with Given Degree Sequences