Spaces of completions of elementary theories and convergence laws for random hypergraphs

preprint2016arXivOpen access

Abstract

Consider the binomial model Gd+1(n,p)G^{d+1}(n,p) of the random (d+1)(d+1)-uniform hypergraph on nn vertices, where each edge is present, independently of one another, with probability p:N→[0,1]p:\mathbb{N}\to[0,1]. We prove that, for all logarithmo-exponential p≪n−d+εp\ll n^{-d+ε}, the probabilities of all elementary properties of hypergraphs converge, with particular emphasis in the ranges p(n)∼C/ndp(n)\sim C/n^d and p(n)∼Clog⁡(n)/ndp(n) \sim C\log(n)/n^d. The exposition is unified by constructing, for each such function pp, the topological space of all completions of its almost sure theory. This space turns out to be compact, metrizable and totally disconnected, but further properties depend on the range of pp. The convergence of the probabilities of elementary properties is associated with a borelian probability measure on the space.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.