Applied Combinatorics

Fred S. Roberts is Professor of Mathematics and Director of DIMACS at Rutgers University. Barry Tesman is Professor of Mathematics at Dickinson College.

Preface

Notation

1 What Is Combinatorics?

1.1 The Three Problems of Combinatorics

1.2 The History and Applications of Combinatorics

References for Chapter 1

PART I The Basic Tools of Combinatorics

2 Basic Counting Rules

2.1 The Product Rule

2.2 The Sum Rule

2.3 Permutations

2.4 Complexity of Computation

2.5 r-Permutations

2.6 Subsets

2.7 r-Combinations

2.8 Probability

2.9 Sampling with Replacement

2.10 Occupancy Problems

2.10.1 The Types of Occupancy Problems

2.10.2 Case 1: Distinguishable Balls and Distinguishable Cells

2.10.3 Case 2: Indistinguishable Balls and Distinguishable Cells

2.10.4 Case 3: Distinguishable Balls and Indistinguishable Cells

2.10.5 Case 4: Indistinguishable Balls and Indistinguishable Cells

2.10.6 Examples

2.11 Multinomial Coefficients

2.11.1 Occupancy Problems with a Specified Distribution

2.11.2 Permutations with Classes of Indistinguishable Objects

2.12 Complete Digest by Enzymes

2.13 Permutations with Classes of Indistinguishable Objects Revisited

2.14 The Binomial Expansion

2.15 Power in Simple Games

2.15.1 Examples of Simple Games

2.15.2 The Shapley-Shubik Power Index

2.15.3 The U.N. Security Council

2.15.4 Bicameral Legislatures

2.15.5 Cost Allocation

2.15.6 Characteristic Functions

2.16 Generating Permutations and Combinations

2.16.1 An Algorithm for Generating Permutations

2.16.2 An Algorithm for Generating Subsets of Sets

2.16.3 An Algorithm for Generating Combinations

2.17 Inversion Distance Between Permutations and the Study of Mutations

2.18 Good Algorithms

2.18.1 Asymptotic Analysis

2.18.2 NP-Complete Problems

2.19 Pigeonhole Principle and Its Generalizations

2.19.1 The Simplest Version of the Pigeonhole Principle

2.19.2 Generalizations and Applications of the Pigeonhole Principle

2.19.3 Ramsey Numbers

Additional Exercises for Chapter 2

References for Chapter 2

3 Introduction to Graph Theory

3.1 Fundamental Concepts

3.1.1 Some Examples

3.1.2 Definition of Digraph and Graph

3.1.3 Labeled Digraphs and the Isomorphism Problem

3.2 Connectedness

3.2.1 Reaching in Digraphs

3.2.2 Joining in Graphs

3.2.3 Strongly Connected Digraphs and Connected Graphs

3.2.4 Subgraphs

3.2.5 Connected Components

3.3 Graph Coloring and Its Applications

3.3.1 Some Applications

3.3.2 Planar Graphs

3.3.3 Calculating the Chromatic Number

3.3.4 2-Colorable Graphs

3.3.5 Graph-Coloring Variants

3.4 Chromatic Polynomials

3.4.1 Definitions and Examples

3.4.2 Reduction Theorems

3.4.3 Properties of Chromatic Polynomials

3.5 Trees

3.5.1 Definition of a Tree and Examples

3.5.2 Properties of Trees

3.5.3 Proof of Theorem 3.15

3.5.4 Spanning Trees

3.5.5 Proof of Theorem 3.16 and a Related Result

3.5.6 Chemical Bonds and the Number of Trees

3.5.7 Phylogenetic Tree Reconstruction

3.6 Applications of Rooted Trees to Searching, Sorting, and

Phylogeny Reconstruction

3.6.1 Definitions

3.6.2 Search Trees

3.6.3 Proof of Theorem 3.24

3.6.4 Sorting

3.6.5 The Perfect Phylogeny Problem

3.7 Representing a Graph in the Computer

3.8 Ramsey Numbers Revisited

References for Chapter 3

4 Relations

4.1 Relations

4.1.1 Binary Relations

4.1.2 Properties of Relations/Patterns in Digraphs

4.2 Order Relations and Their Variants

4.2.1 Defining the Concept of Order Relation

4.2.2 The Diagram of an Order Relation

4.2.3 Linear Orders

4.2.4 Weak Orders

4.2.5 Stable Marriages

4.3 Linear Extensions of Partial Orders

4.3.1 Linear Extensions and Dimension

4.3.2 Chains and Antichains

4.3.3 Interval Orders

4.4 Lattices and Boolean Algebras

4.4.1 Lattices

4.4.2 Boolean Algebras

References for Chapter 4

PART II The Counting Problem

5 Generating Functions and Their Applications

5.1 Examples of Generating Functions

5.1.1 Power Series

5.1.2 Generating Functions

