logo资料库

extremal combinatorics with applications in computer science.pdf

发布时间：2022-06-01 发布人：admin 分类：说明书 资料大小：5.56M 资料格式：pdf 举报 版权申诉
第1页 / 共431页
第2页 / 共431页
第3页 / 共431页
第4页 / 共431页
第5页 / 共431页
第6页 / 共431页
第7页 / 共431页
第8页 / 共431页
资料共431页，剩余部分请下载后查看
    Cover Page
    Texts in Theoretical Computer Science
    Title: Extremal Combinatorics With Applications in Computer Science, Second Edition
    ISBN 9783642173639
    Preface
    Preface to the First Edition
    Preface to the Second Edition
    Notation
    Contents
    Notation
    Part I The Classics
    1 Counting.
    2 AdvancedCounting.
    3 Probabilistic Counting
    4 The Pigeonhole Principle
    5 Systems of Distinct Representatives
    Part II Extremal Set Theory
    6 Sunflowers
    7 Intersecting Families
    8 Chains and Antichains
    9 Blocking Sets and the Duality
    10 Density and Universality
    11 Witness Sets and Isolation
    12 Designs
    Part III The Linear Algebra Method
    13 The Basic Method
    14 Orthogonality and Rank Arguments
    15 Eigenvalues and Graph Expansion
    16 The Polynomial Method
    17 Combinatorics of Codes
    Part IV The Probabilistic Method
    18 Linearity of Expectation
    19 The Lovász Sieve
    20 The Deletion Method
    21 The Second Moment Method
    22 The Entropy Function
    23 Random Walks
    24 Derandomization
    Part V Fragments of Ramsey Theory
    25 Ramseyan Theorems for Numbers
    26 The Hales–Jewett Theorem
    27 Applications in Communication Complexity
    References
    Index
    Part I The Classics
    1. Counting
    1.1 The binomial theorem
    1.2 Selection with repetitions
    1.3 Partitions
    1.4 Double counting
    1.5 The averaging principle
    1.6 The inclusion-exclusion principle
    Exercises
    2. Advanced Counting
    2.1 Bounds on intersection size
    2.2 Graphs with no 4-cycles
    2.3 Graphs with no induced 4-cycles
    2.4 Zarankiewicz’s problem
    2.5 Density of 0-1 matrices
    2.6 The Lovász–Stein theorem
    Exercises
    3. Probabilistic Counting
    3.1 Probabilistic preliminaries
    3.2 Tournaments
    3.3 Universal sets
    3.4 Covering by bipartite cliques
    3.5 2-colorable families
    3.6 The choice number of graphs
    Exercises
    4. The Pigeonhole Principle
    4.1 Some quickies
    4.2 The Erdős–Szekeres theorem
    4.3 Mantel’s theorem
    4.4 Turán’s theorem
    4.5 Dirichlet’s theorem
    4.6 Swell-colored graphs
    4.7 The weight shifting argument
    4.8 Schur’s theorem
    4.9 Ramseyan theorems for graphs
    4.10 Ramsey’s theorem for sets
    Exercises
    5. Systems of Distinct Representatives
    5.1 The marriage theorem
    5.2 Two applications
    5.3 Min–max theorems
    5.4 Matchings in bipartite graphs
    Exercises
    Part II Extremal Set Theory
    6. Sunflowers
    6.1 The sunflower lemma
    6.2 Modifications
    6.3 Applications
    Exercises
    7. Intersecting Families
    7.1 Ultrafilters and Helly property
    7.2 The Erdős–Ko–Rado theorem
    7.3 Fisher’s inequality
    7.4 Maximal intersecting families
    7.5 Cross-intersecting families
    Exercises
    8. Chains and Antichains
    8.1 Decomposition in chains and antichains
    8.2 Application: the memory allocation problem
    8.3 Sperner’s theorem
    8.4 The Bollobás theorem
    8.5 Strong systems of distinct representatives
    8.6 Union-free families
    Exercises
    9. Blocking Sets and the Duality
    9.1 Duality
    9.2 The blocking number
    9.3 Helly-type theorems
    9.4 Blocking sets and decision trees
    9.5 Blocking sets and monotone circuits
    Exercises
    10. Density and Universality
    10.1 Dense sets
    10.2 Hereditary sets
    10.3 Matroids and approximation
    10.4 The Kruskal–Katona theorem
    10.5 Universal sets
    10.6 Paley graphs
    10.7 Full graphs
    Exercises
    11. Witness Sets and Isolation
    11.1 Bondy’s theorem
    11.2 Average witnesses
    11.3 The isolation lemma
    11.4 Isolation in politics: the dictator paradox
    Exercises
    12. Designs
    12.1 Regularity
    12.2 Finite linear spaces
    12.3 Difference sets
    12.4 Projective planes
    12.5 Resolvable designs
    Exercises
    Part III The Linear Algebra Method
    13. The Basic Method
    13.1 The linear algebra background
    13.2 Graph decompositions
    13.3 Inclusion matrices
    13.4 Disjointness matrices
    13.5 Two-distance sets
    13.6 Sets with few intersection sizes
    13.7 Constructive Ramsey graphs
    13.8 Zero-patterns of polynomials
    Exercises
    14. Orthogonality and Rank Arguments
    14.1 Orthogonal coding
    14.2 Balanced pairs
    14.3 Hadamard matrices
    14.4 Matrix rank and Ramsey graphs
    14.5 Lower bounds for boolean formulas
    Exercises
    15. Eigenvalues and Graph Expansion
    15.1 Expander graphs
    15.2 Spectral gap and the expansion
    15.3 Expanders and derandomization
    Exercises
    16. The Polynomial Method
    16.1 DeMillo–Lipton–Schwartz–Zippel lemma
    16.2 Solution of Kakeya’s problem in finite fields
    16.3 Combinatorial Nullstellensatz
    Exercises
    17. Combinatorics of Codes
    17.1 Error-correcting codes
    17.2 Bounds on code size
    17.3 Linear codes
    17.4 Universal sets from linear codes
    17.5 Spanning diameter
    17.6 Expander codes
    17.7 Expansion of random graphs
    Exercises
    Part IV The Probabilistic Method
    18. Linearity of Expectation
    18.1 Hamilton paths in tournaments
    18.2 Sum-free sets
    18.3 Dominating sets
    18.4 The independence number
    18.5 Crossings and incidences
    18.6 Far away strings
    18.7 Low degree polynomials
    18.8 Maximum satisfiability
    18.9 Hash functions
    18.10 Discrepancy
    18.11 Large deviation inequalities
    Exercises
    19. The Lovász Sieve
    19.1 The Lovász Local Lemma
    19.2 Disjoint cycles
    19.3 Colorings
    19.4 The k-SAT problem
    Exercises
    20. The Deletion Method
    20.1 Edge clique covering
    20.2 Independent sets
    20.3 Coloring large-girth graphs
    20.4 Point sets without obtuse triangles
    20.5 Affine cubes of integers
    Exercises
    21. The Second Moment Method
    21.1 The method
    21.2 Distinct sums
    21.3 Prime factors
    21.4 Separators
    21.5 Threshold for cliques
    Exercises
    22. The Entropy Function
    22.1 Quantifying information
    22.2 Limits to data compression
    22.3 Shannon entropy
    22.4 Subadditivity
    22.5 Combinatorial applications
    Exercises
    23. Random Walks
    23.1 The satisfiability problem
    23.2 Random walks in linear spaces
    23.3 Random walks and derandomization
    Exercises
    24. Derandomization
    24.1 The method of conditional probabilities
    24.2 The method of small sample spaces
    24.3 Sum-free sets: the algorithmic aspect
    Exercises
    Part V Fragments of Ramsey Theory
    25. Ramseyan Theorems for Numbers
    25.1 Arithmetic progressions
    25.2 Szemerédi’s cube lemma
    25.3 Sum-free sets
    25.4 Sum-product sets
    Exercises
    26. The Hales–Jewett Theorem
    26.1 The theorem and its consequences
    26.2 Shelah’s proof of HJT
    Exercises
    27. Applications in Communication Complexity
    27.1 Multi-party communication
    27.2 The hyperplane problem
    27.3 The partition problem
    27.4 Lower bounds via discrepancy
    27.5 Making non-disjoint coverings disjoint
    Exercises
    References
    Index
    Symbols
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    M
    N
    O
    P
    Q
    R
    S
    T
    U
    V
    W
    Z
    Texts in Theoretical Computer Science An EATCS Series Editors: J. Hromkoviˇc G. Rozenberg A. Salomaa Founding Editors: W. Brauer G. Rozenberg A. Salomaa On behalf of the European Association for Theoretical Computer Science (EATCS) Advisory Board: G. Ausiello M. Broy C.S. Calude A. Condon D. Harel M. Nivat C. Papadimitriou D. Scott J. Hartmanis T. Henzinger T. Leighton For further volumes: www.springer.com/series/3214
    Stasys Jukna Extremal Combinatorics With Applications in Computer Science Second Edition
    Prof. Dr. Stasys Jukna Goethe Universität Frankfurt Institut für Informatik Robert-Mayer Str. 11-15 60054 Frankfurt am Main Germany jukna@thi.informatik.uni-frankfurt.de Vilnius University Institute of Mathematics and Informatics Akademijos 4 08663 Vilnius Lithuania Series Editors Prof. Dr. Juraj Hromkoviˇc ETH Zentrum Department of Computer Science Swiss Federal Institute of Technology 8092 Zürich, Switzerland juraj.hromkovic@inf.ethz.ch Prof. Dr. Arto Salomaa Turku Centre of Computer Science Lemminkäisenkatu 14 A 20520 Turku, Finland asalomaa@utu.fi Prof. Dr. Grzegorz Rozenberg Leiden Institute of Advanced Computer Science University of Leiden Niels Bohrweg 1 2333 CA Leiden, The Netherlands rozenber@liacs.nl ISSN 1862-4499 ISBN 978-3-642-17363-9 DOI 10.1007/978-3-642-17364-6 Springer Heidelberg Dordrecht London New York Texts in Theoretical Computer Science. An EATCS Series e-ISBN 978-3-642-17364-6 Library of Congress Control Number: 2011937551 ACM Codes: G.2, G.3, F.1, F.2, F.4.1 © Springer-Verlag Berlin Heidelberg 2001, 2011 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: KünkelLopka GmbH, Heidelberg Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
    To Indr˙e
    Preface Preface to the First Edition Combinatorial mathematics has been pursued since time immemorial, and at a reasonable scientific level at least since Leonhard Euler (1707–1783). It rendered 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 a part 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 a period 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. It turns out that (independent of what the given integers actually are!) we can always mark at least one-third of them. Besides classical tools, like the pigeonhole principle, the inclusion-exclusion principle, the double counting argument, induction, Ramsey argument, etc., some recent weapons – the probabilistic method and the linear algebra method – have shown their surprising power in solving such problems. With a mere knowledge of the concepts of linear independence and discrete prob- ability, completely unexpected connections can be made between algebra,
    viii Preface probability, and combinatorics. These techniques have also found striking ap- plications in other areas of discrete mathematics and, in particular, in the theory of computing. Nowadays we have comprehensive monographs covering different parts of extremal combinatorics. These books provide an invaluable source for stu- dents and researchers in combinatorics. Still, I feel that, despite its great po- tential and surprising applications, this fascinating field is not so well known for students and researchers in computer science. One reason could be that, being comprehensive and in-depth, these monographs are somewhat too dif- ficult to start with for the beginner. I have therefore tried to write a “guide tour” to this field – an introductory text which should - be self-contained, - be more or less up-to-date, - present a wide spectrum of basic ideas of extremal combinatorics, - - be accessible to graduate and motivated undergraduate students in show how these ideas work in the theory of computing, and mathematics and computer science. Even if not all of these goals were achieved, I hope that the book will at least give a first impression about the power of extremal combinatorics, the type of problems this field deals with, and what its methods could be good for. This should help students in computer science to become more familiar with combinatorial reasoning and so be encouraged to open one of these monographs for more advanced study. Intended for use as an introductory course, the text is, therefore, far from being all-inclusive. Emphasis has been given to theorems with elegant and beautiful proofs: those which may be called the gems of the theory and may be relatively easy to grasp by non-specialists. Some of the selected arguments are possible candidates for The Book, in which, according to Paul Erdős, God collects the perfect mathematical proofs.∗ I hope that the reader will enjoy them despite the imperfections of the presentation. A possible feature and main departure from traditional books in combina- torics is the choice of topics and results, influenced by the author’s twenty years of research experience in the theory of computing. Another departure is the inclusion of combinatorial results that originally appeared in computer science literature. To some extent, this feature may also be interesting for students and researchers in combinatorics. In particular, some impressive applications of combinatorial methods in the theory of computing are dis- cussed. Teaching. The text is self-contained. It assumes a certain mathematical maturity but no special knowledge in combinatorics, linear algebra, prob- ∗ “You don’t have to believe in God but, as a mathematician, you should believe in The Book.” (Paul Erdős) For the first approximation see M. Aigner and G.M. Ziegler, Proofs from THE BOOK. Second Edition, Springer, 2000.
    Preface ix ability theory, or in the theory of computing — a standard mathematical background at undergraduate level should be enough to enjoy the proofs. All necessary concepts are introduced and, with very few exceptions, all results are proved before they are used, even if they are indeed “well-known.” For- tunately, the problems and results of combinatorics are usually quite easy to state and explain, even for the layman. Its accessibility is one of its many appealing aspects. The book contains much more material than is necessary for getting ac- quainted with the field. I have split it into relatively short chapters, each devoted to a particular proof technique. I have tried to make the chapters almost independent, so that the reader can choose his/her own order to fol- low the book. The (linear) order, in which the chapters appear, is just an extension of a (partial) order, “core facts first, applications and recent devel- opments later.” Combinatorics is broad rather than deep, it appears in dif- ferent (often unrelated) corners of mathematics and computer science, and it is about techniques rather than results – this is where the independence of chapters comes from. Each chapter starts with results demonstrating the particular technique in the simplest (or most illustrative) way. The relative importance of the topics discussed in separate chapters is not reflected in their length – only the topics which appear for the first time in the book are dealt with in greater detail. To facilitate the understanding of the material, over 300 exercises of varying difficulty, together with hints to their solution, are included. This is a vital part of the book – many of the examples were chosen to complement the main narrative of the text. Some of the hints are quite detailed so that they actually sketch the entire solution; in these cases the reader should try to fill out all missing details. Acknowledgments. I would like to thank everybody who was directly or indirectly involved in the process of writing this book. First of all, I am grateful to Alessandra Capretti, Anna Gál, Thomas Hofmeister, Daniel Kral, G. Murali Krishnan, Martin Mundhenk, Gurumurthi V. Ramanan, Martin Sauerhoff and P.R. Subramania for comments and corrections. Although not always directly reflected in the text, numerous earlier discus- sions with Anna Gál, Pavel Pudlák, and Sasha Razborov on various combina- torial problems in computational complexity, as well as short communications with Noga Alon, Aart Blokhuis, Armin Haken, Johan Håstad, Zoltan Füredi, Hanno Lefmann, Ran Raz, Mike Sipser, Mario Szegedy, and Avi Wigder- son, have broadened my understanding of things. I especially benefited from the comments of Aleksandar Pekec and Jaikumar Radhakrishnan after they tested parts of the draft version in their courses in the BRICS International Ph.D. school (University of Aarhus, Denmark) and Tata Institute (Bombay, India), and from valuable comments of László Babai on the part devoted to the linear algebra method. I would like to thank the Alexander von Humboldt Foundation and the German Research Foundation (Deutsche Forschungsgemeinschaft) for sup-
    分享到：
    赞 收藏

    相关推荐

    资料库

    行业

    共收录7266份资料，累计15个分类，关注成员有19位，主要包括：物流,旅游,餐饮零售,网络游戏,咨询,金融,电子政务,外包,教育,制造,医疗,嵌入式,互联网,交通,电信

    热门标签

    物流 旅游 餐饮零售 网络游戏 咨询 金融 电子政务 外包 教育 制造 医疗 嵌入式 互联网 交通 电信

    最新资料