Extremal Combinatorics : With Applications in Computer Science,9783540663133

Extremal Combinatorics : With Applications in Computer Science

by
ISBN13: 9783540663133
ISBN10: 3540663134
Format: Hardcover
Pub. Date: 2001-07-01
Publisher(s): Springer Verlag
List Price: $94.45

Rent Textbook

Select for Price
Add to Cart
There was a problem. Please try again later.

Digital

Rent Digital Options
Online:30 Days access
Downloadable:30 Days
$32.04
Online:60 Days access
Downloadable:60 Days
$42.72
Online:90 Days access
Downloadable:90 Days
$53.40
Online:120 Days access
Downloadable:120 Days
$64.08
Online:180 Days access
Downloadable:180 Days
$69.42
Online:1825 Days access
Downloadable:Lifetime Access
$106.80
*To support the delivery of the digital material to you, a non-refundable digital delivery fee of $3.99 will be charged on each digital item.
$69.42*
Add to Cart

New Textbook

We're Sorry
Sold Out

Used Textbook

We're Sorry
Sold Out

Buy from our Marketplace starting at $179.81

How Marketplace Works:

  • This item is offered by an independent seller and not shipped from our warehouse
  • Item details like edition and cover design may differ from our description; see seller's comments before ordering.
  • Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
  • Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
  • Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.

Summary

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.

Table of Contents

