Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userZero-one laws for existential first order sentences of bounded quantifier depth
61
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For any fixed positive integer $k$, let $alpha_{k}$ denote the smallest $alpha in (0,1)$ such that the random graph sequence $left{Gleft(n, n^{-alpha}right)right}$ does not satisfy the zero-one law for the set $mathcal{E}_{k}$ of all existential first order sentences that are of quantifier depth at most $k$. This paper finds upper and lower bounds on $alpha_{k}$, showing that as $k rightarrow infty$, we have $alpha_{k} = left(k - 2 - t(k)right)^{-1}$ for some function $t(k) = Theta(k^{-2})$. We also establish the precise value of $alpha_{k}$ when $k = 4$.
rate research
Read More
We prove game-theoretic generalizations of some well known zero-one laws. Our proofs make the martingales behind the laws explicit, and our results illustrate how martingale arguments can have implications going beyond measure-theoretic probability.
Classical scope-assignment strategies for multi-quantifier sentences involve quantifier phrase (QP)-movement. More recent continuation-based approaches provide a compelling alternative, for they interpret QPs in situ - without resorting to Logical Forms or any structures beyond the overt syntax. The continuation-based strategies can be divided into two groups: those that locate the source of scope-ambiguity in the rules of semantic composition and those that attribute it to the lexical entries for the quantifier words. In this paper, we focus on the former operation-based approaches and the nature of the semantic operations involved. More specifically, we discuss three such possible operation-based strategies for multi-quantifier sentences, together with their relative merits and costs.
We study the critical probability for the metastable phase transition of the two-dimensional anisotropic bootstrap percolation model with $(1,2)$-neighbourhood and threshold $r = 3$. The first order asymptotics for the critical probability were recently determined by the first and second authors. Here we determine the following sharp second and third order asymptotics: [ p_cbig( [L]^2,mathcal{N}_{(1,2)},3 big) ; = ; frac{(log log L)^2}{12log L} , - , frac{log log L , log log log L}{ 3log L} + frac{left(log frac{9}{2} + 1 pm o(1) right)log log L}{6log L}. ] We note that the second and third order terms are so large that the first order asymptotics fail to approximate $p_c$ even for lattices of size well beyond $10^{10^{1000}}$.
In this paper we study first-passge percolation models on Delaunay triangulations. We show a sufficient condition to ensure that the asymptotic value of the rescaled first-passage time, called the time constant, is strictly positive and derive some upper bounds for fluctuations. Our proofs are based on renormalization ideas and on the method of bounded increments.
Markov categories are a recent category-theoretic approach to the foundations of probability and statistics. Here we develop this approach further by treating infinite products and the Kolmogorov extension theorem. This is relevant for all aspects of probability theory in which infinitely many random variables appear at a time. These infinite tensor products $bigotimes_{i in J} X_i$ come in t
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
