Handbook of Discrete and Combinatorial Mathematics [2nd ed.]

Cover......Page 1
Half Title......Page 2
Title Page......Page 8
Copyright Page......Page 9
Table of Contents......Page 10
PREFACE......Page 16
CONTRIBUTORS......Page 22
1: FOUNDATIONS......Page 26
 1.1 Propositional and Predicate Logic......Page 37
 1.2 Set Theory......Page 47
 1.3 Functions......Page 57
 1.4 Relations......Page 67
 1.5 Proof Techniques......Page 76
 1.6 Axiomatic Program Verification......Page 88
 1.7 Logic-Based Computer Programming Paradigms......Page 95
2: COUNTING METHODS......Page 110
 2.1 Summary of Counting Problems......Page 113
 2.2 Basic Counting Techniques......Page 118
 2.3 Permutations and Combinations......Page 124
 2.4 Inclusion/Exclusion......Page 135
 2.5 Partitions......Page 141
 2.6 Burnside/Pólya Counting Formula......Page 149
 2.7 Möbius Inversion Counting......Page 156
 2.8 Young Tableaux......Page 158
3: SEQUENCES......Page 164
 3.1 Special Sequences......Page 168
 3.2 Generating Functions......Page 198
 3.3 Recurrence Relations......Page 205
 3.4 Finite Differences......Page 216
 3.5 Finite Sums and Summation......Page 221
 3.6 Asymptotics of Sequences......Page 227
 3.7 Mechanical Summation Procedures......Page 232
4: NUMBER THEORY......Page 242
 4.1 Basic Concepts......Page 248
 4.2 Greatest Common Divisors......Page 256
 4.3 Congruences......Page 260
 4.4 Prime Numbers......Page 265
 4.5 Factorization......Page 286
 4.6 Arithmetic Functions......Page 290
 4.7 Primitive Roots and Quadratic Residues......Page 299
 4.8 Diophantine Equations......Page 312
 4.9 Diophantine Approximation......Page 321
 4.10 Algebraic Number Theory......Page 327
 4.11 Elliptic Curves......Page 336
5: ALGEBRAIC STRUCTURES......Page 348
 5.1 Algebraic Models......Page 354
 5.2 Groups......Page 356
 5.3 Permutation Groups......Page 368
 5.4 Rings......Page 372
 5.5 Polynomial Rings......Page 378
 5.6 Fields......Page 381
 5.7 Lattices......Page 391
 5.8 Boolean Algebras......Page 394
6: LINEAR ALGEBRA......Page 406
 6.1 Vector Spaces......Page 412
 6.2 Linear Transformations......Page 422
 6.3 Matrix Algebra......Page 430
 6.4 Linear Systems......Page 445
 6.5 Eigenanalysis......Page 458
 6.6 Combinatorial Matrix Theory......Page 470
 6.7 Singular Value Decomposition......Page 483
7: DISCRETE PROBABILITY......Page 500
 7.1 Fundamental Concepts......Page 505
 7.2 Independence and Dependence......Page 508
 7.3 Random Variables......Page 515
 7.4 Discrete Probability Computations......Page 521
 7.5 Random Walks......Page 526
 7.6 System Reliability......Page 533
 7.7 Discrete-Time Markov Chains......Page 543
 7.8 Hidden Markov Models......Page 552
 7.9 Queueing Theory......Page 561
 7.10 Simulation......Page 568
 7.11 The Probabilistic Method......Page 576
8: GRAPH THEORY......Page 594
 8.1 Introduction to Graphs......Page 609
 8.2 Graph Models......Page 624
 8.3 Directed Graphs......Page 626
 8.4 Distance, Connectivity, Traversability, & Matchings......Page 637
 8.5 Graph Isomorphism and Reconstruction......Page 650
 8.6 Graph Colorings, Labelings, & Related Parameters......Page 656
 8.7 Planar Drawings......Page 672
 8.8 Topological Graph Theory......Page 679
 8.9 Enumerating Graphs......Page 684
 8.10 Graph Families......Page 694
 8.11 Analytic Graph Theory......Page 704
 8.12 Hypergraphs......Page 709
9: TREES......Page 718
 9.1 Characterizations and Types of Trees......Page 721
 9.2 Spanning Trees......Page 730
 9.3 Enumerating Trees......Page 736
