英文BOOK Matousek J., Nesetril J.-An invitation to discrete mathematics-OUP (2008)

Invitation to Discrete Mathematics“Only mathematicians could appreciate this work . . . ”Illustration by G.Roux from the Czech edition of Sans dessus dessous byJules Verne, published by J.R. Vilmek, Prague, 1931 (English title: Thepurchase of the North Pole).Invitation to Discrete MathematicsJir Matousek Jaroslav Nesetril2nd edition.13Great Clarendon Street, Oxford OX2 6DPOxford University Press is a department of the University of Oxford.It furthers the Universitys objective of excellence in research, scholarship,and education by publishing worldwide inOxford New YorkAuckland Cape Town Dar es Salaam Hong Kong KarachiKuala Lumpur Madrid Melbourne Mexico City NairobiNew Delhi Shanghai Taipei TorontoWith oces inArgentina Austria Brazil Chile Czech Republic France GreeceGuatemala Hungary Italy Japan Poland Portugal SingaporeSouth Korea Switzerland Thailand Turkey Ukraine VietnamOxford is a registered trade mark of Oxford University Pressin the UK and in certain other countriesPublished in the United Statesby Oxford University Press Inc., New Yorkc Jir Matousek and Jaroslav Nesetril 2008The moral rights of the authors have been assertedDatabase right Oxford University Press (maker)First Published 2008All rights reserved. No part of this publication may be reproduced,stored in a retrieval system, or transmitted, in any form or by any means,without the prior permission in writing of Oxford University Press,or as expressly permitted by law, or under terms agreed with the appropriatereprographics rights organization. Enquiries concerning reproductionoutside the scope of the above should be sent to the Rights Department,Oxford University Press, at the address aboveYou must not circulate this book in any other binding or coverand you must impose the same condition on any acquirerBritish Library Cataloguing in Publication DataData availableLibrary of Congress Cataloging in Publication DataData availableTypeset by Newgen Imaging Systems (P) Ltd., Chennai, IndiaPrinted in Great Britainon acid-free paper byBiddles Ltd., Kings Lynn, NorfolkISBN 9780198570431ISBN 9780198570424 (pbk)1 3 5 7 9 10 8 6 4 2Preface to the second editionThis is the second edition of Invitation to Discrete Mathematics.Compared to the rst edition we have added Chapter 2 on partiallyordered sets, Section 4.7 on Turans theorem, several proofs of theCauchySchwarz inequality in Section 7.3, a new proof of Cayleysformula in Section 8.6, another proof of the determinant formula forcounting spanning trees in Section 8.5, a geometric interpretation ofthe construction of the real projective plane in Section 9.2, and theshort Chapter 11 on Ramseys theorem. We have also made a numberof smaller modications and we have corrected a number of errorskindly pointed out by readers (some of the errors were corrected inthe second and third printings of the rst edition). So readers whodecide to buy the second edition instead of hunting for a used rstedition at bargain price should rest assured that they are gettingsomething extra. . .PragueNovember 2006J. M.J. N.This page intentionally left blankPrefaceWhy should an introductory textbook on discrete mathematics havesuch a long preface, and what do we want to say in it? There are manyways of presenting discrete mathematics, and rst we list some of theguidelines we tried to follow in our writing; the reader may judgelater how we succeeded. Then we add some more technical remarksconcerning a possible course based on the book, the exercises, theexisting literature, and so on.So, here are some features which may perhaps distinguish thisbook from some others with a similar title and subject: Developing mathematical thinking. Our primary aim, besidesteaching some factual knowledge, and perhaps more importantlythan that, is to lead the student to understand and appreciatemathematical notions, denitions, and proofs, to solve problemsrequiring more than just standard recipes, and to express math-ematical thoughts precisely and rigorously. Mathematical habitsmay give great advantages in many human activities, say in pro-gramming or in designing complicated systems.1 It seems thatmany private (and well-paying) companies are aware of this.They are not really interested in whether you know mathemat-ical induction by heart, but they may be interested in whetheryou have been trained to think about and absorb complicatedconcepts quicklyand mathematical theorems seem to providea good workout for such a training. The choice of specic mat-erial for this preparation is probably not essentialif youre en-chanted by algebra, we certainly wont try to convert you tocombinatorics! But we believe that discrete mathematics is esp-ecially suitable for such a rst immersion into mathematics, sincethe initial problems and notions are more elementary than inanalysis, for instance, which starts with quite deep ideas at theoutset.1On the other hand, one should keep in mind that in many other humanactivities, mathematical habits should better be suppressed.viii Preface Methods, techniques, principles. In contemporary university cur-ricula, discrete mathematics usually means the mathematics ofnite sets, often including diverse topics like logic, nite aut-omata, linear programming, or computer architecture. Our texthas a narrower scope; the book is essentially an introduction tocombinatorics and graph theory. We concentrate on relativelyfew basic methods and principles, aiming to display the rich var-iety of mathematical techniques even at this basic level, and thechoice of material is subordinated to this. Joy. The book is written for a reader who, every now andthen, enjoys mathematics, and our boldest hope is that ourtext might help some readers to develop some positive feelingstowards mathematics that might have remained latent so far.In our opinion, this is a key prerequisite: an aesthetic pleasurefrom an elegant mathematical idea, sometimes mixed with a tri-umphant feeling when the idea was dicult to understand orto discover. Not all people seem to have this gift, just as noteveryone can enjoy music, but without it, we imagine, studyingmathematics could be a most boring thing. All cards on the table. We try to present arguments in full andto be mathematically honest with the reader. When we say thatsomething is easy to see, we really mean it, and if the readercant see it then something is probably wrongwe may havemisjudged the situation, but it may also indicate a readers prob-lem in following and understanding the preceding text. When-ever possible, we make everything self-contained (sometimes weindicate proofs of auxiliary results in exercises with hints), andif a proof of some result cannot be presented rigorously andin full (as is the case for some results about planar graphs,say), we emphasize this and indicate the steps that arent fullyjustied. CS. A large number of discrete mathematics students nowadaysare those specializing in computer science. Still, we believe thateven people who know nothing about computers and computing,or nd these subjects repulsive, should have free access to dis-crete mathematics knowledge, so we have intentionally avoidedoverburdening the text with computer science terminology andexamples. However, we have not forgotten computer scientistsand have included several passages on ecient algorithms andPreface ixtheir analysis plus a number of exercises concerning algorithms(see below). Other voices, other rooms. In the material covered, there are sev-eral opportunities to demonstrate concepts from other branchesof mathematics in action, and while we intentionally restrict thefactual scope of the book, we want to emphasize these connec-tions. Our experience tells us that students like such applica-tions, provided that they are done thoroughly enough and notjust by hand-waving.Prerequisites and readership. In most of the book, we do notassume much previous mathematical knowledge beyond a standardhigh-school course. Several more abstract notions that are very com-mon in all mathematics but go beyond the usual high-school level areexplained in the rst chapter. In several places, we need some con-cepts from undergraduate-level algebra, and these are summarizedin an appendix. There are also a few excursions into calculus (enc-ountering notions such as limit, derivative, continuity, and so on),but we believe that a basic calculus knowledge should be generallyavailable to almost any student taking a course related to our book.The readership can include early undergraduate students of math-ematics or computer science with a standard mathematical prepa-ration from high school (as is usual in most of Europe, say), andmore senior undergraduate or early graduate students (in the UnitedStates, for instance). Also nonspecialist graduates, such as biologistsor chemists, might nd the text a useful source. For mathematicallymore advanced readers, the book could serve as a fast introductionto combinatorics.Teaching it. This book is based on an undergraduate course wehave been teaching for a long time to students of mathematics andcomputer science at the Charles University in Prague. The secondauthor also taught parts of it at the University of Chicago, at theUniversity of Bonn, and at Simon Fraser University in Vancouver.Our one-semester course in Prague (13 weeks, with one 90-minutelecture and one 90-minute tutorial per week) typically included mat-erial from Chapters 19, with many sections covered only partiallyand some others omitted (such as 3.6, 4.5 4.5, 5.5, 8.38.5, 9.2).While the book sometimes proves one result in several ways, weonly presented one proof in a lecture, and alternative proofs werex Prefaceoccasionally explained in the tutorials. Sometimes we inserted twolectures on generating functions (Sections 12.112.3) or a lecture onthe cycle space of a graph (13.4).To our basic course outline, we have added a lot of additional (andsometimes more advanced) material in the book, hoping that thereader might also read a few other things besides the sections that arenecessary for an exam. Some chapters, too, can serve as introductionsto more specialized courses (on the probabilistic method or on thelinear algebra method).This type of smaller print is used for “second-level” material, namelythings which we consider interesting enough to include but less essential.These are additional clarications, comments, and examples, sometimeson a more advanced level than the basic text. The main text shouldmostly make sense even if this smaller-sized text is skipped.We also tried to sneak a lot of further related information into theexercises. So even those who dont intend to solve the exercises maywant to read them.On the exercises. At the end of most of the sections, the reader willnd a smaller or larger collection of exercises. Some of them are onlyloosely related to the theme covered and are included for fun andfor general mathematical education. Solving at least some exercisesis an essential part of studying this book, although we know thatthe pace of modern life and human nature hardly allow the reader toinvest the time and eort to solve the majority of the 478 exercisesoered (although this might ultimately be the fastest way to masterthe material covered).Mostly we havent included completely routine exercises requiringonly an application of some given “recipe”, such as “Apply the al-gorithm just explained to this specic graph”. We believe that mostreaders can check their understanding by themselves.We classify the exercises into three groups of diculty (no star,one star, and two stars). We imagine that a good student who hasunderstood the material of a given section should be able to solvemost of the no-star exercises, although not necessarily eortlessly.One-star exercises usually need some clever idea or some slightlymore advanced mathematical knowledge (from calculus, say), andnally two-star exercises probably require quite a bright idea. Almostall the exercises have short solutions; as far as we know, long andtedious computations can always be avoided. Our classication ofdiculty is subjective, and an exercise which looks easy to somePreface ximay be insurmountable for others. So if you cant solve some no-starexercises dont get desperate.Some of the exercises are also marked by CS, a shorthand forcomputer science. These are usually problems in the design of e-cient algorithms, sometimes requiring an elementary knowledge ofdata structures. The designed algorithms can also be programmedand tested, thus providing material for an advanced programmingcourse. Some of the CS exercises with stars may serve (and haveserved) as project suggestions, since they usually require a combi-nation of a certain mathematical ingenuity, algorithmic tricks, andprogramming skills.Hints to many of the exercises are given in a separate chapterof the book. They are really hints, not complete solutions, and al-though looking up a hint spoils the pleasure of solving a problem,writing down a detailed and complete solution might still be quitechallenging for many students.On the literature. In the citations, we do not refer to all sourcesof the ideas and results collected in this book. Here we would liketo emphasize, and recommend, one of the sources, namely a largecollection of solved combinatorial problems by Lovasz 8. This bookis excellent for an advanced study of combinatorics, and also as anencyclopedia of many results and methods. It seems impossible toignore when writing a new book on combinatorics, and, for exam-ple, a signicant number of our more dicult exercises are selectedfrom, or inspired by, Lovasz (less advanced) problems. Biggs 1 is anice introductory textbook with a somewhat dierent scope to ours.Slightly more advanced ones (suitable as a continuation of our text,say) are by Van Lint and Wilson 7 and Cameron 3. The beautifulintroductory text in graph theory by Bollobas 2 was probably writ-ten with somewhat similar goals as our own book, but it proceedsat a less leisurely pace and covers much more on graphs. A very rec-ent textbook on graph theory at graduate level is by Diestel 4. Theart of combinatorial counting and asymptotic analysis is wonderfullyexplained in a popular book by Graham, Knuth, and Patashnik 6(and also in Knuths monograph 41). Another, extensive and mod-ern book on this subject by Flajolet and Sedgewick 5 should go toprint soon. If youre looking for something specic in combinatoricsand dont know where to start, we suggest the Handbook of Combi-natorics 38. Other recommendations to the literature are scatteredxii Prefacethroughout the text. The number of textbooks in discrete mathe-matics is vast, and we only mention some of our favorite titles.On the index. For most of the mathematical terms, especially thoseof general signicance (such as relation, graph), the index only refersto their denition. Mathematical symbols composed of Latin letters(such as Cn) are placed at the beginning of the appropriate letterssection. Notation including special symbols (such as X Y , G = H)and Greek letters are listed at the beginning of the index.Acknowledgments. A preliminary Czech version of this book wasdeveloped gradually during our teaching in Prague. We thank ourcolleagues in the Department of Applied Mathematics of the CharlesUniversity, our teaching assistants, and our students for a stimulatingenvironment and helpful comments on the text and exercises. Inparticular, Pavel Socha, Eva Matouskova, Tomas Holan, and RobertBabilon discovered a number of errors in the Czech version. MartinKlazar and Jir Otta compiled a list of a few dozen problems andexercises; this list was a starting point of our collection of exercises.Our colleague Jan Kratochvl provided invaluable remarks based onhis experience in teaching the same course. We thank Tomas Kaiserfor substantial help in translating one chapter into English. AdamDingle and Tim Childers helped us with some comments on theEnglish at early stages of the translation. Jan Nekovar was so kindas to leave the peaks of number theory for a moment and providepointers to a suitable proof of Fact 12.7.1.Several people read parts of the English version at various stagesand provided insights that would probably never have occurred tous. Special thanks go to Je Stopple for visiting us in Prague, care-fully reading the whole manuscript, and sharing some of his teachingwisdom with us. We are much indebted to Mari Inaba and HelenaNesetrilova for comments that were very useful and dierent fromthose made by most of other people. Also opinions in several rep-orts obtained by Oxford University Press from anonymous refereeswere truly helpful. Most of the nishing and polishing work on thebook was done by the rst author during a visit to the ETH Zurich.Emo Welzl and the members of his group provided a very pleasantand friendly environment, even after they were each asked to readthrough a chapter, and so the help of Hans-Martin Will, Beat Tra-chsler, Bernhard von Stengel, Lutz Kettner, Joachim Giesen, BerndPreface xiiiGartner, Johannes Blomer, and Artur Andrzejak is gratefully ack-nowledged. We also thank Hee-Kap Ahn for reading a chapter.Many readers have contributed to correcting errors from the rstprinting. A full list can be found at the web page with errata men-tioned below; here we just mention Mel Hausner, Emo Welzl, HansMielke, and Bernd Bischl as particularly signicant contributors tothis eort.Next, we would like to thank Karel Horak for several expert sug-gestions helping the rst author in his struggle with the layout ofthe book (unfortunately, the times when books used to be typesetby professional typographers seem to be over), and Jana Chlebkovafor a long list of minor typographic corrections.Almost all the gures were drawn by the rst author using thegraphic editor Ipe 5.0. In the name of humankind, we thank OtfriedCheon