From social networks such as Facebook, the World Wide Web and the Internet, to the
complex interactions between proteins in the cells of our bodies, we constantly face the …

Although the theory of random graphs is one of the youngest branches of graph theory, in
importance it is second to none. It began with some sporadic papers of Erdős in the 1940s …

In this introductory section we first present a simple version of a bounded differences
inequality which does not require us to introduce any concepts like martingales. We then …

Randomized algorithms have become a central part of the algorithms curriculum based on
their increasingly widespread use in modern applications. This book presents a coherent …

Upper bounds on probabilities of large deviations for sums of bounded independent random
variables may be extended to handle functions which depend in a limited way on a number …

Watts and Strogatz, with the publication in 1998 of their seminal paper on small-world
networks, opened the golden era of complex networks studies and showed in particular how …

This survey describes a general approach to a class of problems that arise in combinatorial
probability and combinatorial optimization. Formally, the method is part of weak …

Random graphs have proven to be one of the most important and fruitful concepts in modern
Combinatorics and Theoretical Computer Science. Besides being a fascinating study …

Consider a complete graph G=(V, E) in which each node is present with probability p. We
are interested in solving combinatorial optimization problems on subsets of nodes which are …

The random assignment (or bipartite matching) problem asks about An= minπ∑ c (i, π (i)),
where (c (i, j)) is an× n matrix with iid entries, say with exponential (1) distribution, and the …