10: NETWORKS AND FLOWS......Page 746
 10.1 Minimum Spanning Trees......Page 751
 10.2 Matchings......Page 758
 10.3 Shortest Paths......Page 773
 10.4 Maximum Flows......Page 784
 10.5 Minimum Cost Flows......Page 794
 10.6 Communication Networks......Page 804
 10.7 Difficult Routing and Assignment Problems......Page 818
 10.8 Small-World Networks......Page 832
 10.9 Network Representations and Data Structures......Page 851
11: PARTIALLY ORDERED SETS......Page 868
 11.1 Basic Poset Concepts......Page 876
 11.2 Poset Properties......Page 889
12: COMBINATORIAL DESIGNS......Page 904
 12.1 Block Designs......Page 910
 12.2 Symmetric Designs and Finite Geometries......Page 921
 12.3 Latin Squares and Orthogonal Arrays......Page 930
 12.4 Matroids......Page 938
13: DISCRETE AND COMPUTATIONAL GEOMETRY......Page 950
 13.1 Arrangements of Geometric Objects......Page 958
 13.2 Space Filling......Page 977
 13.3 Combinatorial Geometry......Page 986
 13.4 Polyhedra......Page 995
 13.5 Algorithms and Complexity in Computational Geometry......Page 999
 13.6 Geometric Data Structures and Searching......Page 1008
 13.7 Computational Techniques......Page 1017
 13.8 Applications of Geometry......Page 1023
14: CODING THEORY......Page 1048
 14.1 Communication Systems and Information Theory......Page 1052
 14.2 Basics of Coding Theory......Page 1056
 14.3 Linear Codes......Page 1060
 14.4 Cyclic Codes......Page 1069
 14.5 Bounds for Codes......Page 1078
 14.6 Nonlinear Codes......Page 1081
 14.7 Convolutional Codes......Page 1082
 14.8 Quantum Error-Correcting Codes......Page 1087
15: CRYPTOGRAPHY......Page 1094
 15.1 Basics of Cryptography......Page 1100
 15.2 Classical Cryptography......Page 1104
 15.3 Modern Private Key Cryptosystems......Page 1108
 15.4 Hash Functions......Page 1121
 15.5 Public Key Cryptography......Page 1125
 15.6 Cryptographic Mechanisms......Page 1137
 15.7 High-Level Applications of Cryptography......Page 1154
16: DISCRETE OPTIMIZATION......Page 1168
 16.1 Linear Programming......Page 1173
 16.2 Location Theory......Page 1199
 16.3 Packing and Covering......Page 1210
 16.4 Activity Nets......Page 1220
 16.5 Game Theory......Page 1230
 16.6 Sperner’s Lemma and Fixed Points......Page 1242
 16.7 Combinatorial Auctions......Page 1247
 16.8 Very Large-Scale Neighborhood Search......Page 1257
 16.9 Tabu Search......Page 1266
17: THEORETICAL COMPUTER SCIENCE......Page 1290
 17.1 Computational Models......Page 1299
 17.2 Computability......Page 1311
 17.3 Languages and Grammars......Page 1315
 17.4 Algorithmic Complexity......Page 1326
 17.5 Complexity Classes......Page 1333
 17.6 Randomized Algorithms......Page 1340
18: INFORMATION STRUCTURES......Page 1348
 18.1 Abstract Datatypes......Page 1355
 18.2 Concrete Data Structures......Page 1364
 18.3 Sorting and Searching......Page 1372
 18.4 Hashing......Page 1387
 18.5 Dynamic Graph Algorithms......Page 1390
19: DATA MINING......Page 1400
 19.1 Data Mining Fundamentals......Page 1403
 19.2 Frequent Itemset Mining and Association Rules......Page 1409
 19.3 Classification Methods......Page 1412
 19.4 Clustering......Page 1419
 19.5 Outlier Detection......Page 1442
20: DISCRETE BIOINFORMATICS......Page 1450
 20.1 Sequence Alignment......Page 1453
 20.2 Phylogenetics......Page 1471
 20.3 Discrete-Time Dynamical Systems......Page 1480
 20.4 Genome Assembly......Page 1492
 20.5 RNA Folding......Page 1500
 20.6 Combinatorial Neural Codes......Page 1508
 20.7 Food Webs and Graphs......Page 1515
BIOGRAPHIES......Page 1540
INDEX......Page 1566