Extremal Combinatorics
With Applications in Computer Science
This is a concise, up-to-date introduction to extremal combinatorics for non-specialists. Strong emphasis is made on theorems with particularly elegant and informative proofs which may be called the gems of the theory. A wide spectrum of the most powerful...
Leider schon ausverkauft
versandkostenfrei
Buch
69.50 €
Produktdetails
Produktinformationen zu „Extremal Combinatorics “
This is a concise, up-to-date introduction to extremal combinatorics for non-specialists. Strong emphasis is made on theorems with particularly elegant and informative proofs which may be called the gems of the theory. A wide spectrum of the most powerful combinatorial tools is presented, including methods of extremal set theory, the linear algebra method, the probabilistic method and fragments of Ramsey theory. A thorough discussion of recent applications to computer science illustrates the inherent usefulness of these methods.
Klappentext zu „Extremal Combinatorics “
The book is a concise, self-contained and up-to-date introduction to extremal combinatorics for non-specialists. Strong emphasis is made on theorems with particularly elegant and informative proofs which may be called gems of the theory. A wide spectrum of most powerful combinatorial tools is presented: methods of extremal set theory, the linear algebra method, the probabilistic method and fragments of Ramsey theory. A throughout discussion of some recent applications to computer science motivates the liveliness and inherent usefulness of these methods to approach problems outside combinatorics. No special combinatorial or algebraic background is assumed. All necessary elements of linear algebra and discrete probability are introduced before their combinatorial applications. Aimed primarilrily as an introductory text for graduates, it provides also a compact source of modern extremal combinatorics for researchers in computer science and other fields of discrete mathematics.
Inhaltsverzeichnis zu „Extremal Combinatorics “
Introduction.- I. The Classis: Counting.- The Pigeon-Hole Principle.- Principle of Inclusion and Exclusion.- Systems of Distinct Representatives.- Colorings.- Chains and Antichains.- Intersecting Families.- Covers and Transversals.- Sunflowers.- Density and Universality.- Designs.- Witness Sets.- Isolation Lemmas.- II. The Linear Algebra Method: Basic Method.- The Polynomial Technique.- Monotone Span Programs.- III. The Probabilistic Method: Basic Tools.- Counting Sieve.- Lovasz Sieve.- Linearity of Expectation.- The Deletion Method.- Second Moment Method.- Bounding of Large Deviations.- Randomized Algorithms.- Derandomization.- The Entropy Function.- Random Walks and Search Problems.- IV. Fragments of Ramsey Theory: Ramsey's Theorem.- The Hales-Jewett Theorem.- Epilogue: What Next?- Bibliography.- Index.
Bibliographische Angaben
- Autor: Stasys Jukna
- 2001, XVII, 375 Seiten, Maße: 16,5 x 24,2 cm, Gebunden, Deutsch
- Verlag: Springer, Berlin
- ISBN-10: 3540663134
- ISBN-13: 9783540663133
Rezension zu „Extremal Combinatorics “
From the reviews:"This monograph deals with problems of the following type: 'If a collection of finite objects ... satisfies certain restrictions, how large or how small can it be?' The text is self-contained and assumes no special knowledge (only a standard mathematical background). Moreover, its 29 chapters - 'each devoted to a particular proof technique' - are (almost) independent. Because of this modularity, its style ... and the character of its subject, this book can also be browsed and read for (mathematical) pleasure." (P. Schmitt, Monatshefte für Mathematik, Vol. 141 (1), 2004)"The book is structured as a collection of short, largely independent chapters, each dedicated to a specific proof technique. ... The book is broad in scope and gives equal space to the classical counting techniques and to more recent methods. ... I used the book to teach a small group of graduate students. It was a rewarding experience. ... The material was interesting, diverse, and challenging. ... this is a book I heartily recommend to anyone wishing to learn or teach combinatorics." (Jeannette C. M. Janssen, SIAM Review, Vol. 26 (1), 2004)"The author has covered a huge amount of ground in this book. ... Each topic is covered in a way that takes the reader from the start right up to the most recent results in the area. ... the book is clearly a 'labour of love'. The author's enthusiasm for the subject shines through page after page: it is hard not to feel his excitement as one reads what he has written." (Imre Leader, Combinatorics, Probability and Computing, Vol. 13, 2004)"A text suitable for advanced undergraduate or graduate students. It begins with basics, inclusion-exclusion, pigeonhole, systems of distinct representatives. Substantial space is devoted to the more modern linear algebra and probabilistic methods. Algorithmic aspects permeate the book, making it suitable for a computer science, or joint math/computer science course. There are numerous exercises." (J.
... mehr
Spencer, Mathematical Reviews, Issue 2003 g)"Extremal Combinatorics is a part of finite mathematics ... . The present book collects many different aspects of the field. It is wider than deep having 29 relatively short and independent chapters. These properties make the book accessible to a broad readership. ... this volume also contains a large number of well chosen exercises of various range of difficulty. There is a useful home page edited by the author ... . We warmly recommend this well-written and nicely edited book to anybody with combinatorial interest." (János Barát, Acta Scientiarum Mathematicarum, Vol. 68, 2002)"This book presents several important parts of combinatorics with emphasis to methods for solving extremal problems. Some interesting applications in theoretical computer science are included. ... As written in the preface, the text is indeed self-contained and the chapters are almost independent. More than 300 exercises ... are included. The presentation is clear and sound. The book is not only valuable for students and teachers, but also for researchers working in discrete mathematics or theoretical computer science." (Konrad Engel, Zentralblatt MATH, Vol. 978, 2002)
... weniger
Kommentar zu "Extremal Combinatorics"
0 Gebrauchte Artikel zu „Extremal Combinatorics“
Zustand | Preis | Porto | Zahlung | Verkäufer | Rating |
---|
Schreiben Sie einen Kommentar zu "Extremal Combinatorics".
Kommentar verfassen