Combinatorial Mathematics

Описание

xiv Preface
In 1996, I realized that this structure served only students already committed to focusing on combinatorics. For others, an overview of the subject could
have great value. An educated mathematical scientist should know some algebra and analysis, and also such a person should be acquainted with fundamental
combinatorics and its relationships to other areas. Furthermore, disparities in
preparation of entering students make a core course worthwhile to establish a
common background before studying advanced material in combinatorics.
In 1997, I started a one-semester overview course to serve these goals. I extracted the fundamental material from The Art of Combinatorics and organized
it to emphasize connections among topics. This book is the result. However, with
so much beautiful combinatorics to choose from, I could not bring myself to cut
the book down to one semester. It can support a two-semester sequence, analogous to fundamental two-semester sequences in classical areas of mathematics.
It can also support various one-semester courses, as discussed later.
Since the scope is large, I have also sought to make the book useful as a research reference, rewarding further study after the courses are over. This leads to
a fair amount of optional material allowing the reader to probe farther into the
subject, plus remarks that provide statements and pointers to further results.
Nevertheless, I still aim to keep the material accessible to graduate students.
Organization
One can organize combinatorial mathematics in many ways: by structures
discussed, types of questions, methods used, etc. In a broad overview, the connections among topics are as important as the groupings within topics.
Most presentations of elementary combinatorics begin with enumeration or
with graph theory; the former is the more classical approach. Natural enumerative questions arise in elementary graph theory, and many graph-theoretic arguments use basic counting techniques, so each informs the other. Here the basic
notions of trees, cycles, and isomorphism are stated in Chapter 0 so that enumerative problems about graphs can be used as examples in Part I.
Part I presents the basics of bijective arguments, recurrence relations, generating functions, and inclusion-exclusion, with enhancements. Young tableaux
and the elementary aspects of Polya–Redfield counting appear here from a com- ´
binatorial point of view. Deeper algebraic aspects of enumeration are omitted.
Part II pursues central themes of elementary graph theory while reaching
important and classical results, particularly those having broad applications.
Graph theory is now a huge subject, so selecting fundamental core material is
difficult. Many large topics are mentioned here at most in passing or in exercises;
these include automorphism groups, Cayley graphs, graph representations, reconstruction, domination, decomposition, packings, genus, minors, nowhere-zero
flows, Tutte polynomials, graph labelings, and structured families of graphs.
Part III explores our most general structural object: families of sets, generalizing graphs to hypergraphs. Four aspects of set systems are studied: Ramsey
theory, extremal set theory, the structure of partially ordered sets and matroids,
and combinatorial designs. Many aspects of posets and enumeration known as
algebraic combinatorics are omitted (but Mobius inversion is in Chapter 15 ¨ ).

Детали