László Lovász - Discrete Mathematics: Elementary and Beyond

Discrete Mathematics: Elementary and Beyond — read online for free the complete book (whole text) full work

Below is the text of the book, divided by pages. System saving the place of the last page read, allows you to conveniently read the book "Discrete Mathematics: Elementary and Beyond" online for free, without having to search again every time where you left off. Put a bookmark, and you can go to the page where you finished reading at any time.

Light

Font size:

↓

↑

Georgia Tahoma Arial Verdana

Reset

Interval:

↓

↑

Bookmark:

Make

1234567...78

ISSN 0172-6056

ISBN 978-0-387-95585-8 ISBN 978-0-387-21777-2 (eBook)

DOI 10.1007/978-0-387-21777-2

Springer Science+Business Media, LLC 2003

All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden.

The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.

www.springer.com

Preface

For most students, the first and often only course in college mathematics is calculus. It is true that calculus is the single most important field of mathematics, whose emergence in the seventeenth century signaled the birth of modern mathematics and was the key to the successful applications of mathematics in the sciences and engineering.

But calculus (or analysis) is also very technical. It takes a lot of work even to introduce its fundamental notions like continuity and the derivative (after all, it took two centuries just to develop the proper definition of these notions). To get a feeling for the power of its methods, say by describing one of its important applications in detail, takes years of study.

If you want to become a mathematician, computer scientist, or engineer, this investment is necessary. But if your goal is to develop a feeling for what mathematics is all about, where mathematical methods can be helpful, and what kinds of questions do mathematicians work on, you may want to look for the answer in some other fields of mathematics.

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 the positive integers 1, 2, 3, ...), and is widely applied, for example, in computer security and electronic banking. Other important areas in applied mathematics are linear programming, coding theory, and the theory of computing. The mathematical content in these applications is collectively called discrete mathematics . (The word discrete is used in the sense of separated from each other, the opposite of continuous; it is also often used in the more restrictive sense of finite. The more everyday version of this word, meaning circumspect, is spelled discreet.)

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 be ill-defined and impossible anyway). Rather, we discuss a number of selected results and methods, mostly from the areas of combinatorics and graph theory, with a little elementary number theory, probability, and combinatorial geometry.

It is important to realize that there is no mathematics 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, we will give the proofs of the theorems we state. 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, we will at least state that the proof is highly technical and goes beyond the scope of this book.

Another important ingredient of mathematics is problem solving . You wont be able to learn any mathematics without dirtying your hands and trying out the ideas you 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. Treat it as puzzle solving, and if you find that some idea that you came up with in the solution plays some role later, be satisfied that you are beginning to get the essence of how mathematics develops.

We hope that we can illustrate that mathematics is a building, where results are built on earlier results, often going back to the great Greek mathematicians; that mathematics is alive, with more new ideas and more pressing unsolved problems than ever; and that mathematics is also an art, where the beauty of ideas and methods is as important as their difficulty or applicability.

Lszl Lovsz

Jzsef Pelikn

Katalin Vesztergombi

Table of Contents

1
Lets Count!

L. Lovsz 1

(1)

Microsoft Research, Microsoft Corporation, One Microsoft Way, Redmond, WA, 98052-6399, USA

(2)

Department of Algebra and Number Theory, Etvs Lornd University, Pzmny Pter Stany 1/C, Budapest, H-1117, Hungary

(3)

Department of Mathematics, University of Washington, Box 354-350, Seattle, WA, 98195-4350, USA

L. Lovsz

Email:

J. Pelikn

Email:

K. Vesztergombi

Email:

1.1 A Party

Alice invites six guests to her birthday party: Bob, Carl, Diane, Eve, Frank, and George. When they arrive, they shake hands with each other (strange European custom). This group is strange anyway, because one of them asks, How many handshakes does this mean?

I shook 6 hands altogether, says Bob, and I guess, so did everybody else.

Since there are seven of us, this should mean 7 6 = 42 handshakes, ventures Carl.

This seems too many says Diane. The same logic gives 2 handshakes if two persons meet, which is clearly wrong.

This is exactly the point: Every handshake was counted twice. We have to divide 42 by 2 to get the right number: 21, with which Eve settles the issue.

When they go to the table, they have a difference of opinion about who should sit where. To resolve this issue, Alice suggests, Lets change the seating every half hour, until we get every seating.

But you stay at the head of the table, says George, since it is your birthday.

How long is this party going to last? How many different seatings are there (with Alices place fixed)?

Let us fill the seats one by one, starting with the chair on Alices right. Here we can put any of the 6 guests. Now look at the second chair. If Bob sits in the first chair, we can put any of the remaining 5 guests in the second chair; if Carl sits in the first chair, we again have 5 choices for the second chair, etc. Each of the six choices for the first chair gives us five choices for the second chair, so the number of ways to fill the first two chairs is 5 + 5 + 5 + 5 + 5 + 5 = 6 5 = 30. Similarly, no matter how we fill the first two chairs, we have 4 choices for the third chair, which gives 6 5 4 ways to fill the first three chairs. Proceeding similarly, we find that the number of ways to seat the guests is 6 5 4 3 2 1 = 720.

If they change seats every half hour, it will take 360 hours, that is, 15 days, to go through all the seating arrangements. Quite a party, at least as far as the duration goes!

Next page

1234567...78

Light

Font size:

↓

↑

Georgia Tahoma Arial Verdana

Reset

Interval:

↓

↑

Bookmark:

Make

Similar books «Discrete Mathematics: Elementary and Beyond»

Look at similar books to Discrete Mathematics: Elementary and Beyond. We have selected literature similar in name and meaning in the hope of providing readers with more options to find new, interesting, not yet read works.

Sergei Kurgalin [Сергей Кургалин]

The Discrete Math Workbook: A Companion Manual Using Python, 2nd Edition

Jon Pierre Fortney

Discrete Mathematics for Computer Science: An Example-Based Introduction

Gerard ORegan

Guide to Discrete Mathematics: An Accessible Introduction to the History, Theory, Logic and Applications (Texts in Computer Science)

Ferland

Discrete Mathematics and Applications

Pinsky

Problems from the discrete to the continuous: probability, number theory, graph theory, and combinatorics

Bagdasar

Concise Computer Mathematics: Tutorials on Theory and Problems

Karoly Bezdek

Volumetric Discrete Geometry (Discrete Mathematics and Its Applications)

Steven Krantz

Discrete Mathematics DeMYSTiFied

Donald Bindner

Mathematics for the Liberal Arts

Stephen B. Maurer

Discrete Algorithmic Mathematics, Third Edition

V. K . Balakrishnan

Introductory Discrete Mathematics

Martin J. Erickson

Introduction to Combinatorics

Discussion, reviews of the book Discrete Mathematics: Elementary and Beyond and just readers' own opinions. Leave your comments, write what you think about the work, its meaning or the main characters. Specify what exactly you liked and what you didn't like, and why you think so.