Umeå University's logo

It is known that for K_n,n equipped with i.i.d. exp(1) edge costs, the minimum total cost of a perfect matching converges to π²/6 in probability. Similar convergence has been established for all edge cost distributions of pseudo-dimension q≥1, such as Weibull(1,q) costs. In this paper we extend those results all q>0, confirming the Mézard-Parisi conjecture in the last remaining applicable case.

Let V be an n-set, and let X be a random variable taking values in the powerset of V. Suppose we are given a sequence of random coupons X₁,X₂,…, where the X_i are independent random variables with distribution given by X. The covering time T is the smallest integer t≥0 such that ⋃^t_i=1X_i=V. The distribution of T is important in many applications in combinatorial probability, and has been extensively studied. However the literature has focussed almost exclusively on the case where X is assumed to be symmetric and/or uniform in some way.

In this paper we study the covering time for much more general random variables X; we give general criteria for T being sharply concentrated around its mean, precise tools to estimate that mean, as well as examples where T fails to be concentrated and when structural properties in the distribution of X allow for a very different behaviour of T relative to the symmetric/uniform case.

The basic random k‐SAT problem is: given a set of n Boolean variables, and m clauses of size k picked uniformly at random from the set of all such clauses on our variables, is the conjunction of these clauses satisfiable? Here we consider a variation of this problem where there is a bias towards variables occurring positive—that is, variables occur negated w.p. 0<p<½  and positive otherwise—and study how the satisfiability threshold depends on p. For p<½ this model breaks many of the symmetries of the original random k‐SAT problem, for example, the distribution of satisfying assignments in the Boolean cube is no longer uniform. For any fixed k, we find the asymptotics of the threshold as p approaches 0 or ½ . The former confirms earlier predictions based on numerical studies and heuristic methods from statistical physics.

We introduce a variation of the random k-SAT problem, which we call polarized random k-SAT. In polarized random k-SAT we have a polarization parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p = 1/2 we get the classical random k-SAT model.

Of particular interest is the fully polarized model where p = 0. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated.

We show that the threshold of satisfiability does not decrease as p moves away from 1. Thus the satisfiability threshold for polarized random k-SAT is an upper bound on the threshold for the classical random k-SAT. We also conjecture that the two thresholds coincide.