Combinatorial Mathematics

This long-awaited textbook is the most comprehensive introduction to a broad swath of combinatorial and discrete mathematics. The text covers enumeration, graphs, sets, and methods, and it includes both classical results and more recent developments. Assuming no prior exposure to combinatorics, it explains the basic material for graduate-level students in mathematics and computer science. Optional more advanced material also makes it valuable as a research reference. Suitable for a one-year course or a one-semester introduction, this textbook prepares students to move on to more advanced material. It is organized to emphasize connections among the topics, and facilitate instruction, self-study, and research, with more than 2200 exercises (many accompanied by hints) at various levels of difficulty. Consistent notation and terminology are used throughout, allowing for a discussion of diverse topics in a unified language. The thorough bibliography, containing thousands of citations, makes this a valuable source for students and researchers alike. Cover Half-title page Title page Copyright page Dedication Contents Preface Chapter 0 – Introduction Sets, Functions, and Relations Graphs Discrete Probability Other Discrete Structures Complexity Part I — Enumeration Chapter 1 – Combinatorial Arguments. 1.1. Classical Models. Elementary Principles Words, Sets, and Multisets Exercises 1.2. Identities Lattice Paths and Pascal ’s Triangle Delannoy Numbers Exercises 1.3. Applications Graphs and Trees Multinomial Coefficients The Ballot Problem Catalan Numbers Exercises Chapter 2 – Recurrence Relations 2.1. Obtaining Recurrences Classical Examples Variations Exercises 2.2. Elementary Solution Methods The Characteristic Equation Method The Generating Function Method Exercises 2.3. Further Topics The Substitution Method Asymptotic Analysis The WZ Method (optional) Exercises Chapter 3 – Generating Functions 3.1. Ordinary Generating Functions Modeling Counting Problems Permutation Statistics Exercises 3.2. Coefficients and Applications Operations and Summations Snake Oil Exercises 3.3. Exponential Generating Functions Modeling Labeled Structures Stirling and Derangement Applications The Exponential Formula The Lagrange Inversion Formula (optional) Exercises 3.4. Partitions of Integers Generating Function Methods Ferrers Diagrams Bulgarian Solitaire (optional) Distribution Models Exercises Chapter 4 – Further Topics 4.1. The Inclusion-Exclusion Principle The Basic Principle Restricted Permutations Signed Involutions Determinants and Path Systems (optional) Exercises 4.2. P ́olya–Redfield Counting Burnside’s Lemma The Pattern Inventory Classical Cycle Indices Exercises 4.3. Permutations and Tableaux The Hook-Length Formula The RSK Correspondence Switching P-Symbol and Q-Symbol Jeu de Taquin (optional) Exercises Part II — Graphs Chapter 5 – First Concepts for Graphs 5.1. Definitions and Examples Graphs and Subgraphs Isomorphism The Petersen Graph and Hypercubes Exercises 5.2. Vertex Degrees The Degree-Sum Formula Degree Lists Extremality Directed Graphs Exercises 5.3. Connection and Decomposition Components and Walks Cycles and Cut-Edges Eulerian Circuits Exercises 5.4. Trees and Distance Properties of Trees Distance and Diameter Optimization on Weighted Graphs Exercises Chapter 6 – Matchings 6.1. Matching in Bipartite Graphs Hall’s Theorem Min-Max Relations Exercises 6.2. Matching in General Graphs Tutte’s 1-Factor Theorem General Factors of Graphs Exercises 6.3. Algorithmic Aspects Augmenting Paths Weighted Bipartite Matching Fast Bipartite Matching (optional) Stable Matchings (optional) Exercises Chapter 7 – Connectivity and Cycles 7.1. Connectivity Parameters Separating Sets Edge Cuts Blocks Exercises 7.2. Properties of k-Connected Graphs Menger’s Theorem Applications of Menger’s Theorem 2-Connected and 3-Connected Graphs Highly Connected Orientations (optional) Exercises 7.3. Spanning Cycles Properties of Hamiltonian Graphs Sufficient Conditions Long Cycles (optional) Further Directions (optional) Exercises Chapter 8 – Coloring 8.1. Vertex Coloring Upper Bounds Triangle-Free Graphs Exercises 8.2. Structural Aspects Color-Critical Graphs List Coloring Forced Subgraphs (optional) Exercises 8.3. Edge-Coloring and Perfection Special Classes Vizing’s Theorem and Extensions List Edge-Coloring Perfect Graphs Exercises Chapter 9 – Planar Graphs 9.1. Embeddings and Euler ’s Formula Drawings and Duals Euler’s Formula Exercises 9.2. Structure of Planar Graphs Kuratowski’s Theorem The Separator Theorem (optional) Exercises 9.3. Coloring of Planar Graphs Edge-Colorings and Spanning Cycles 5-Colorable and 5-Choosable The Four Color Problem Discharging and Light Edges Other Aspects of Discharging (optional) Exercises Part III — Sets Chapter 10 – Ramsey Theory 10.1. The Pigeonhole Principle Classical Applications Monotone Sublists Pattern-Avoiding Permutations (optional) Large Girth and Chromatic Number (optional) Edge-Coloring of Hypergraphs (optional) Exercises 10.2. Ramsey’s Theorem The Main Theorem Applications Ramsey Numbers Graph Ramsey Theory Exercises 10.3. Further Topics Van der Waerden’s Theorem Infinite Sets (optional) The Canonical Ramsey Theorem (optional) Exercises Chapter 11 – Extremal Problems 11.1. Forced Subgraphs Turán’s Theorem Erdo[doublegrave]s–Stone Theorem Linear Ramsey for Bounded Degree Roth’s Theorem Proof of the Regularity Lemma (optional) Exercises 11.2. Families of Sets The Kruskal–Katona Theorem Antichains and Intersecting Families Chv ́atal ’s Conjecture Sunflowers (optional) Entropy (optional) Exercises 11.3. Matroids Hereditary Systems and Examples Axiomatics of Matroids Duality and Minors The Span Function Matroid Intersection Matroid Union Exercises Chapter 12 – Partially Ordered Sets 12.1. Structure of Posets Definitions and Examples Dilworth’s Theoremand Beyond Exercises 12.2. Symmetric Chains and LYM Orders Graded Posets Symmetric Chain Decompositions LYM and Sperner Properties Products of LYM Orders (optional) Exercises 12.3. Linear Extensions and Dimension Order Dimension Computation and Bounds Bipartite Posets Exercises 12.4. Special Families of Posets Semiorders and Interval Orders Lattices Distributive Lattices Correlational Inequalities A Problemin Ramsey Theory (optional) Exercises Chapter 13 – Combinatorial Designs 13.1. Arrangements. Latin Squares Block Designs Symmetric Designs Hadamard Matrices Exercises 13.2. Projective Planes Relation to Designs Applications to Extremal Problems Difference Sets Exercises 13.3. Further Constructions Steiner Triple Systems Graphical Designs Resolvable Designs and Other Tools The Euler Conjecture (optional) Exercises Part IV — Methods Chapter 14 – The Probabilistic Method 14.1. Existence and Expectation The Union Bound Random Variables Exercises 14.2. Refinements of Basic Methods Deletions and Alterations The Symmetric Local Lemma The General Local Lemma (optional) Exercises 14.3. Moments and Thresholds “Almost Always” Threshold Functions Convergence of Moments Graph Evolution Exercises 14.4. Concentration Inequalities Chebyshev and Chernoff Bounds Martingales Bounded Differences (optional) Exercises Chapter 15 – Linear Algebra 15.1. Dimension and Polynomials The Dimension Argument Restricted Intersections of Sets (optional) Combinatorial Nullstellensatz The Alon–Tarsi Theorem Exercises 15.2. Matrices Determinants and Trees Cycle Space and Bond Space Permanents and Planar Graphs Möbius Inversion (optional) Exercises 15.3. Eigenvalues Spectra of Graphs Eigenvalues and Graph Parameters Regular and Strongly Regular Graphs Laplacian Eigenvalues Exercises Chapter 16 – Geometry and Topology 16.1. Graph Drawings Embeddings on Grids Crossing Number Exercises 16.2. Combinatorial Topology Sperner ’s Lemma and Bandwidth Equivalent Topological Lemmas The Borsuk–UlamTheorem Kneser Conjecture and Gale’s Lemma Ham Sandwiches and Bisections Borsuk’s Conjecture Exercises 16.3. Volumes and Containment Monotone Subsequences Balanced Comparisons Containment Orders Exercises Hints to Selected Exercises References Author Index Glossary of Notation Subject Index "This long-awaited textbook is the most comprehensive introduction to a broad swath of combinatorial and discrete mathematics. The text covers enumeration, graphs, sets, and methods, and it includes both classical results and more recent developments. Assuming no prior exposure to combinatorics, it explains the basic material for graduate-level students in mathematics and computer science. Optional more advanced material makes it also valuable as a research reference. Suitable for a one-year course or a one-semester introduction, this textbook prepares students to move on to more advanced material. It is organized to emphasize connections among the topics and facilitate instruction, self-study, and research, with more than 2200 exercises (many accompanied by hints) at various levels of difficulty. Consistent notation and terminology are used throughout, allowing for a discussion of diverse topics in a unified language. The thorough bibliography, containing thousands of citations, makes this a valuable source for students and researchers alike"-- Provided by publisher "This long-awaited textbook is the most comprehensive introduction to a broad swath of combinatorial and discrete mathematics. The text covers enumeration, graphs, sets, and methods, and it includes both classical results and more recent developments. Assuming no prior exposure to combinatorics, it explains the basic material for graduate-level students in mathematics and computer science. Optional more advanced material makes it also valuable as a research reference. Suitable for a one-year course or a one-semester introduction, this textbook prepares students to move on to more advanced material. It is organized to emphasize connections among the topics and facilitate instruction, self-study, and research, with more than 2100 exercises (many accompanied by hints) at various levels of difficulty. Consistent notation and terminology are used throughout, allowing for a discussion of diverse topics in a unified language. The thorough bibliography, containing thousands of citations, makes this a valuable source for students and researchers alike"-- Provided by publisher This thorough introduction to combinatorial and discrete mathematics provides readable and well-illustrated instruction in the basic material for graduate students in mathematics and computer science. With optional more advanced material and a thorough bibliography, it will also be an essential reference work for researchers in the field.