



LEADER 
03624nmm a2200385 u 4500 
001 
EB000385822 
003 
EBX01000000000000000238874 
005 
00000000000000.0 
007 
cr 
008 
130626  eng 
020 


a 9783642173646

100 
1 

a Jukna, Stasys

245 
0 
0 
a Extremal Combinatorics
h Elektronische Ressource
b With Applications in Computer Science
c by Stasys Jukna

250 


a 2nd ed. 2011

260 


a Berlin, Heidelberg
b Springer Berlin Heidelberg
c 2011, 2011

300 


a XXIV, 412 p
b online resource

505 
0 

a What this Book Is About  Notation  Counting  Advanced Counting  Probabilistic Counting  The Pigeonhole Principle  Systems of Distinct Representatives  Sunflowers  Intersecting Families  Chains and Antichains  Blocking Sets and the Duality  Density and Universality  Witness Sets and Isolation  Designs  The Basic Method  Orthogonality and Rank Arguments  Eigenvalues and Graph Expansion  The Polynomial Method  Combinatorics of Codes  Linearity of Expectation  The Lovász Sieve  The Deletion Method  The Second Moment Method  The Entropy Function  Random Walks  Derandomization  Ramseyan Theorems for Numbers  The Hales–Jewett Theorem  Applications in Communications Complexity  References  Index

653 


a Theory of Computation

653 


a Number theory

653 


a Number Theory

653 


a Computational Mathematics and Numerical Analysis

653 


a Computer science / Mathematics

653 


a Information theory

653 


a Computational complexity

653 


a Combinatorics

653 


a Discrete Mathematics in Computer Science

653 


a Combinatorics

710 
2 

a SpringerLink (Online service)

041 
0 
7 
a eng
2 ISO 6392

989 


b Springer
a Springer eBooks 2005

490 
0 

a Texts in Theoretical Computer Science. An EATCS Series

856 


u https://doi.org/10.1007/9783642173646?nosfx=y
x Verlag
3 Volltext

082 
0 

a 004.0151

520 


a This book is a concise, selfcontained, uptodate 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 selfcontained 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 errorcorrecting 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 4cycles, 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 3SAT, the Szemerédi—Trotter theorem on the number of pointline incidences, surprising applications of expander graphs in extremal number theory, and some other new results
