| The second edition of Applied Combinatorics comes 20 years after the first one. It has been substantially rewritten with more than 200 pages of new material and significant changes in numerous sections. There are many new examples and exercises. On the other hand, the main philosophy of the book is unchanged. The following three paragraphs are from the preface of the first edition and these words still ring true today. Perhaps the fastest growing area of modern mathematics is combinatorics. A major reason for this rapid growth is its wealth of applications, to computer science, communications, transportation, genetics, experimental design, scheduling, and so on. This book introduces the reader to the tools of combinatorics from an applied point of view. Much of the growth of combinatorics has gone hand in hand with the development of the computer. Today's high-speed computers make it possible to implement solutions to practical combinatorial problems from a wide variety of fields, solutions that could not be implemented until quite recently. This has resulted in increased emphasis on the development of solutions to combinatorial problems. At the same time, the development of computer science has brought with it numerous challenging combinatorial problems of its own. Thus, it is hard to separate combinatorial mathematics from computing. The reader will see the emphasis on computing here by the frequent use of examples from computer science, the frequent discussion of algorithms, and so on. On the other hand, the general point of view taken in this book is that combinatorics has a wealth of applications to a large number of subjects, and this book has tried to emphasize the variety of these applications rather than just focusing on one. Many of the mathematical topics presented here are relatively standard topics from the rapidly growing textbook literature of combinatorics. Others are taken from the current research literature, or are chosen because they illustrate interesting applications of the subject. The book is distinguished, we believe, by its wide-ranging treatment of applications. Entire sections are devoted to such applications as switching functions, the use of enzymes to uncover unknown RNA chains, searching and sorting problems of information retrieval, construction of error-correcting codes, counting of chemical compounds, calculation of power in voting situations, and uses of Fibonacci numbers. There are entire sections on applications of recurrences involving convolutions, applications of eulerian chains, applications of generating functions, and so on, that are unique to the literature. WHAT'S NEW IN THIS EDITION? Much of the appeal of this book has stemmed from its references to modern literature and real applications. The applications that motivate the development and use of combinatorics are expanding greatly, especially in the natural and social sciences. In particular, computer science and biology are primary sources of many of the new applications appearing in this second edition. Along with these additions, we have also added some major new topics, deleted some specialized ones, made organizational changes, and updated and improved the examples, exercises, and references to the literature. Some of the major changes in the second edition are the following: Chapter 1 (What is Combinatorics?): We have added major new material on list colorings, expanding discussion of scheduling legislative committees. List colorings are returned to in various places in the book. Chapter 2 (Basic Counting Rules): Section 2.16, that previously only discussed algorithmic methods for generating permutations, has been substantially expanded and broken into subsections. Section 2.18, that introduces the notion of "good algorithms" and NP-completeness, has been substantially rewritten and modernized. A new section on the pigeonhole principle has been added. The section consists of the material from Section 8.1 of the first edition and some of the material from Section 8.2, that deals with Ramsey theory. We have also added a substantial new section on inversion distance between permutations and the study of mutations in evolutionary biology. Chapter 3 (Introduction to Graph Theory): A major new subsection has been added to Section 3.3, the graph coloring section. This new subsection deals with the generalizations of graph coloring, such as multi-coloring and T-coloring, that have been motivated by practical problems such as mobile radio telephone problems, traffic phasing, and channel assignment. We have also introduced a major new subsection on phylogenetic tree reconstruction. Much of the material on Ramsey theory from Chapter 8 of the first edition, and not covered in Chapter 2, has been updated and presented in a new section. Chapter 4 (Relations): This chapter is brand new. Concepts of binary relations are defined and connected to digraphs. Orders are introduced using digraphs and relations, and parts of the new chapter deal with linear and weak orders; partial orders, linear extensions and dimension; chains and comparability graphs; lattices; boolean algebras; and switching functions and gate networks. The chapter is closely tied to applications ranging from information theory to utility theory to searching and sorting, as well as returning to the earlier applications such as switching functions. This chapter includes some applications not widely discussed in the combinatorics literature, such as preference, search engines, sequencing by hybridization, and psychophysical scaling. Examples based on Chapter 4 concepts have also been added to many subsequent chapters. Coverage of Chapter 4 can be delayed until after Chapter 11. Chapter 5 (Generating Functions and their Applications): In the first edition, this was Chapter 4. Many new concepts and examples introduced in earlier chapters are revisited here, for example, weak orders from Chapter 4 and list colorings from Chapter 3. Chapter 6 (Recurrence Relations): This was Chapter 5 in the first edition. New material on DNA sequence alignment has been added as has material on the "transposition average" of permutations. Chapter 7 (The Principle of Inclusion and Exclusion): This was Chapter 6 in the first edition. We have added major new material on cryptography and factoring integers throughout the chapter (and revisited it later in the book). Old Chapter 8 - 1st edition (Pigeonhole Principle): This chapter has been dropped, with important parts of the material added to Chapter 2 and other parts included from time to time throughout the book. Chapter 8 (The Polya Theory of Counting): This was Chapter 7 in the first edition. Some examples based on newly-added Chapter 4 concepts such as weak order run through the chapter. A subsection on automorphisms of graphs has been added and returned to throughout the chapter. Chapter 9 (Combinatorial Designs): Major additions to this chapter include a section on orthogonal arrays and cryptography, including authentication codes and secret sharing. There is also a new section on connections between modular arithmetic and the RSA cryptosystem and one on resolvable designs with applications to secret sharing. A new section on "Group Testing" includes applications to identifying defective products, screening diseases, mapping genomes, and satellite communication. Chapter 10 (Coding Theory): There is a new subsection on "consensus decoding" with connections to finding proteins in molecular sequences and there are added connections of error-correcting codes to compact disks. Material on "reading" DNA to produce proteins is also new. Chapter 11 (Existence Problems in Graph Theory): We have added new subsections to Section 11.2 that deal with the one-way street problem. These new subsections deal with recent results about orientations of square and annular grids reflecting different kinds of cities. We have-added a new subsection on testing for connectedness of truly massive graphs, arising from modern applications involving telecommunications traffic and web data. There is also a new subsection on sequencing DNA by hybridization. Chapter 12 (Matching and Covering): There are many new examples illustrating the concepts of this chapter, including examples involving smallpox vaccinations, sound systems, and oil drilling. We have introduced a new section dealing with stable marriages and their many modern applications, including the assignment of interns to hospitals, dynamic labor markets, and strategic behavior. A section on maximum-weight matching, that was in Chapter 13 of the first edition, has been moved to this chapter. Chapter 13 (Optimization Problems for Graphs and Networks): We have introduced a new subsection on Menger's Theorems. There are also many new examples throughout the chapter, addressing such problems as building evacuation, clustering and data mining, and distributed computing. CONTINUING FEATURES While the second edition has been substantially changed from the first, this edition continues to emphasize the features that make this book unique: Its emphasis on applications from a variety of fields, the treatment of applications as major topics of their own rather than as isolated examples, and the use of applications from the current literature. Many examples, especially ones that tie in new topics with old ones and are revisited throughout the book. An emphasis on problem solving through a variety of exercises that test routine ideas, introduce new concepts and applications, or attempt to challenge the reader to use the combinatorial techniques developed. The book continues to be based on the philosophy that the best way to learn combinatorial mathematics, indeed any kind of mathematics, is through problem solving. A mix of difficulty in topics with careful annotation that makes it possible to use this book in a variety of courses at a variety of levels. An organization that allows the use of the topics in a wide variety of orders, reflecting the somewhat independent nature of the topics in combinatorics while at the same time using to... |
