Search

We study asymptotical probabilities of first order and monadic second order properties of Bernoulli random graph G ( n , n − a ) . The random graph obeys FO (MSO) zero-one k -law ( k is a positive integer) if, for any first order (monadic second order) formulae with quantifier depth at most k , it is true for G ( n , n − a ) with probability tending to 0 or to 1. Zero-one k -laws are well studied only for the first order language and a < 1 . We obtain new zero-one k -laws (both for first order and monadic second order languages) when a > 1 . Proofs of these results are based on the earlier studies of first order equivalence classes and our study of monadic second order equivalence classes. The respective results are of interest by themselves. [ABSTRACT FROM AUTHOR]

The presented paper is devoted to the asymptotical behavior of first-order properties of the Erdős–Rényi random graph. In previous works the zero–one k -law was proved. This law describes asymptotical behavior of first-order properties which are expressed by formulae with a quantifier depth bounded by k . The random graph G ( N , N − α ) obeys the law if α ∈ ( 0 , 1 / ( k − 2 ) ) . In this work we find new values of α , which are close to 1, such that G ( N , N − α ) obeys the zero–one k -law and, therefore, extend the previous result. [ABSTRACT FROM AUTHOR]

The Le Bars conjecture (2001) states that the binomial random graph G(n, 12) obeys the zero-one law for existential monadic sentences with two first-order variables. This conjecture is disproved. Moreover, it is proved that there exists an existential monadic sentence with a single monadic variable and two first-order variables whose truth probability does not converge. [ABSTRACT FROM AUTHOR]

We study connectivity property in the superposition of random key graph on random geometric graph. For this class of random graphs, we establish a new version of a conjectured zero-one law for graph connectivity as the number of nodes becomes unboundedly large. The results reported here strengthen recent work by the Krishnan et al. [ABSTRACT FROM AUTHOR]

We study the secure and reliable connectivity of wireless sensor networks. Security is assumed to be ensured by the random pairwise key predistribution scheme of Chan, Perrig, and Song, and unreliable wireless links are represented by independent ON/OFF channels. Modeling the network by an intersection of a random $K$ -out graph and an Erdős–Rényi graph, we present scaling conditions (on the number of nodes $n$ , the scheme parameter $K$ , and the probability $p$ of a wireless channel being on), such that the resulting graph contains no nodes with a degree less than $k$ with high probability. Results are given in the form of zero–one laws with $n$ getting large, and are shown to improve the previous results by Yağan and Makowski on the absence of isolated nodes (i.e., absence of nodes with degree zero) in the same model. Through simulations, the established zero–one laws are also shown to hold for the property of $k$ -connectivity, i.e., the property that graph remains connected despite the deletion of any $k-1$ nodes or edges. [ABSTRACT FROM PUBLISHER]

The limit probabilities of the first-order properties of a random graph in the Erdős-Rényi model G( n, n), α ∈ (0, 1], are studied. Earlier, the author obtained zero-one k-laws for any positive integer k ≥ 3, which describe the behavior of the probabilities of the first-order properties expressed by formulas of quantifier depth bounded by k for α in the interval (0, 1/( k − 2)] and k ≥ 4 in the interval (1 − 1/2, 1). This result is improved for k = 4. Moreover, it is proved that, for any k ≥ 4, the zero-one k-law does not hold at the lower boundary of the interval (1 − 1/2, 1). [ABSTRACT FROM AUTHOR]

We study zero-one laws for random distance graph with vertices in {−1, 0, 1} depending on a set of parameters. We give some conditions under which sequences of random distance graphs obey or do not obey the zero-one law. [ABSTRACT FROM AUTHOR]

We explore the scaling properties for graph connectivity in random threshold graphs. In the many node limit, we provide a complete characterization for the existence and type of the underlying zero-one laws, and identify the corresponding critical scalings. These results are consequences of well-known facts in Extreme Value Theory concerning the asymptotic behavior of running maxima on i.i.d. random variables. In the important special case of exponentially distributed fitness, we show that the (essentially unique) critical scaling which ensures a power-law degree distribution, does not result in graph connectivity in the asymptotically almost sure (a.a.s.) sense. [ABSTRACT FROM AUTHOR]

We consider a collection of n independent points which are distributed on the unit interval [0,1] according to some probability distribution function F. Two nodes communicate with each other if their distance is less than some given threshold value. When F admits a density f which is strictly positive on [0,1], we give conditions on f under which the property of graph connectivity for the induced geometric random graph obeys a very strong zero-one law when the transmission range is scaled appropriately with n large. The very strong critical threshold is identified. This is done by applying a version of the method of first and second moments. [ABSTRACT FROM AUTHOR]

A random graph G( n, p) is said to obey the (monadic) zero-one k-law if, for any monadic formula of quantifier depth k, the probability that it is true for the random graph tends to either zero or one. In this paper, following J. Spencer and S. Shelah, we consider the case p = n . It is proved that the least k for which there are infinitely many α such that a random graph does not obey the zero-one k-law is equal to 4. [ABSTRACT FROM AUTHOR]