Extremal Combinatorics: With Applications in Computer Science [Hardcover]

Stasys Jukna (Author)

Book Description

ISBN-10: 3540663134 | ISBN-13: 978-3540663133 | Publication Date: June 27, 2001 | Edition: 1

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.

Editorial Reviews

Review

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. 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)

From the Back Cover

This book is a concise, self-contained, up-to-date introduction to extremal combinatorics for nonspecialists. There is a strong emphasis on theorems with particularly elegant and informative proofs, they may be called gems of the theory. The author presents a wide spectrum of the most powerful combinatorial tools together with impressive applications in computer science: methods of extremal set theory, the linear algebra method, the probabilistic method, and fragments of Ramsey theory. No special knowledge in combinatorics or computer science is assumed – the text is self-contained and the proofs can be enjoyed by undergraduate students in mathematics and computer science. Over 300 exercises of varying difficulty, and hints to their solution, complete the text. This second edition has been extended with substantial new material, and has been revised and updated throughout. It offers three new chapters on expander graphs and eigenvalues, the polynomial method and error-correcting codes. Most of the remaining chapters also include new material, such as the Kruskal—Katona theorem on shadows, the Lovász—Stein theorem on coverings, large cliques in dense graphs without induced 4-cycles, a new lower bounds argument for monotone formulas, Dvir's solution of the finite field Kakeya conjecture, Moser's algorithmic version of the Lovász Local Lemma, Schöning's algorithm for 3-SAT, the Szemerédi—Trotter theorem on the number of point-line incidences, surprising applications of expander graphs in extremal number theory, and some other new results. --This text refers to an alternate Hardcover edition.

See all Editorial Reviews

Product Details

• Hardcover: 392 pages
• Publisher: Springer; 1 edition (June 27, 2001)
• Language: English
• ISBN-10: 3540663134
• ISBN-13: 978-3540663133
• Product Dimensions: 9.5 x 6.3 x 1.1 inches
• Shipping Weight: 1.6 pounds (View shipping rates and policies)
• Average Customer Review: 4.0 out of 5 stars  See all reviews (1 customer review)
• Amazon Best Sellers Rank: #695,916 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

3 of 3 people found the following review helpful:

4.0 out of 5 stars Polya Lives, December 31, 2010

By 

John Scott "Bounty Coder" (Dallas, Texas) - See all my reviews
(REAL NAME)   

Amazon Verified Purchase

This review is from: Extremal Combinatorics: With Applications in Computer Science (Hardcover)

A collection of gems from the field of extremal combinatorics, written in the informal but thorough style of George Polya. I very much enjoy browsing this book, especially at night, when I 'm looking for a digestible morsel to chew on before falling asleep. Like Polya, his writing style is both upbeat, lean and enthusiastic. The author doesn't dwell too much on any single problem and covers a lot ground for a single book, using concrete problems to illustrate a particular subject. The book reads as if the author is speaking directly to you.

I am professional programmer with a math background who very much recommends this book to a programmer looking to get a feel for the subject of combinatorics from a more than introductory point of view. I would have given 5 stars, but the editing is sloppy. Also, don't expect to start cutting code tomorrow. The book is much more a math book than computer science book.