Skip to search
Skip to main content
Title starts with
Author (sorted by title)
Call number (browse)
Princeton University Library Catalog
Extremal Combinatorics [electronic resource] : With Applications in Computer Science / by Stasys Jukna.
1st ed. 2001.
Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2001.
1 online resource (XVII, 378 p.)
Texts in Theoretical Computer Science. An EATCS Series,
[More in this series]
Texts in Theoretical Computer Science. An EATCS Series, 1862-4499
[More in this series]
Combinatorial mathematics has been pursued since time immemorial, and at a reasonable scientific level at least since Leonhard Euler (1707-1783). It ren dered many services to both pure and applied mathematics. Then along came the prince of computer science with its many mathematical problems and needs - and it was combinatorics that best fitted the glass slipper held out. Moreover, it has been gradually more and more realized that combinatorics has all sorts of deep connections with "mainstream areas" of mathematics, such as algebra, geometry and probability. This is why combinatorics is now apart of the standard mathematics and computer science curriculum. This book is as an introduction to extremal combinatorics - a field of com binatorial mathematics which has undergone aperiod of spectacular growth in recent decades. The word "extremal" comes from the nature of problems this field deals with: if a collection of finite objects (numbers, graphs, vectors, sets, etc. ) satisfies certain restrictions, how large or how small can it be? For example, how many people can we invite to a party where among each three people there are two who know each other and two who don't know each other? An easy Ramsey-type argument shows that at most five persons can attend such a party. Or, suppose we are given a finite set of nonzero integers, and are asked to mark an as large as possible subset of them under the restriction that the sum of any two marked integers cannot be marked.
Bibliographic Level Mode of Issuance: Monograph
Includes bibliographical references and indexes.
Prolog: What This Book Is About
2. Advanced Counting
3. The Principle of Inclusion and Exclusion
4. The Pigeonhole Principle
5. Systems of Distinct Representatives
8. Intersecting Families
9. Chains and Antichains
10. Blocking Sets and the Duality
11. Density and Universality
12. Witness Sets and Isolation
14. The Basic Method
15. Orthogonality and Rank Arguments
16. Span Programs
17. Basic Tools
18. Counting Sieve
19. The Lovász Sieve
20. Linearity of Expectation
21. The Deletion Method
22. The Second Moment Method
23. The Entropy Function
24. Random Walks
25. Randomized Algorithms
27. Ramsey’s Theorem
28. Ramseyan Theorems for Numbers
29. The Hales-Jewett Theorem
Epilog: What Next?
Show 31 more Contents items
Statement on language in description
Princeton University Library aims to describe library materials in a manner that is respectful to the individuals and communities who create, use, and are represented in the collections we manage.
Ask a Question
Suggest a Correction
Report Harmful Language
Extremal combinatorics : with applications in computer science / Stasys Jukna.