Random Structures and Algorithms, Volume 2

Volume 2, Number 1, Spring 1991

Miklós Simonovits, Vera T. Sós: Szemerédi's Partition and Quasirandomness. 1-10
Vasek Chvátal: Almost All Graphs with 1.44n Edges are 3-Colorable. 11-28
Martin E. Dyer, Alan M. Frieze: Randomized Greedy Matching. 29-46
William M. Y. Goh, Eric Schmutz: A Central Limit Theorem on GL_n /F_q). 47-54
Hans Jürgen Prömel, Angelika Steger: Excluding Induced Subgraphs: Quadrilaterals. 55-72
A. F. Sidorenko: Inequalities in Probability Theory and Turán-Type Problems for Graphs with Colored Vertices. 73-100
Yu Zhang: A Power Law for Connectedness of Some Random Graphs at the Critical Point. 101-120

Nicholas Pippenger: The Blocking Probability of Spider-Web Networks. 121-150
Guy Louchard, René Schott: Probabilistic Analysis of Some Distributed Algorithms. 151-186
Michael Drmota, Peter Kirschenhofer: On Generalized Independent Subsets of Trees. 187-208
Svante Janson, Jan Kratochvíl: Proportional Graphs. 209-224
Béla Bollobás, Alan M. Frieze: Spanning Maximal Planar Subgraphs of Random Graphs. 225-232
Martin E. Dyer, Alan M. Frieze: Probabilistic Analysis of a Parallel Algorithm for Finding the Lexicographically First Depth First Search Tree in a Dense Random Graph. 233-240
Fan R. K. Chung: Regularity Lemmas for Hypergraphs and Quasi-randomness. 241-252

Paul Erdös, Henry A. Kierstead, William T. Trotter: The Dimension of Random Ordered Sets. 254-276
Noga Alon, Colin McDiarmid, Bruce A. Reed: Acyclic Coloring of Graphs. 277-288
József Beck: Quasi-Random 2-Colorings of Point Sets. 289-302
Luc Devroye: Limit Laws for Local Counters in Random Binary Search Tree. 303-316
Peter Dolan: A Zero-One Law for Random Subset. 317-326
Tomasz Luczak, Joel E. Cohen: Stability of Vertices in Random Boolean Cellular Automata. 327-334
J. van den Berg, Ronald W. J. Meester: Stability Properties of a Flow Process in Graphs. 335-342