Invitation to Discrete Mathematics

by Matousek, Jiri; Nesetril, Jaroslav

• ISBN13: 9780198502081
• ISBN10: 0198502087
• Format: Hardcover
• Copyright: 1998-11-12
• Publisher: Oxford University Press

Summary

This book is a clear and self-contained introduction to discrete mathematics, and in particular to combinatorics and graph theory. Aimed at undergraduates and early graduate students in mathematics and computer science, it is written with the goal of stimulating interest in mathematics andencourages an active, problem-solving approach to the material. The reader is led to an understanding of the basic principles and methods of actually doing mathematics. It is more narrowly focused than many discrete mathematics textbooks and treats selected topics in unusual depth and from severalpoints of view. The book reflects the conviction of the authors, active and internationally renowned mathematicians, that the most important gain from studying mathematics is the cultivation of clear and logical thinking and habits, invariably useful for attacking new problems. More than 400exercises, ranging widely in difficulty, and many accompanied by hints for solution, support this approach to teaching. Readers will appreciate the lively and informal style of the text, accompanied by more than 200 drawings and diagrams. Specialists in various parts of science ( with a basicmathematical education) wishing to apply discrete mathematics in their field will find the book a useful source, and even experts in combinatorics may occasionally learn from pointers to research literature or from the presentation of recent results. Invitation to Discrete Mathematics should makedelightful reading both for beginners and mathematical professionals.

Table of Contents

1 Introduction and basic concepts	1	(46)
1.1 An assortment of problems	2	(5)
1.2 Numbers and sets: notation	7	(9)
1.3 Mathematical induction and other proofs	16	(9)
1.4 Functions	25	(7)
1.5 Relations	32	(4)
1.6 Equivalences	36	(4)
1.7 Ordered sets	40	(7)
2 Combinatorial counting	47	(50)
2.1 Functions and subsets	47	(5)
2.2 Permutations and factorials	52	(3)
2.3 Binomial coefficients	55	(11)
2.4 Estimates: an introduction	66	(7)
2.5 Estimates: the factorial function	73	(8)
2.6 Estimates: binomial coefficients	81	(5)
2.7 Inclusion-exclusion principle	86	(5)
2.8 The hatcheck lady & co.	91	(6)
3 Graphs: an introduction	97	(41)
3.1 The notion of a graph; isomorphism	97	(9)
3.2 Subgraphs, components, adjacency matrix	106	(6)
3.3 Graph score	112	(5)
3.4 Eulerian graphs	117	(6)
3.5 An algorithm for an Eulerian tour	123	(4)
3.6 Eulerian directed graphs	127	(5)
3.7 2-connectivity	132	(6)
4 Trees	138	(29)
4.1 Definition and characterizations of trees	138	(6)
4.2 Isomorphism of trees	144	(7)
4.3 Spanning trees of a graph	151	(4)
4.4 The minimum spanning tree problem	155	(6)
4.5 Jarnik's algorithm and Boruvka's algorithm	161	(6)
5 Drawing graphs in the plane	167	(35)
5.1 Drawing in the plane and on other surfaces	167	(7)
5.2 Cycles in planar graphs	174	(7)
5.3 Euler's formula	181	(10)
5.4 Coloring maps: the four-color problem	191	(11)
6 Double-counting	202	(21)
6.1 Parity arguments	202	(9)
6.2 Sperner's theorem on independent systems	211	(7)
6.3 A result in extremal graphy theory	218	(5)
7 The number of spanning trees	223	(17)
7.1 The result	223	(1)
7.2 A proof via score	224	(2)
7.3 A proof with vertebrates	226	(3)
7.4 A proof using the Prufer code	229	(2)
7.5 A proof working with determinants	231	(9)
8 Finite projective planes	240	(22)
8.1 Definition and basic properties	240	(10)
8.2 Existence of finite projective planes	250	(5)
8.3 Orthogonal Latin squares	255	(3)
8.4 Combinatorial applications	258	(4)
9 Probability and probabilistic proofs	262	(32)
9.1 Proofs by counting	262	(7)
9.2 Finite probability spaces	269	(10)
9.3 Random variables and their expectation	279	(6)
9.4 Several applications	285	(9)
10 Generating functions	294	(39)
10.1 Combinatorial applications of polynomials	294	(4)
10.2 Calculation with power series	298	(11)
10.3 Fibonacci numbers and the golden section	309	(8)
10.4 Binary trees	317	(5)
10.5 On rolling the dice	322	(1)
10.6 Random walk	323	(3)
10.7 Integer partitions	326	(7)
11 Applications of linear algebra	333	(30)
11.1 Block designs	333	(5)
11.2 Fisher's inequality	338	(4)
11.3 Covering by complete bipartite graphs	342	(3)
11.4 Cycle space of a graph	345	(4)
11.5 Circulations and cuts: cycle space revisited	349	(4)
11.6 Probabilistic checking	353	(10)
Appendix: Prerequisites from algebra	363	(8)
Bibliography	371	(6)
Hints to selected exercises	377	(22)
Index	399