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

Abstract: 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) showed that for every first order sentence

p h i

, the limiting probability that

G_{n}

satisfies

p h i

as

n o i n f t y

exists, and moreover it is an analytic function of

c

. In this paper we consider the closure

o v e r l i n e L_{c}

in

[0, 1]

of the set

L_{c}

of all limiting probabilities of first order sentences in

G_{n}

. We show that there exists a critical value

c_{0} a p p r o x 0.93

such that

o v e r l i n e L_{c} = [0, 1]

when

c g e c_{0}

, whereas

o v e r l i n e L_{c}

misses at least one subinterval when

c < c_{0}

. We extend these results to random

d

-uniform sparse hypergraphs, where the probability of a hyperedge is given by

p = c / n^{d - 1}

.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Limiting probabilities of first order properties of random sparse graphs and hypergraphs