Convergence Laws for Extensions of First-Order Logic with Averaging

2025/04/19 by Adam-Day, Sam, Benedikt, Michael, Larrauri, Alberto · 1 citation
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2504.14270

Abstract

For many standard models of random structure, first-order logic sentences exhibit a convergence phenomenon on random inputs. The most well-known example is for random graphs with constant edge probability, where the probabilities of first-order sentences converge to 0 or 1. In other cases, such as certain ``sparse random graph'' models, the probabilities of sentences converge, although not necessarily to 0 or 1. In this work we deal with extensions of first-order logic with aggregate operators, variations of averaging. These logics will consist of real-valued terms, and we allow arbitrary Lipschitz functions to be used as ``connectives''. We show that some of the well-known convergence laws extend to this setting.

Cited by

• Domain size asymptotics for Markov logic networks

Related

• Logical convergence laws via stochastic approximation and Markov processes
• γ-variable first-order logic of uniform attachment random graphs
• γ-variable first-order logic of preferential attachment random graphs
• Failure of 0-1 law for sparse random graph in strong logics
• First Order Logic of Sparse Graphs with Given Degree Sequences