# Applied Combinatorics

(1 review)

Mitchel Keller, Washington and Lee University

William Trotter, Georgia Institute of Technology

Pub Date: 2017

ISBN 13: 9781973702719

Publisher: Independent

Language: English

## Conditions of Use

Attribution-ShareAlike

CC BY-SA

## Reviews

This is a book used at Georgia Tech for a junior level course targeted primarily at students pursuing a B.S. in Computer Science. The purpose of this course is to expose students to combinatorics using applications to emphasize the key concepts... read more

## Table of Contents

About the Authors

Acknowledgements

Preface

Preface to 2017 Edition

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.

*Applied Combinatorics* began its life as a set of course notes we developed when Mitch was a TA for a larger than usual section of Tom's MATH 3012: Applied Combinatorics course at Georgia Tech in Spring Semester 2006. Since then, the material has been greatly expanded and exercises have been added. The text has been in use for most MATH 3012 sections at Georgia Tech for several years now. Since the text has been available online for free, it has also been adopted at a number of other institutions for a wide variety of courses. In August 2016, we made the first release of Applied Combinatorics in HTML format, thanks to a conversion of the book's source from LaTeX to MathBook XML. An inexpensive print-on-demand version is also available for purchase. Find out all about ways to get the book.

Since Fall 2016, *Applied Combinatorics* has been on the list of approved open textbooks from the American Institute of Mathematics.

Applied Combinatorics is open source and licensed under the Creative Commons Attribution-ShareAlike 4.0 International License (CC-BY-SA).

## About the Contributors

### Authors

**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.