Böcker i Algorithms and Combinatorics-serien

This is the first comprehensive exposition of basic lower-bounds arguments, reviewing gems discovered in the past two decades right up to results from the last year. Covers a wide spectrum of models: circuits, formulas, communication protocols, branching programs.

This comprehensive textbook on combinatorial optimization emphasizes theoretical results and algorithms with provably good performance, in contrast to heuristics. The text contains complete but concise proofs, and also provides numerous exercises and references.

Over the past decade, many major advances have been made in the field of graph coloring via the probabilistic method. This monograph, by two of the best on the topic, provides an accessible and unified treatment of these results, using tools such as the Lovasz Local Lemma and Talagrand's concentration inequality.

This book offers a systematic study of sparse graphs and sparse finite structures. Although the notion of sparsity appears in various contexts and is typical of a fuzzy notion, the authors present a unifying classification of general classes of structures.

What is the "most uniform" way of distributing n points in the unit square? How big is the "irregularity" necessarily present in any such distribution? This book is an accessible and lively introduction to the area of geometric discrepancy theory.

Some of the most convincing demonstrations of the power of these tech niques are randomized algorithms for estimating quantities which are hard to compute exactly. One example is the randomized algorithm of Dyer, Frieze and Kannan for estimating the volume of a polyhedron.

One of the important areas of contemporary combinatorics is Ramsey theory. The whole subject is quickly developing and has some new and unexpected applications in areas as remote as functional analysis and theoretical computer science.