Discrete Mathematics

Authors : László Lovász and Katalin Vesztergombi, Yale University
Publication Date : Spring 1999

Document Excerpts:

There are many success stories of applied mathematics outside calculus. A recent hot topic is mathematical cryptography, which is based on number theory (the study of positive integers 1,2,3,...), and is widely applied, among others, in computer security and electronic banking. Other important areas in applied mathematics include linear programming, coding theory, theory of computing. The mathematics in these applications is collectively called discrete mathematics. ("Discrete" here is used as the opposite of "continuous"; it is also often used in the more restrictive sense of "finite".)

The aim of this book is not to cover "discrete mathematics" in depth (it should be clear from the description above that such a task would he ill-defined and impossible anyway). Rather, this book discusses a number of selected results and methods, mostly from the areas of combinatorics, graph theory, and combinatorial geometry, with a little elementary number theory.

At the same time, it is important to realize that mathematics cannot be done without proofs. Merely stating the facts, without, saying something about why these facts are valid, would be terribly far from the spirit of mathematics and would make it impossible to give any idea about how it works. Thus, wherever possible, this book will give the proofs of the theorems stated. Sometimes this is not possible; quite simple, elementary facts can be extremely difficult to prove, and some such proofs may take advanced courses to go through. In these cases, this book will state at least that the proof is highly technical and goes beyond the scope of this book.

Another important, ingredient of mathematics is problem solving. One won't be able to learn any mathematics without dirtying his hands and trying out the ideas he learn about in the solution of problems. To some, this may sound frightening, but in fact most people pursue this type of activity almost, every day: everybody who plays a game of chess, or solves a puzzle, is solving discrete mathematical problems. The reader is strongly advised to answer the questions posed in the text and to go through the problems at the end of each chapter of this book.

View/Download Discrete Mathematics