Random Structures and Algorithms, Volume 4

Volume 4, Number 1, Spring 1993

Samuel Karlin, Bo Lindqvist, Yi-Ching Yao: Markoc Chains on Hypercubes: Spectral Representations and Several Mahorization Relations. 1-36
Vladimir Estivill-Castro, Derick Wood: Randomized Adative Sorting. 37-58
Tamás F. Móri: How Much Homogeneous Can the Appearing Pattern Be? 59-70
Svante Janson: Multicyclic Components in a Random Graph Process. 71-84
Xin Ke: The Size Ramsey Number of Trees with Bounded Degree. 85-98
Peter J. Grabner: Searching for Losers. 99-110
Dana Randall: Efficient Generation of Random Nonsingular Matrices. 111-118
Noga Alon, Oded Goldreich, Johan Håstad, René Peralta: Addendum to "Simple Construction of Almost k-wise Independent Random Variables". 119-120

Russell Impagliazzo, Noam Nisan: The Effect of Random Restrictions on Formula Size. 121-134
Mike Paterson, Uri Zwick: Shrinkage of de Morgan Formulae under Restriction. 135-150
Hosam M. Mahmoud, Robert T. Smythe, Jerzy Szymanski: On the Structure of Random Plane-oriented Recursive Trees and Their Branches. 151-176
Robert M. Burton, Ronald W. J. Meester: Long Range Percolation in Stationary Point Processes. 177-190
Mikhail J. Atallah, Philippe Jacquet, Wojciech Szpankowski: A Probabilistic Analysis of a Pattern Matching Problem. 191-214
Alexandr V. Kostochka, Alexander A. Sapozhenko, K. Weber: Radius and Diameter of Random Subgraphs of the Hypercube. 215-230

Paul Erdös: The Giant Component 1960-1993. 231-232
Svante Janson, Donald E. Knuth, Tomasz Luczak, Boris Pittel: The Birth of the Giant Component. 233-359

László Lovász, Miklós Simonovits: Random Walks in a Convex Body and an Improved Volume Algorithm. 359-412
Graham Brightwell, Yoshiharu Kohayakawa: Ramsey Properties of Orientations of Graphs. 413-428
Peter Dolan, James F. Lynch: The Logic of Ordered Random Structures. 429-447
Walter J. Gutjahr: Expectation Transfer between Branching Processes and Random Trees. 447-468
Colin Cooper: A Note on the Connectivity of 2-Regular Digraphs. 469-472