5.2 Operating on Generating Functions

5.3 Applications to Counting

5.3.1 Sampling Problems

5.3.2 A Comment on Occupancy Problems

5.4 The Binomial Theorem

5.5 Exponential Generating Functions and Generating Functions for Permutations

5.5.1 Definition of Exponential Generating Function

5.5.2 Applications to Counting Permutations

5.5.3 Distributions of Distinguishable Balls into Indistinguishable

Cells

5.6 Probability Generating Functions

5.7 The Coleman and Banzhaf Power Indices

References for Chapter 5

6 Recurrence Relations

6.1 Some Examples

6.1.1 Some Simple Recurrences

6.1.2 Fibonacci Numbers and Their Applications

6.1.3 Derangements

6.1.4 Recurrences Involving More than One Sequence

6.2 The Method of Characteristic Roots

6.2.1 The Case of Distinct Roots

6.2.2 Computation of the kth Fibonacci Number

6.2.3 The Case of Multiple Roots

6.3 Solving Recurrences Using Generating Functions

6.3.1 The Method

6.3.2 Derangements

6.3.3 Simultaneous Equations for Generating Functions

6.4 Some Recurrences Involving Convolutions

6.4.1 The Number of Simple, Ordered, Rooted Trees

6.4.2 The Ways to Multiply a Sequence of Numbers in a

Computer

6.4.3 Secondary Structure in RNA

6.4.4 Organic Compounds Built Up from Benzene Rings

References for Chapter 6

7 The Principle of Inclusion and Exclusion

7.1 The Principle and Some of Its Applications

7.1.1 Some Simple Examples

7.1.2 Proof of Theorem 6.1

7.1.3 Prime Numbers, Cryptography, and Sieves

7.1.4 The Probabilistic Case

7.1.5 The Occupancy Problem with Distinguishable Balls and

Cells

7.1.6 Chromatic Polynomials

7.1.7 Derangements

7.1.8 Counting Combinations

7.1.9 Rook Polynomials

7.2 The Number of Objects Having Exactly m Properties

7.2.1 The Main Result and Its Applications

7.2.2 Proofs of Theorems 7.4 and 7.5

References for Chapter 7

8 The Po´lya Theory of Counting

8.1 Equivalence Relations

8.1.1 Distinct Configurations and Databases

8.1.2 Definition of Equivalence Relations

8.1.3 Equivalence Classes

8.2 Permutation Groups

8.2.1 Definition of a Permutation Group

8.2.2 The Equivalence Relation Induced by a Permutation Group

8.2.3 Automorphisms of Graphs

8.3 Burnside’s Lemma

8.3.1 Statement of Burnside’s Lemma

8.3.2 Proof of Burnside’s Lemma

8.4 Distinct Colorings

8.4.1 Definition of a Coloring

8.4.2 Equivalent Colorings

8.4.3 Graph Colorings Equivalent under Automorphisms

8.4.4 The Case of Switching Functions

8.5 The Cycle Index

8.5.1 Permutations as Products of Cycles

8.5.2 A Special Case of P´olya’s Theorem

8.5.3 Graph Colorings Equivalent under Automorphisms Revisited

8.5.4 The Case of Switching Functions

8.5.5 The Cycle Index of a Permutation Group

8.5.6 Proof of Theorem 8.6

8.6 P´olya’s Theorem

8.6.1 The Inventory of Colorings

8.6.2 Computing the Pattern Inventory

8.6.3 The Case of Switching Functions

8.6.4 Proof of P´olya’s Theorem

References for Chapter 8

PART III The Existence Problem

9 Combinatorial Designs

9.1 Block Designs

9.2 Latin Squares

9.2.1 Some Examples

9.2.2 Orthogonal Latin Squares

9.2.3 Existence Results for Orthogonal Families

9.2.4 Proof of Theorem 9.3

9.2.5 Orthogonal Arrays with Applications to Cryptography

9.3 Finite Fields and Families of Latin Squares

9.3.1 Modular Arithmetic

9.3.2 Modular Arithmetic and the RSA Cryptosystem

9.3.3 The Finite Fields GF(pk)

9.3.4 Construction of a Complete Orthogonal Family of n x n Latin Squares if n Is a Power of a Prime

9.3.5 Justification of the Construction of a Complete Orthogonal Family if n = pk

9.4 Balanced Incomplete Block Designs

9.4.1 (b, v, r, k, λ)-Designs

9.4.2 Necessary Conditions for the Existence of

(b, v, r, k, λ)-Designs

9.4.3 Proof of Fisher’s Inequality

9.4.4 Resolvable Designs

9.4.5 Steiner Triple Systems

9.4.6 Symmetric Balanced Incomplete Block Designs

9.4.7 Building New (b, v, r, k, λ)-Designs from Existing Ones

9.4.8 Group Testing and Its Applications

