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 Part I — Enumeration Chapter 1 – Combinatorial Arguments. 1.1. Classical Models. 1.2. Identities 1.3. Applications Chapter 2 – Recurrence Relations 2.1. Obtaining Recurrences 2.2. Elementary Solution Methods 2.3. Further Topics Chapter 3 – Generating Functions 3.1. Ordinary Generating Functions 3.2. Coefficients and Applications 3.3. Exponential Generating Functions 3.4. Partitions of Integers Chapter 4 – Further Topics 4.1. The Inclusion-Exclusion Principle 4.2. P ́olya–Redfield Counting 4.3. Permutations and Tableaux Part II — Graphs Chapter 5 – First Concepts for Graphs 5.1. Definitions and Examples 5.2. Vertex Degrees 5.3. Connection and Decomposition 5.4. Trees and Distance Chapter 6 – Matchings 6.1. Matching in Bipartite Graphs 6.2. Matching in General Graphs 6.3. Algorithmic Aspects Chapter 7 – Connectivity and Cycles 7.1. Connectivity Parameters 7.2. Properties of k-Connected Graphs 7.3. Spanning Cycles Chapter 8 – Coloring 8.1. Vertex Coloring 8.2. Structural Aspects 8.3. Edge-Coloring and Perfection Chapter 9 – Planar Graphs 9.1. Embeddings and Euler ’s Formula 9.2. Structure of Planar Graphs 9.3. Coloring of Planar Graphs Part III — Sets Chapter 10 – Ramsey Theory 10.1. The Pigeonhole Principle 10.2. Ramsey’s Theorem 10.3. Further Topics Chapter 11 – Extremal Problems 11.1. Forced Subgraphs 11.2. Families of Sets 11.3. Matroids Chapter 12 – Partially Ordered Sets 12.1. Structure of Posets 12.2. Symmetric Chains and LYM Orders 12.3. Linear Extensions and Dimension 12.4. Special Families of Posets Chapter 13 – Combinatorial Designs 13.1. Arrangements. 13.2. Projective Planes 13.3. Further Constructions Part IV — Methods Chapter 14 – The Probabilistic Method 14.1. Existence and Expectation 14.2. Refinements of Basic Methods 14.3. Moments and Thresholds 14.4. Concentration Inequalities Chapter 15 – Linear Algebra 15.1. Dimension and Polynomials 15.2. Matrices 15.3. Eigenvalues Chapter 16 – Geometry and Topology 16.1. Graph Drawings 16.2. Combinatorial Topology 16.3. Volumes and Containment 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.