The Resource Extremal combinatorics : with applications in computer science, Stasys Jukna, (electronic resource)

Extremal combinatorics : with applications in computer science, Stasys Jukna, (electronic resource)

Label
Extremal combinatorics : with applications in computer science
Title
Extremal combinatorics
Title remainder
with applications in computer science
Statement of responsibility
Stasys Jukna
Creator
Contributor
Provider
Subject
Genre
Language
eng
Summary
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
Member of
Cataloging source
GW5XE
http://library.link/vocab/creatorDate
1953-
http://library.link/vocab/creatorName
Jukna, Stasys
Image bit depth
0
LC call number
QA164
LC item number
.J85 2011
Literary form
non fiction
Nature of contents
dictionaries
http://library.link/vocab/relatedWorkOrContributorName
SpringerLink
Series statement
Texts in Theoretical Computer Science. An EATCS Series,
http://library.link/vocab/subjectName
  • Combinatorial analysis
  • Extremal problems (Mathematics)
  • Computer science
  • Combinatorial analysis
  • Computer science
  • Extremal problems (Mathematics)
  • Informatique
Label
Extremal combinatorics : with applications in computer science, Stasys Jukna, (electronic resource)
Instantiates
Publication
Antecedent source
mixed
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
not applicable
Content category
text
Content type code
txt
Content type MARC source
rdacontent
Contents
Preface -- 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
Dimensions
unknown
Edition
2nd ed.
Extent
1 online resource (xxii, 411 p.)
File format
multiple file formats
Form of item
  • online
  • electronic
Isbn
9783642173646
Level of compression
uncompressed
Media category
computer
Media MARC source
rdamedia
Media type code
c
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
Stock number
978-3-642-17363-9
System control number
  • (OCoLC)756677711
  • (OCoLC)ocn756677711
Label
Extremal combinatorics : with applications in computer science, Stasys Jukna, (electronic resource)
Publication
Antecedent source
mixed
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
not applicable
Content category
text
Content type code
txt
Content type MARC source
rdacontent
Contents
Preface -- 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
Dimensions
unknown
Edition
2nd ed.
Extent
1 online resource (xxii, 411 p.)
File format
multiple file formats
Form of item
  • online
  • electronic
Isbn
9783642173646
Level of compression
uncompressed
Media category
computer
Media MARC source
rdamedia
Media type code
c
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
Stock number
978-3-642-17363-9
System control number
  • (OCoLC)756677711
  • (OCoLC)ocn756677711

Library Locations

  • African Studies LibraryBorrow it
    771 Commonwealth Avenue, 6th Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Alumni Medical LibraryBorrow it
    72 East Concord Street, Boston, MA, 02118, US
    42.336388 -71.072393
  • Astronomy LibraryBorrow it
    725 Commonwealth Avenue, 6th Floor, Boston, MA, 02445, US
    42.350259 -71.105717
  • Fineman and Pappas Law LibrariesBorrow it
    765 Commonwealth Avenue, Boston, MA, 02215, US
    42.350979 -71.107023
  • Frederick S. Pardee Management LibraryBorrow it
    595 Commonwealth Avenue, Boston, MA, 02215, US
    42.349626 -71.099547
  • Howard Gotlieb Archival Research CenterBorrow it
    771 Commonwealth Avenue, 5th Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Mugar Memorial LibraryBorrow it
    771 Commonwealth Avenue, Boston, MA, 02215, US
    42.350723 -71.108227
  • Music LibraryBorrow it
    771 Commonwealth Avenue, 2nd Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Pikering Educational Resources LibraryBorrow it
    2 Silber Way, Boston, MA, 02215, US
    42.349804 -71.101425
  • School of Theology LibraryBorrow it
    745 Commonwealth Avenue, 2nd Floor, Boston, MA, 02215, US
    42.350494 -71.107235
  • Science & Engineering LibraryBorrow it
    38 Cummington Mall, Boston, MA, 02215, US
    42.348472 -71.102257
  • Stone Science LibraryBorrow it
    675 Commonwealth Avenue, Boston, MA, 02445, US
    42.350103 -71.103784
Processing Feedback ...