Preface vii
Prolog: What This Book is About 1(4)
Notation 5(6)
Part I. The Classics
Counting
11(12)
The binomial theorem
11(2)
Selection with repetitions
13(1)
Partitions
14(1)
Double counting
14(2)
The averaging principle
16(7)
Exercises
19(4)
Advanced Counting
23(9)
Bounds on intersection size
23(2)
Zarankiewicz's problem
25(2)
Density of 0--1 matrices
27(5)
Exercises
29(3)
The Principle of Inclusion and Exclusion
32(5)
The principle
32(2)
The number of derangements
34(3)
Exercises
35(2)
The Pigeonhole Principle
37(18)
Some quickies
37(1)
The Erdos-Szekeres theorem
38(2)
Mantel's theorem
40(1)
Turan's theorem
41(1)
Dirichlet's theorem
42(1)
Swell-colored graphs
43(2)
The weight shifting argument
45(2)
Pigeonhole and resolution
47(8)
Resolution refutation proofs
47(1)
Haken's lower bound
48(3)
Exercises
51(4)
Systems of Distinct Representatives
55(10)
The marriage theorem
55(2)
Two applications
57(2)
Latin rectangles
57(1)
Decomposition of doubly stochastic matrices
58(1)
Min-max theorems
59(1)
Matchings in bipartite graphs
60(5)
Exercises
63(2)
Colorings
65(14)
Property B
65(2)
The averaging argument
67(4)
Almost good colorings
67(1)
The number of mixed triangles
68(3)
Coloring the cube: the algorithmic aspect
71(8)
Exercises
73(6)
Part II. Extremal Set Theory
Sunflowers
79(10)
The sunflower lemma
79(2)
Modifications
81(2)
Relaxed core
81(1)
Relaxed disjointness
82(1)
Applications
83(6)
The number of minterms
83(1)
Small depth formulas
84(2)
Exercises
86(3)
Intersecting Families
89(8)
The Erdos-Ko-Rado theorem
89(1)
Finite ultrafilters
90(1)
Maximal intersecting families
91(2)
A Helly-type result
93(1)
Intersecting systems
93(4)
Exercises
95(2)
Chains and Antichains
97(12)
Decomposition of posets
97(4)
Symmetric chains
99(1)
Application: the memory allocation problem
100(1)
Antichains
101(8)
Sperner's theorem
101(1)
Bollobas's theorem
102(3)
Strong systems of distinct representatives
105(1)
Union-free families
106(1)
Exercises
107(2)
Blocking Sets and the Duality
109(24)
Duality
109(2)
The blocking number
111(1)
Generalized Helly theorems
112(2)
Decision trees
114(3)
Depth versus certificate complexity
115(1)
Block sensitivity
116(1)
The switching lemma
117(4)
Monotone circuits
121(12)
The lower bounds criterion
122(3)
Explicit lower bounds
125(5)
Exercises
130(3)
Density and Universality
133(10)
Dense sets
133(1)
Hereditary sets
134(2)
Universal sets
136(4)
Isolated neighbor condition
137(1)
Paley graphs
138(2)
Full graphs
140(3)
Exercises
141(2)
Witness Sets and Isolation
143(10)
Bondy's theorem
143(1)
Average witnesses
144(3)
The isolation lemma
147(3)
Isolation in politics: the dictator paradox
150(3)
Exercises
152(1)
Designs
153(16)
Regularity
153(2)
Finite linear spaces
155(1)
Difference sets
156(1)
Projective planes
157(4)
The construction
158(1)
Bruen's theorem
159(2)
Resolvable designs
161(8)
Affine planes
162(1)
Blocking sets in affine planes
163(2)
Exercises
165(4)
Part III. The Linear Algebra Method
The Basic Method
169(22)
The linear algebra background
169(3)
Spaces of incidence vectors
172(4)
Fisher's inequality
172(1)
Inclusion matrices
173(2)
Disjointness matrices
175(1)
Spaces of polynomials
176(5)
Two-distance sets
177(1)
Sets with few intersection sizes
178(1)
Constructive Ramsey graphs
179(1)
Bollobas theorem - another proof
180(1)
Combinatorics of linear spaces
181(3)
Universal sets from linear codes
182(1)
Short linear combinations
182(2)
The flipping cards game
184(7)
Exercises
186(5)
Orthogonality and Rank Arguments
191(14)
Orthogonality
191(5)
Orthogonal coding
191(1)
A bribery party
192(2)
Hadamard matrices
194(2)
Rank arguments
196(9)
Balanced families
196(1)
Lower bounds for boolean formulas
197(6)
Exercises
203(2)
Span Programs
205(16)
The model
205(1)
Span programs and switching networks
206(1)
Monotone span programs
206(6)
Threshold functions
207(1)
Non-bipartite graphs
208(1)
Odd factors
208(3)
A lower bound for threshold functions
211(1)
A general lower bound
212(2)
Explicit self-avoiding families
214(7)
Exercises
216(5)
Part IV. The Probabilistic Method
Basic Tools
221(8)
Probabilistic preliminaries
221(3)
Elementary tools
224(1)
Advanced tools
225(4)
Exercises
227(2)
Counting Sieve
229(8)
Ramsey numbers
229(1)
Van der Waerden's theorem
230(1)
Tournaments
231(1)
Property B revised
231(1)
The existence of small universal sets
232(1)
Cross-intersecting families
233(4)
Exercises
236(1)
The Lovasz Sieve
237(8)
The local lemma
237(2)
Counting sieve for almost independence
239(1)
Applications
240(5)
Colorings
240(3)
Hashing functions
243(1)
Exercises
244(1)
Linearity of Expectation
245(18)
Hamilton paths in tournaments
245(1)
Sum-free sets
246(1)
Dominating sets
247(1)
The independence number
247(1)
Low degree polynomials
248(2)
Maximum satisfiability
250(1)
Hashing functions
251(2)
Submodular complexity measures
253(3)
Discrepancy
256(7)
Example: matrix multiplication
259(1)
Exercises
260(3)
The Deletion Method
263(10)
Ramsey numbers
263(1)
Independent sets
264(1)
Coloring large-girth graphs
265(1)
Point sets without obtuse triangles
266(2)
Covering designs
268(1)
Affine cubes of integers
269(4)
Exercises
272(1)
The Second Moment Method
273(6)
The method
273(1)
Separators
274(2)
Threshold for cliques
276(3)
Exercises
278(1)
The Entropy Function
279(7)
Basic properties
279(1)
Subadditivity
280(2)
Combinatorial applications
282(4)
Exercises
285(1)
Random Walks
286(13)
Satisfying assignments for 2-CNF
286(2)
The best bet for simpletons
288(2)
Small formulas for complicated functions
290(4)
Random walks and search problems
294(5)
Long words over a small alphabet
295(1)
Short words over a large alphabet
296(2)
Exercises
298(1)
Randomized Algorithms
299(8)
Zeroes of multivariate polynomials
299(3)
Verifying the equality of long strings
302(1)
The equivalence of branching programs
302(2)
A min-cut algorithm
304(3)
Exercises
306(1)
Derandomization
307(14)
The method of conditional probabilities
307(5)
A general frame
308(1)
Splitting graphs
309(1)
Maximum satisfiability: the algorithmic aspect
310(2)
The method of small sample spaces
312(4)
Sum-free sets: the algorithmic aspect
316(5)
Exercises
317(4)
Part V. Fragments of Ramsey Theory
Ramsey's Theorem
321(8)
Colorings and Ramsey numbers
321(1)
Ramsey's theorem for graphs
322(2)
Ramsey's theorem for sets
324(2)
Schur's theorem
326(1)
Geometric application: convex polygons
327(2)
Exercises
327(2)
Ramseyan Theorems for Numbers
329(8)
Sum-free sets
329(3)
Zero-sum sets
332(2)
Szemeredi's cube lemma
334(3)
Exercises
336(1)
The Hales---Jewett Theorem
337(14)
The theorem and its consequences
337(3)
Van der Waerden's theorem
338(1)
Gallai---Witt's Theorem
339(1)
Shelah's proof of HJT
340(3)
Application: multi-party games
343(8)
Few players: the hyperplane problem
344(4)
Many players: the matrix product problem
348(1)
Exercises
349(2)
Epilog: What Next? 351(2)
References 353(14)
Name Index 367(4)
Subject Index 371

An electronic version of this book is available through VitalSource.

This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.

By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.

Digital License

You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.

More details can be found here.

A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.

Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.

Please view the compatibility matrix prior to purchase.