An Invitation to Discrete Mathematics

by Matousek, Jiri; Nesetril, Jaroslav

• ISBN13: 9780198570431
• ISBN10: 0198570430
• Edition: 2nd
• Format: Hardcover
• Copyright: 2008-12-15
• Publisher: Oxford University Press

Summary

This book is a clear and self-contained introduction to discrete mathematics. Aimed mainly at undergraduate and early graduate students of mathematics and computer science, it is written with the goal of stimulating interest in mathematics and an active, problem-solving approach to the presented material. The reader is led to an understanding of the basic principles and methods of actually doing mathematics (and having fun at that). Being more narrowly focused than many discrete mathematics textbooks and treating selected topics in an unusual depth and from several points 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 useful for attacking new problems. More than 400 enclosed exercises with a wide range of difficulty, many of them accompanied by hints for solution, support this approach to teaching. The 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 basic mathematical education wishing to apply discrete mathematics in their field can use the book as a useful source, and even experts in combinatorics may occasionally learn from pointers to research literature or from presentations of recent results. Invitation to Discrete Mathematics should make a delightful reading both for beginners and for mathematical professionals. The main topics include: elementary counting problems, asymptotic estimates, partially ordered sets, basic graph theory and graph algorithms, finite projective planes, elementary probability and the probabilistic method, generating functions, Ramsey's theorem, and combinatorial applications of linear algebra. General mathematical notions going beyond the high-school level are thoroughly explained in the introductory chapter. An appendix summarizes the undergraduate algebra needed in some of the more advanced sections of the book.

Author Biography

Jiri Matousek received his PhD in Mathematics from the Charles University in Prague in 1990 and is now Professor of Computer Science at Charles University Prague. He has held several visiting positions at universities in the U.S., Germany, Switzerland, Japan, and other countries. Humboldt Research Fellow in 1992 (Free University Berlin). Prize for Young Mathematicians of the 2nd European Congress of Mathematics in Budapest in 1996, speaker at the ICM 1998. Jaroslav Nesetril received his PhD from the Charles University in Prague in 1975 and is now Professor of Mathematics at Charles University Prague. He has held several visiting positions abroad (U.S.A., Canada, Germany). Currently he is the head of the Centre for Theoretical Computer Science (ITI) at Charles University and the director of the international center for Discrete Mathematics, Theoretical Computer Science and Their Applications (DIMATIA).

Table of Contents

Introduction and basic concepts	p. 1
An assortment of problems	p. 2
Numbers and sets: notation	p. 7
Mathematical induction and other proofs	p. 16
Functions	p. 25
Relations	p. 32
Equivalences and other special types of relations	p. 36
Orderings	p. 43
Orderings and how they can be depicted	p. 43
Orderings and linear orderings	p. 48
Ordering by inclusion	p. 52
Large implies tall or wide	p. 55
Combinatorial counting	p. 59
Functions and subsets	p. 59
Permutations and factorials	p. 64
Binomial coefficients	p. 67
Estimates: an introduction	p. 78
Estimates: the factorial function	p. 85
Estimates: binomial coefficients	p. 93
Inclusion-exclusion principle	p. 98
The hatcheck lady & co.	p. 103
Graphs: an introduction	p. 109
The notion of a graph; isomorphism	p. 109
Subgraphs, components, adjacency matrix	p. 118
Graph score	p. 125
Eulerian graphs	p. 130
Eulerian directed graphs	p. 138
2-connectivity	p. 143
Triangle-free graphs: an extremal problem	p. 148
Trees	p. 153
Definition and characterizations of trees	p. 153
Isomorphism of trees	p. 159
Spanning trees of a graph	p. 166
The minimum spanning tree problem	p. 170
Jarník's algorithm and Borůvka's algorithm	p. 176
Drawing graphs in the plane	p. 182
Drawing in the plane and on other surfaces	p. 182
Cycles in planar graphs	p. 190
Euler's formula	p. 196
Coloring maps: the four-color problem	p. 206
Double-counting	p. 217
Parity arguments	p. 217
Sperner's theorem on independent systems	p. 226
An extremal problem: forbidden four-cycles	p. 233
The number of spanning trees	p. 239
The result	p. 239
A proof via score	p. 240
A proof with vertebrates	p. 242
A proof using the Prufer code	p. 245
Proofs working with determinants	p. 247
The simplest proof?	p. 258
Finite projective planes	p. 261
Definition and basic properties	p. 261
Existence of finite projective planes	p. 271
Orthogonal Latin squares	p. 277
Combinatorial applications	p. 281
Probability and probabilistic proofs	p. 284
Proofs by counting	p. 284
Finite probability spaces	p. 291
Random variables and their expectation	p. 301
Several applications	p. 307
Order from disorder: Ramsey's theorem	p. 317
A party of six	p. 318
Ramsey's theorem for graphs	p. 319
A lower bound for the Ramsey numbers	p. 321
Generating functions	p. 325
Combinatorial applications of polynomials	p. 325
Calculation with power series	p. 329
Fibonacci numbers and the golden section	p. 340
Binary trees	p. 348
On rolling the dice	p. 353
Random walk	p. 354
Integer partitions	p. 357
Applications of linear algebra	p. 364
Block designs	p. 364
Fisher's inequality	p. 369
Covering by complete bipartite graphs	p. 373
Cycle space of a graph	p. 376
Circulations and cuts: cycle space revisited	p. 380
Probabilistic checking	p. 384
Appendix: Prerequisites from algebra	p. 395
Bibliography	p. 402
Hints to selected exercises	p. 407
Index	p. 433
Table of Contents provided by Ingram. All Rights Reserved.