The unsatisfiability threshold revisited

The problem of determining the unsatisfiability threshold for random 3-SAT formulas consists in determining the clause to variable ratio that marks the experimentally observed abrupt change from almost surely satisfiable formulas to almost surely unsatisfiable. Up to now, there have been rigorously established increasingly better lower and upper bounds to the actual threshold value. In this paper, we consider the problem of bounding the threshold value from above using methods that, we believe, are of interest on their own right. More specifically, we show how the method of local maximum satisfying truth assignments can be combined with results for the occupancy problem in schemes of random allocation of balls into bins in order to achieve an upper bound for the unsatisfiability threshold less than 4.571. In order to obtain this value, we establish a bound on the q-binomial coefficients (a generalization of the binomial coefficients). No such bound was previously known, despite the extensive literature on q-binomial coefficients. Finally, to prove our result we had to establish certain relations among the conditional probabilities of an event in various probabilistic models for random formulas. It turned out that these relations were considerably harder to prove than the corresponding ones for unconditional probabilities, which were previously known.     

On Asymptotics for the Signless Noncentral q-Stirling Numbers of the First Kind

In this paper, we derive asymptotic formulas for the signless noncentral q -Stirling numbers of the first kind and for the corresponding series. The signless noncentral q -Stirling numbers of the first kind appear as coefficients of a polynomial of q -number [ t ] _q , expressing the noncentral ascending q -factorial of t of order m and noncentrality parameter k . In this paper, we have two main purposes. The first is to give an expression by which we obtain the asymptotic behavior of these coefficients, using the saddle point method . The second main purpose is to derive an asymptotic expression for the signless noncentral q -Stirling of the first kind series by using the singularity analysis method. We then apply our first formula to provide asymptotic expressions for probability functions of the number of successes in m trials and of the number of trials until the occurrence of the n th success in sequences of Bernoulli trials with varying success probability which are both written in terms of the signless noncentral q -Stirling numbers of the first kind. In addition, we present some numerical calculations using the computer program MAPLE indicating that our expressions are close to the actual values of the signless noncentral q -Stirling numbers of the first kind and of the corresponding series even for moderate values of m .     

Upper Bounds and Asymptotics for the q-Binomial Coefficients

In this article, we a derive an upper bound and an asymptotic formula for the q -binomial, or Gaussian, coefficients. The q -binomial coefficients, that are defined by the expression are a generalization of the binomial coefficients, to which they reduce as q tends toward 1. In this article, we give an expression that captures the asymptotic behavior of these coefficients using the saddle point method and compare it with an upper bound for them that we derive using elementary means. We then consider as a case study the case q =1+ z / m , z <0, that was actually encountered by the authors before in an application stemming from probability and complexity theory. We show that, in this case, the asymptotic expression and the expression for the upper bound differ only in a polynomial factor; whereas, the exponential factors are the same for both expressions. In addition, we present some numerical calculations using MAPLE (a computer program for performing symbolic and numerical computations), that show that both expressions are close to the actual value of the coefficients, even for moderate values of m .     

q-Random Walks on Zd,d = 1, 2, 3

Methodology and Computing in Applied Probability - In this work, we consider nearest neighbour q-random walks on Zd for d = 1,2,3, with transition probabilities q-varying by the number of...     

A q-Analogue of the Stirling Formula and a Continuous Limiting Behaviour of the q-Binomial Distribution—Numerical Calculations

In this article, we derive an asymptotic formula for the q-factorial number of order n using the saddle point method. This formula is a q-analogue, for 0?<?q?<?1, of the usual Stirling formula for the factorial number of order n. Also, this formula is used to provide a continuous limiting behaviour of the q-Binomial distribution in the sense of pointwise convergence. Specifically, the q-Binomial distribution converges to a continuous Stieltjes–Wigert distribution. Furthermore, we present some numerical calculations, using the computer program MAPLE, indicating a quite strong convergence.