Construction of a random sequence

A completely equidistributed sequence of real numbers is constructed explicitly.     

Enumeration of plane partitions

Using some recent results involving Young tableaux and matrices of non-negative integers [10], it is possible to enumerate various classes of plane partitions by actual construction. One of the results is a simple proof of MacMahon's [12] generating function for plane partitions. Previous results of this type [12, 4, 3, 8, 7] involved complicated algebraic methods which did not reveal any intrinsic “reason” why the corresponding generating functions have such a simple form.     

The birth of the giant component

Limiting distributions are derived for the sparse connected components that are present when a random graph on n vertices has approximately 1/2n edges. In particular, we show that such a graph consists entirely of trees, unicyclic components, and bicyclic components with probability approaching √2/3 cosh √5/18 ≈ 0.9325 as n→∞. The limiting probability that it is consists of trees, unicyclic components, and at most one another component is approximately 0.9957; the limiting probability that it is planar lies between 0.987 and 0.9998. When a random graph evolves and the number of edges passes 1/2n, its components grow in cyclic complexity according to an interesting Markov process whose asymptotic structure is derived. The probability that there never is more than a single component with more edges than vertices, throughout the veolution, approaches 5 π/18 ≈ 0.8727. A “uniform” model of random graphs, which allows self-loops and multiple edges, is shown to lead to formulas that are substanitially simpler than the analogous formulas for the classical random graphs of Erdõs and Rényi. The notions of “excess” and “deficiency,” which are significant characteristics of the generating function as well as of the graphs themselves, lead to a mathematically attractive structural theory for the uniform model. A general approach to the study of stopping configurations makes it possible to sharpen previously obtained estimates in a uniform manner and often to obtain closed forms for the constants of interest. Empirical results are presented to complement the analysis, indicating the typical behavior when n is near 2oooO. © 1993 John Wiley & Sons, Inc.     

Stable husbands

Suppose n boys and n girls rank each other at random. We show that any particular girl has at least (1/2 ? ?) in n and at most (1 + ?) in n different husbands in the set of all Gale/Shapley stable matchings defined by these rankings, with probability approaching 1 as n → ∞, if ? is any positive constant. the proof emphasizes general methods that appear to be useful for the analysis of many other combinatorial algorithms.     

Verification of link-level protocols

Stein Krogdahl [1] has given an interesting demonstration of the partial correctness of a protocol skeleton, by which the validity of the essential aspects of a large variety of data transmission schemes can be demonstrated. The purpose of this note is to present a simpler way to obtain the same results, by first establishing the validity of a less efficient skeleton and then optimizing the algorithms. The present approach, which was introduced for a particular protocol by N. V. Stenning [2], also solves a wider class of problems that do not require first-in-first-out transmissions.The preparation of this paper was supported in part by National Science Foundation grants MCS-77-23738 and IST-79-21977, and by Office of Naval Research contract N00014-76-C-0330.