Lázaro Alberto Larrauri

collaborators

Showing math.COShow all

2 papers · 1 filter

math.CO2020

Limiting probabilities of first order properties of random sparse graphs and hypergraphs

Alberto Larrauri, Tobias Müller, Marc Noy

Let $G_{n}$ be the binomial random graph $G (n, p = c / n)$ in the sparse regime, which as is well-known undergoes a phase transition at $c = 1$ . Lynch (Random Structures Algorithms, 1992) s…

math.CO2020

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

Lázaro Alberto Larrauri

We extend the convergence law for sparse random graphs proven by Lynch to arbitrary relational languages. We consider a finite relational vocabulary $σ$ and a first order theory $T…