9.4.9 Steiner Systems and the National Lottery

9.5 Finite Projective Planes

9.5.1 Basic Properties

9.5.2 Projective Planes, Latin Squares, and (v, k, λ)-Designs

References for Chapter 9

10 Coding Theory

10.1 Information Transmission

10.2 Encoding and Decoding

10.3 Error-Correcting Codes

10.3.1

Error Correction and Hamming Distance

10.3.2

The Hamming Bound

10.3.3

The Probability of Error

10.3.4

Consensus Decoding and Its Connection to Finding Patterns

in Molecular Sequences

10.4

Linear

Codes

10.4.1

Generator Matrices

10.4.2

Error Correction Using Linear Codes

10.4.3

Hamming Codes

10.5 The Use of Block Designs to Find Error-Correcting Codes

10.5.1

HadamardCodes

10.5.2

ConstructingHadamardDesigns

10.5.3

The Richest (n, d)-Codes

10.5.4

SomeApplications

References

forChapter10

11 Existence Problems in Graph Theory

11.1 Depth-First Search: A Test for Connectedness

11.1.1 Depth-First Search

11.1.2 The Computational Complexity of Depth-First Search

11.1.3 A Formal Statement of the Algorithm

11.1.4 Testing for Connectedness of Truly Massive Graphs

11.2 The One-Way Street Problem

11.2.1 Robbins’ Theorem

11.2.2 A Depth-First Search Algorithm

11.2.3 Efficient One-Way Street Assignments

11.2.4 Efficient One-Way Street Assignments for Grids

11.2.5 Annular Cities and Communications in Interconnection Networks

11.3 Eulerian Chains and Paths

11.3.1 The K¨onigsberg Bridge Problem

11.3.2 An Algorithm for Finding an Eulerian Closed Chain

11.3.3 Further Results about Eulerian Chains and Paths

11.4 Applications of Eulerian Chains and Paths

11.4.1 The “Chinese Postman” Problem

11.4.2 Street Sweeping

11.4.3 Finding Unknown RNA/DNA Chains

11.4.4 A Coding Application

11.4.5 De Bruijn Sequences and Telecommunications

11.5 Hamiltonian Chains and Paths

11.5.1 Definitions

11.5.2 Sufficient Conditions for the Existence of a Hamiltonian

Circuit in a Graph

11.5.3 Sufficient Conditions for the Existence of a Hamiltonian Cycle

in a Digraph

11.6 Applications of Hamiltonian Chains and Paths

11.6.1

Tournaments

11.6.2

TopologicalSorting

11.6.3

SchedulingProblems inOperationsResearch

11.6.4

Facilities Design

11.6.5

Sequencing by Hybridization

References

forChapter11

PART IV Combinatorial Optimization

12 Matching and Covering

12.1 Some Matching Problems

12.2 Some Existence Results: Bipartite Matching and Systems of Distinct Representatives

12.2.1 Bipartite Matching

12.2.2 Systems of Distinct Representatives

12.3 The Existence of Perfect Matchings for Arbitrary Graphs

12.4 Maximum Matchings and Minimum Coverings

12.4.1 Vertex Coverings

12.4.2 Edge Coverings

12.5 Finding a Maximum Matching

12.5.1 M -Augmenting Chains

12.5.2 Proof of Theorem 12.7

12.5.3 An Algorithm for Finding a Maximum Matching

12.6 Matching as Many Elements of X as Possible

12.7 Maximum-Weight Matching

12.7.1 The “Chinese Postman” Problem Revisited

12.7.2 An Algorithm for the Optimal Assignment Problem

(Maximum-Weight Matching)

12.8 Stable Matchings

12.8.1 Gale-Shapley Algorithm

12.8.2 Numbers of Stable Matchings

12.8.3 Structure of Stable Matchings

12.8.4 Stable Marriage Extensions

References for Chapter 12

13 Optimization Problems for Graphs and Networks

13.1 Minimum Spanning Trees

13.1.1 Kruskal’s Algorithm

13.1.2 Proof of Theorem 13.1

13.1.3 Prim’s Algorithm

13.2 The Shortest Route Problem

13.2.1 The Problem

13.2.2 Dijkstra’s Algorithm

13.2.3 Applications to Scheduling Problems

13.3 Network Flows

13.3.1 The Maximum-Flow Problem

13.3.2 Cuts

13.3.3 A Faulty Max-Flow Algorithm

13.3.4 Augmenting Chains

13.3.5 The Max-Flow Algorithm

13.3.6 A Labeling Procedure for Finding Augmenting Chains

13.3.7 Complexity of the Max-Flow Algorithm

13.3.8 Matching Revisited

13.3.9 Menger’s Theorems

13.4 Minimum-Cost Flow Problems

13.4.1 Some Examples

References for Chapter 13

Author Index

Subject Index