Hardcover(3rd ed.)
-
SHIP THIS ITEMAvailable for Pre-Order. This item will be released on August 14, 2024PICK UP IN STORE
Store Pickup available after publication date.
Available within 2 business hours
Related collections and offers
Overview
Product Details
| ISBN-13: | 9781032816524 |
|---|---|
| Publisher: | CRC Press |
| Publication date: | 08/14/2024 |
| Series: | Discrete Mathematics and Its Applications |
| Edition description: | 3rd ed. |
| Pages: | 766 |
| Product dimensions: | 7.00(w) x 10.00(h) x 0.00(d) |
About the Author
Fred S. Roberts is Professor of Mathematics and Director of DIMACS at Rutgers University.
Barry Tesman is Professor of Mathematics at Dickinson College.
Table of Contents
Notation.1. What is Combinatorics?
I. The Basic Tools of Combinatorics.
2. Basic Counting Rules3. Introduction to Graph Theory.
II. The Counting Problem.
4. Generating Functions and Their Applications.5. Recurrence Relations.
7. The Polya Theory of Counting.
III. The Existence Problem.
8. The Pigeonhole Principle and its Generalizations.9. Experimental Design.
10. Coding Theory.
11. Existence Problems in Graph Theory.
IV. Combinatorial Optimization.
12. Matching and Covering.13. Optimization Problems for Graphs and Networks.
Answers to Selected Exercises.
Author Index.
Subject Index.
What People are Saying About This
The book has been substantially rewritten with more than 200 pages of new materials and many changes in the exercises. There are also many new examples to reflect the new developments in computer science and biology since 1990. … Many important topics are covered and they are done in detail. This book is one of the rare ones that does the job really well. … I strongly endorse this book. It is suitable for motivated math, computer science or engineering sophomores and even beginning graduate students. In fact bright high school students would love this book and if they are exposed early (through reading this book and being guided by their teachers), many of them might end up doing combinatorics for their careers! I really love this book. It is a gem.
—IACR Book Reviews, 2011
… the overall organization is excellent. … Many inviting exercises are included. They cover both theoretical aspects and practical problems from state-of-the-art scientific research in various areas, such as biology and telecommunications. … I can heartily recommend expanding your library with a copy of this work. It is so much fun to just open the book at random and explore the material that jumps out of the pages.
—Computing Reviews, March 2010
This is an overwhelmingly complete introductory textbook in combinatorics. It not only covers nearly every topic in the subject, but gives several realistic applications for each topic. … much more breadth than its competitors. …valuable as a source of applications and for enrichment reading.
—MAA Reviews, December 2009
The writing style is excellent. … The explanations are detailed enough that the students can follow the arguments readily. The motivating examples are a truly strong point for the text. No other text with which I am familiar comes even close to the number of applications presented here.
—John Elwin, San Diego State University, California, USA
This book is a required textbook for my graduate course in discrete mathematics. Both my students and I have found it to be an excellent resource with interesting application examples from a variety of fields interspersed throughout the text. The book is very well organized and clearly reinforces both the practical and theoretical understanding in a way students are able to correlate. Because the level of difficulty for selected problems range from simple to challenging, it makes an appropriate text for junior, senior, and graduate students alike. I am particularly pleased with the relevancy and inclusion of computer science applications … .
—Dawit Haile, Virginia State University, Petersburg, USA
Roberts and Tesman’s book covers all the major areas of combinatorics in a clear, insightful fashion. But what really sets it apart is its impressive use of applications. I know of no other text which comes close. There are entire sections devoted to subjects like computing voting power, counting organic compounds built up from benzene rings, and the use of orthogonal arrays in cryptography. And in exercises and examples, students test psychic powers, consider the UNIX time problem, plan mail carriers’ routes, and assign state legislators to committees. This really helps them to understand the mathematics and also to see how this field is useful in the real world.
—Thomas Quint, University of Nevada, Reno, USA
Introduction
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 toemphasize 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 topics from different chapters to reinforce each other.
THE ORGANIZATION OF THE BOOK
The book is divided into four parts. The first part (Chapters 2, 3, and 4) introduces the basic tools of combinatorics and their applications. It introduces fundamental counting rules and the tools of graph theory and relations. The remaining three parts are organized around the three basic problems of combinatorics: the counting problem, the existence problem, and the optimization problem. These problems are discussed in Chapter 1. Part II of the book is concerned with more advanced tools for dealing with the counting problem: generating functions, recurrences, inclusion/exclusion, and Polya Theory. Part III deals with the existence problem. It discusses combinatorial design, coding theory, and special problems in graph theory. It also begins a series of three chapters on graphs and networks (Chapters 11-13) and begins an introduction to graph algorithms. Part IV deals with combinatorial optimization, illustrating the basic ideas through a continued study of graphs and networks. It begins with a transitional chapter on matching and covering that starts with the existence problem and ends with the optimization problem. Then Part IV ends with a discussion of optimization problems for graphs and networks. The division of the book into four parts is somewhat arbitrary, and many topics illustrate several different aspects of combinatorics, for instance both existence and optimization questions. However, dividing the book into four parts seemed to be a reasonable way to organize the large amount of material that is modern combinatorics.
PREREQUISITES
This book can be used at a variety of levels. Most of the book is written for a junior/senior audience, in a course populated by math and computer science majors and nonmajors. It could also be appropriate for sophomores with sufficient mathematical maturity. (Topics that can be omitted in elementary treatments are indicated throughout.) On the other hand, at a fast pace, there is more than enough material for a challenging graduate course. In the undergraduate courses for which the material has been used at Rutgers, the majority of the enrollees come from mathematics and computer science, and the rest from such disciplines as business, economics, biology, and psychology. At Dickinson, the material has been used primarily for junior/senior-level mathematics majors. The prerequisites for these courses, and for the book, include familiarity with the language of functions and sets usually attained by taking at least one course in calculus. Infinite sequences and series are used in Chapters 5 and 6 (though much of Chapter 6 uses only the most elementary facts about infinite sequences, and does not require the notion of limit). Other traditional topics of the calculus are not needed. However, the mathematical sophistication attained by taking a course like calculus is a prerequisite. Also required are some tools of linear algebra, specifically familiarity with matrix manipulations. An understanding of mathematical induction is also assumed. (There are those instructors who will want to review mathematical induction in some detail at an early point in their course, and who will want to quickly review the language of sets.) A few optional sections of the book require probability beyond what is developed in the text. Other sections introduce topics in modern algebra, such as groups and finite fields. These sections are self-contained, but they would be too fast-paced for a student without sufficient background.
ALGORITHMS
Many parts of the book put an emphasis on algorithms. This is inevitable, as combinatorics is increasingly connected to the development of precise and efficient procedures for solving complicated problems, and because the development of combinatorics is so closely tied to computer science. Our aim is to introduce students to the notion of an algorithm and to introduce them to some important examples of algorithms. For the most part, we have adopted a relatively informal style in presenting algorithms. The style presumes little exposure to the notion of an algorithm and how to describe it. The major goal is to present the basic idea of a procedure, without attempting to present it in its most concise or most computer-oriented form. There are those who will disagree with this method of presenting algorithms. Our own view is that no combinatorics course is going to replace the learning of algorithms. The computer science student needs a separate course in algorithms that includes discussion of implementing the data structures for the algorithms presented. However, all students of combinatorics need to be exposed to the idea of algorithm, and to the algorithmic way of thinking, a way of thinking that is so central and basic to the subject. We realize that our compromise on how to present algorithms will not make everyone happy. However, it should be pointed out that for students with a background in computer science, it would make for interesting, indeed important, exercises to translate the informal algorithms of the text into more precise computer algorithms or even computer programs.
ROLE OF EXAMPLES AND APPLICATIONS
Applications play a central role in this book and are a feature that makes the book unique among combinatorics books. The instructor is advised to pick and choose among the applications or to assign them for outside reading. Many of the applications are presented as Examples that are returned to as the book progresses. It is not necessary for either the instructor or the student to be an expert in the area of application represented in the various examples and subsections of the book. They tend to be self-contained and, when not, should be readily understood with some appropriate searching of the Internet.
The connection between combinatorics and computer science is well understood and vitally important and does not need specific emphasis in this discussion.
Of particular importance in this book are examples from the biological sciences. Our emphasis on such examples stems from our observation that the connection between the biological and the mathematical sciences is growing extremely fast. Methods of mathematics and computer science have played and are playing a major role in modern biology, for example in the "human genome project" and in the modeling of the spread of disease. Increasingly, it is vitally important for mathematical scientists to understand such modern applications and also for students of the biological sciences to understand the importance for their discipline of mathematical methods such as combinatorics. This interdisciplinarity is reflected in the growing number of schools that have courses or programs at the interface between the mathematical and the biological sciences.
While less advanced than th6 connection between the mathematical and the biological sciences, the connection between the mathematical and the social sciences is also growing rapidly as more and more complex problems of the social sciences are tackled using tools of computer science and mathematical modeling. Thus, we have introduced a variety of applications that arise from the social sciences, with an emphasis on decision-making and voting.
PROOFS
Proving things is an essential aspect of mathematics that distinguishes it from other sciences. Combinatorics can be a wonderful mechanism for introducing students to the notion of mathematical proof and teaching them how to write good proofs. Some schools use the combinatorics course as the introduction to proofs course. That is not our purpose with this book. While the instructor using this book should include proofs, we tend to treat proofs as rather informal and do not put emphasis on writing them. Many of the harder proofs in the book are starred as optional.
EXERCISES
The exercises play a central role in this book. They test routine ideas, introduce new concepts and applications, and attempt to challenge the reader to use the combinatorial techniques developed in the text. It is the nature of combinatorics, indeed the nature of most of mathematics, that it is best mastered by doing many problems. We have tried to include a wide variety of both applied and theoretical exercises, of varying degrees of difficulty, throughout the book.
WAYS TO USE THE BOOK IN VARIOUS SETTINGS
This book is appropriate for a variety of courses at a variety of levels. We have both used the material of the book for several courses, in particular a one-semester course entitled Combinatorics and a one-semester course entitled Applied Graph Theory. The combinatorics course, taught to juniors and seniors, covers much of the material of Chapters 1, 2, 3, 5, 6, 7, 9, and 10, omitting the sections indicated by footnotes in the text. (These are often proofs.) At Rutgers, a faster-paced course, that Fred Roberts has used with first year graduate students, puts more emphasis on proofs, includes many of the optional sections, and also covers the material either of Chapter 8 or Chapter 12. In either an undergraduate or a graduate course, the instructor could also substitute for Chapters 9 and 10 either Chapter 8 or Chapter 11 and parts of Chapters 12 and 13. Including Chapter 11 is especially recommended at institutions that do not have a separate course in graph theory. Similarly, including parts of Chapter 13 is especially recommended for institutions that do not have a course in operations research. At Rutgers, there are separate (both undergraduate and graduate) courses that cover much of the material of Chapters 11 to 13.
Other one-semester or one-quarter courses could be designed from this material, as most of the chapters are relatively independent. (See the discussion below.) At Rutgers, the applied graph theory course that is taught is built around Chapters 3 and 11, supplemented with graph-theoretical topics from the rest of the book (Chapters 4, 12, and 13) and elsewhere. (A quick treatment of Sections 2.1 through 2.7, plus perhaps Section 2.18, is needed background.) Chapters 3, 11, 12, and 13 would also be appropriate for a course introducing graph algorithms or a course called Graphs and Networks. The entire book would make a very appropriate one-year introduction to modern combinatorial mathematics and its applications. A course emphasizing applications of combinatorics for those who have previously studied combinatorics could be constructed out of the applied subsections and examples in the text.
This book could be used for a one-semester or one-quarter sophomore-level course. Such a course would cover much of Chapters 1, 2, and 3, skip Chapters 4 and 5, and cover only Sections 6.1 and 6.2 of Chapter 6. It would then cover Chapter 7 and parts of Chapter 11. Starred sections and most proofs would be omitted. Other topics would be added at the discretion of the instructor.
DEPENDENCIES AMONG TOPICS AND ORDERS IN WHICH TO USE THE BOOK
In organizing any course, the instructor will wish to take note of the relative independence of the topics here. There is no well-accepted order in which to present an introduction to the subject matter of combinatorics, and there is no universal agreement on the topics that make up such an introduction. We have tried to write this book in such a way that the chapters are quite independent and can be covered in various orders.
Chapter 2 is basic to the book. It introduces the basic counting rules that are used throughout. Chapter 3 develops just enough graph theory to introduce the subject. It emphasizes graph-theoretical topics that illustrate the counting rules developed in Chapter 2. The ideas introduced in Chapter 3 are referred to in places throughout the book, and most heavily in Chapters 4, 11, 12, and 13. It is possible to use this book for a one-semester or one-quarter course in combinatorics without covering Chapter 3. However, in our opinion, at least the material on graph coloring (Sections 3.3 and 3.4) should be included. The major dependencies beyond Chapter 3 are that Chapter 4 depends on Chapter 3; Chapter 6 after Section 6.2 depends on Chapter 5; Chapter 7 refers to examples developed in Chapters 3 and 6; Chapters 11, 12, and 13 depend on Chapter 3; and Section 10.5 depends on Chapter 9. Ideas from Chapter 12 are used in Chapter 13, Section 13.3.8.
COMBINATORICS IS RAPIDLY CHANGING
Finally, it should be emphasized that combinatorics is a rapidly growing subject and one whose techniques are being rapidly developed and whose applications are being rapidly explored. Many of the topics presented here are close to the frontiers of research. It is typical of the subject that it is possible to bring a newcomer to the frontiers very quickly. We have tried to include references to the literature of combinatorics and its applications that will allow the interested reader to delve more deeply into the topics discussed here.