000 04549nam a22005895i 4500
001 978-3-642-17364-6
003 DE-He213
005 20221102211609.0
007 cr nn 008mamaa
008 110831s2011 gw | s |||| 0|eng d
020 _a9783642173646
_9978-3-642-17364-6
024 7 _a10.1007/978-3-642-17364-6
_2doi
050 4 _aQA75.5-76.95
072 7 _aUYA
_2bicssc
072 7 _aCOM014000
_2bisacsh
072 7 _aUYA
_2thema
082 0 4 _a004.0151
_223
100 1 _aJukna, Stasys.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_966782
245 1 0 _aExtremal Combinatorics
_h[electronic resource] :
_bWith Applications in Computer Science /
_cby Stasys Jukna.
250 _a2nd ed. 2011.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2011.
300 _aXXIV, 412 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTexts in Theoretical Computer Science. An EATCS Series,
_x1862-4502
505 0 _aPreface -- Prolog: 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.
520 _aThis 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.
650 0 _aComputer science.
_99832
650 0 _aNumber theory.
_913208
650 0 _aComputer science—Mathematics.
_931682
650 0 _aDiscrete mathematics.
_912873
650 0 _aMathematics—Data processing.
_931594
650 1 4 _aTheory of Computation.
_966783
650 2 4 _aNumber Theory.
_913208
650 2 4 _aDiscrete Mathematics in Computer Science.
_931837
650 2 4 _aDiscrete Mathematics.
_912873
650 2 4 _aComputational Mathematics and Numerical Analysis.
_931598
710 2 _aSpringerLink (Online service)
_966784
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783642269905
776 0 8 _iPrinted edition:
_z9783642173639
776 0 8 _iPrinted edition:
_z9783642173653
830 0 _aTexts in Theoretical Computer Science. An EATCS Series,
_x1862-4502
_966785
856 4 0 _uhttps://doi.org/10.1007/978-3-642-17364-6
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
942 _cETB
999 _c81722
_d81722