Random Structures and Algorithms, Volume 7

Volume 7, Number 1, August 1995

Luc Devroye, Jiang Lu: The Strong Convergence of Maximal Degrees in Uniform Random Recursive Trees and Dags. 1-14
Jan Krajícek, Pavel Pudlák, Alan R. Woods: An Exponenetioal Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle. 15-40
Alan M. Frieze, Svante Janson: Perfect Matchings in Random s-Uniform Hypergraphs. 41-58
Anil Kamath, Rajeev Motwani, Krishna V. Palem, Paul G. Spirakis: Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture. 59-80
Werner Schachinger: The Variance of Partial Match Retrieval in a Multidimensional Symmetric Trie. 81-96

Richard M. Karp, Yanjun Zhang: Bounded Branching Process AND/OR Tree Evaluation. 97-116
Philippe Flajolet, Gilbert Labelle, Louise Laforest, Bruno Salvy: Hypergeometrics and the Cost Structure of Quadtrees. 117-144
Michael Krivelevich: Bounding Ramsey Numbers through Large Deviation Inequalities. 145-156
Mark Jerrum: A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph. 157-166
Joel Spencer: Asymptotic Packing via a Branching Process. 167-172

Jeong Han Kim: The Ramsey Number R(3, t) Has Order of Magnitude t₂/log t. 173-208
Michael Molloy, Bruce A. Reed: The Dominating Number of Random Cubic Graph. 209-222
Dwight Duffus, Mark Ginn, Vojtech Rödl: On the Computational Complexity of Ordered Subgraph Recognition. 223-268
James B. Shearer: On the Independence Number of Sparse Graphs. 269-272

Edward A. Bender, L. Bruce Richmond, Nicholas C. Wormald: Largest 4-Connected Components of 3-Connected Planar Triangulations. 273-286
Catherine C. McGeoch, J. D. Tygar: Optimal Sampling Strategies for Quicksort. 287-300
Jin-yi Cai, Suresh Chari: On the Impossibility of Amplifying the Independence of Random Variables. 301-310
Svante Janson: The Minimal Spanning Tree in a Complete Graph and a Functional Limit Theorem for Trees in a Random Graph. 337-356