Bøger i Algorithms and Combinatorics serien

The study of random graphs was begun by Paul Erdos and Alfred Renyi in the 1960s and now has a comprehensive literature. A compelling element has been the threshold function, a short range in which events rapidly move from almost certainly false to almost certainly true. This book now joins the study of random graphs (and other random discrete objects) with mathematical logic. The possible threshold phenomena are studied for all statements expressible in a given language. Often there is a zero-one law, that every statement holds with probability near zero or near one. The methodologies involve probability, discrete structures and logic, with an emphasis on discrete structures.The book will be of interest to graduate students and researchers in discrete mathematics.

The book makes use of this mathematical theory to develop efficient algorithms for constructing such networks, with an emphasis on exact solutions.Marcus Brazil and Martin Zachariasen focus principally on the geometric structure of optimal interconnection networks, also known as Steiner trees, in the plane.

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.

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.

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.

Written by one of the top experts in the fields of combinatorics and representation theory, this book distinguishes itself from the existing literature by its applications-oriented point of view. Recent progress in this field, in particular in design and coding theory, is described.

From the reviews: "Do you know M.Padberg's Linear Optimization and Extensions? [...] Now here is the continuation of it, discussing the solutions of all its exercises and with detailed analysis of the applications mentioned. [...] For those who strive for good exercises and case studies for LP this is an excellent volume."

Cuts and metrics are well-known objects that arise-- independently, but with many deep and fascinating connections--in diverse fields. This book presents a wealth of results, from different mathematical disciplines, in a unified comprehensive manner.

Cryptography is one of the most active areas in current mathematics research and applications. This book focuses on cryptography along with two related areas: the study of probabilistic proof systems, and the theory of computational pseudorandomness.

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.

In particular, this book contains the first systematic treatment of epsilon-nets, geometric tranversal theory, partitions of Euclidean spaces and a general method for the analysis of randomized geometric algorithms.

In the last two decades, it has become clear how important the concept is, for the following reasons: (1) Combinatorics (or discrete mathematics) was considered by many to be a collection of interesting, sometimes deep, but mostly unrelated ideas.

With contributions by numerous experts

While the "worst-case analysis" of some variants of the method shows that this is not a "good" algorithm in the usual sense of complexity theory, it seems to be useful to apply other criteria for a judgement concerning the quality of the algorithm.

Moreover, despite the success of the interior point methods for the solution of explicitly given linear programs there is still no method known that solves implicitly given linear programs, such as those described in this book, and that is both practically and theoretically efficient.

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.

With contributions by numerous experts

Recent technology involves large-scale physical or engineering systems consisting of thousands of interconnected elementary units. The structural solvability of a system of linear or nonlinear equations as well as the structural controllability of a linear time-invariant dynamical system are treated by means of graphs and matroids.

Leading experts have contributed survey and research papers in the areas of Algebraic Combinatorics, Combinatorial Number Theory, Game theory, Ramsey Theory, Graphs and Hypergraphs, Homomorphisms, Graph Colorings and Graph Embeddings.

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.

This book offers a unique introduction to matroid theory, emphasizing motivations from matrix theory and applications to systems analysis. It serves also as a comprehensive presentation of the theory and application of mixed matrices.

Leading experts have contributed survey and research papers in the areas of Algebraic Combinatorics, Combinatorial Number Theory, Game theory, Ramsey Theory, Graphs and Hypergraphs, Homomorphisms, Graph Colorings and Graph Embeddings.

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.

The study of random graphs was begun in the 1960s and now has a comprehensive literature. This excellent book by one of the top researchers in the field now joins the study of random graphs (and other random discrete objects) with mathematical logic.

In eight parts, various areas are treated, each starting with an elementary introduction to the area, with short, elegant proofs of the principal results, and each evolving to the more advanced methods and results, with full proofs of some of the deepest theorems in the area.