# Applied Combinatorics

Mitchel Keller, Washington and Lee University

William Trotter, Georgia Institute of Technology

Pub Date: 2016

ISBN 13: 978-1-5348786-5-5

Publisher: Independent

## Conditions of Use

Attribution-ShareAlike

CC BY-SA

## Reviews

There are no reviews for this book

## Table of Contents

About the Authors

Acknowledgements

Preface

Preface to 2016 Edition

Prologue

1. An Introduction to Combinatorics

2. Strings, Sets and Binomial Coefficients

3. Induction

4. Combinatorial Basics

5. Graph Theory

6. Partially Ordered Sets

7. Inclusion-Exclusion

8. Generating Functions

9. Recurrence Equations

10. Probability

11. Applying Probability to Combinatorics

12. Graph Algorithms

13. Network Flows

14. Combinatorial Applications of Network Flows

15. Polya’s Enumeration Theorem

16. The Many Faces of Combinatorics

A. Epilogue

B. Background Material for Combinatorics

C. List of Notation

Index

## About the Book

*Applied Combinatorics* is an open-source textbook for a course covering the fundamental enumeration techniques (permutations, combinations, subsets, pigeon hole principle), recursion and mathematical induction, more advanced enumeration techniques (inclusion-exclusion, generating functions, recurrence relations, Polyá theory), discrete structures (graphs, digraphs, posets, interval orders), and discrete optimization (minimum weight spanning trees, shortest paths, network flows). There are also chapters introducing discrete probability, Ramsey theory, combinatorial applications of network flows, and a few other nuggets of discrete mathematics.

## About the Contributors

### Author(s)

**Mitchel T. Keller** is an assistant professor in the Department of Mathematics at Washington and Lee University, a small liberal arts college in Lexington, Virginia. He holds a B.S. in mathematics from North Dakota State University and a Ph.D. in mathematics from the Georgia Institute of Technology. (His Ph.D. advisor is now his co-author on this book.) Mitch’s research interests are in the combinatorics of partially ordered sets, online algorithms, and combinatorial approaches to Stanley depth of monomial ideals. He likes to travel, bake, and take photographs. (The cover image for the 2016 Edition of Applied Combinatorics is of work his honors thesis student Matthew R. Kiser did on the board in Mitch’s office.) Mitch is also the Managing Director of the Mathematics Genealogy Project.

**William T. Trotter** is a professor in the School of Mathematics at the Georgia Institute of Technology in Atlanta. In a career spanning more than four decades, Tom has been a faculty member and administrator at the University of South Carolina, Arizona State University, and Georgia Tech. He has published extensively on the combinatorics of partially ordered sets, graph theory, Ramsey theory, and extremal combinatorics. His monograph on dimension theory for partially ordered sets has been in print for nearly 25 years. Tom is an avid movie buff, fan of the New York Yankees, and golfer.