2016/02/21 by Nicolau C. Saldanha, Saldanha, Nicolau C., Márcio Telles +1
Mathematics · #05C65 (Secondary) #05C80 (Primary) 60C05 #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #math.CO #math.LO #msc:05C65 #msc:05C80 #msc:60C05
paper · pdf · doi:10.48550/arxiv.1602.06537
45 pages, 8 figures, substantial overlapping material with arXiv:1411.5290
arxiv created 2016/02/21 · arxiv updated 2016/02/23
Consider the binomial model Gd+1(n,p) of the random (d+1)-uniform hypergraph on n vertices, where each edge is present, independently of one another, with probability p:ℕ→[0,1]. We prove that, for all logarithmo-exponential p≪ n-d+ε, the probabilities of all elementary properties of hypergraphs converge, with particular emphasis in the ranges p(n)∼ C/nd and p(n) ∼ Clog(n)/nd. The exposition is unified by constructing, for each such function p, 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 p. The convergence of the probabilities of elementary properties is associated with a borelian probability measure on the space.