Joel Spencer - Böcker

This book develops a clear and systematic treatment of time series of data, regular and chaotic, that one finds in observations of nonlinear systems. The reader is led from measurements of one or more variables through the steps of building models of the source as a dynamical system, classifying the source by its dynamical characteristics, and finally predicting and controlling the dynamical system. The text examines methods for separating the signal of physical interest from contamination by unwanted noise, and for investigating the phase space of the chaotic signal and its properties. The emphasis throughout is on the use of the modern mathematical tools for investigating chaotic behavior to uncover properties of physical systems. The methods require knowledge of dynamical systems at the advanced undergraduate level and some knowledge of Fourier transforms and other signal processing methods.The toolkit developed in the book will provide the reader with efficient and effective methods for analyzing signals from nonlinear sources; these methods are applicable to problems of control, communication, and prediction in a wide variety of systems encountered in physics, chemistry, biology, and geophysics.

This update of the 1987 title of the same name is an examination of what is currently known about the probabilistic method, written by one of its principal developers. Based on the notes from Spencer's 1986 series of ten lectures, this new edition contains an additional lecture: The Janson Inequalities. These inequalities allow accurate approximation of extremely small probabilities. A new algorithmic approach to the Lovász Local Lemma, attributed to Jozsef Beck, has been added to Lecture 8, as well.Throughout the monograph, Spencer retains the informal style of his original lecture notes and emphasizes the methodology, shunning the more technical ""best possible"" results in favour of clearer exposition. The book is not encyclopaedic - it contains only those examples that clearly display the methodology.The probabilistic method is a powerful tool in graph theory, combinatorics, and theoretical computer science. It allows one to prove the existence of objects with certain properties (e.g., colourings) by showing that an appropriately defined random object has positive probability of having those properties.Spencer retains the informal style of his original lecture notes and emphasizes the methodology, shunning the more technical ""best possible"" results in favor of clearer exposition. Topics include: A description via examples of the basic Probabilistic Method and its refinements; Random Graphs; The Lovasz Local Lemma and its recent algorithmic implementations; Discrepancy; Derandomization; Large Deviation Estimates; Martingales; and the recent Janson Inequalities.

Discrete probability theory and the theory of algorithms have become close partners over the last ten years, though the roots of this partnership go back much longer. The papers in this volume address the latest developments in this active field. They are from the IMA Workshops "Probability and Algorithms" and "The Finite Markov Chain Renaissance." They represent the current thinking of many of the world's leading experts in the field.Researchers and graduate students in probability, computer science, combinatorics, and optimization theory will all be interested in this collection of articles. The techniques developed and surveyed in this volume are still undergoing rapid development, and many of the articles of the collection offer an expositionally pleasant entree into a research area of growing importance.

Asymptotics in one form or another are part of the landscape for every mathematician. The objective of this book is to present the ideas of how to approach asymptotic problems that arise in discrete mathematics, analysis of algorithms, and number theory. A broad range of topics is covered, including distribution of prime integers, Erdős Magic, random graphs, Ramsey numbers, and asymptotic geometry.The author is a disciple of Paul Erdős, who taught him about Asymptopia. Primes less than n , graphs with v vertices, random walks of t steps - Erdős was fascinated by the limiting behavior as the variables approached, but never reached, infinity. Asymptotics is very much an art. The various functions nlnn , n 2 , lnn n , lnn ? ? ? ? , 1 nlnn all have distinct personalities. Erdős knew these functions as personal friends. It is the author's hope that these insights may be passed on, that the reader may similarly feel which function has the right temperament for a given task. This book is aimed at strong undergraduates, though it is also suitable for particularly good high school students or for graduates wanting to learn some basic techniques.Asymptopia is a beautiful world. Enjoy!

This book gives a broad overview of core topics of finite model theory: expressive power, descriptive complexity, and zero-one laws, together with selected applications to database theory and artificial intelligence, especially constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, which emphasizes the continuity in spirit and technique with finite model theory. This underlying spirit involves the use of various fragments of, and hierarchies within, first order, second order, fixed point, and infinitary logics to gain insight into phenomena in complexity theory and combinatorics. Students of logic and computer science will find here the tools necessary to embark on research in finite model theory, and all readers will experience the excitement of a vibrant area of application of logic to computer science.

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.

CONTENTS: D.D. Dawson: Measure-valued Markov Processes.- B. Maisonneuve: Processus de Markov: Naissance, Retournement, Regeneration.- J. Spencer: Nine lectures on Random Graphs

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.