Applied Combinatorics 2016 Edition Mitchel T. KellerWilliam T. Trotter Applied Combinatorics Applied Combinatorics Mitchel T. Keller Washington and Lee University Lexington, Virginia William T. Trotter Georgia Institute of Technology Atlanta, Georgia 2016 Edition Edition: 2016Edition Website: http://rellek.net/appcomb/ ©2006–2016 MitchelT.Keller,WilliamT.Trotter ThisworkislicensedundertheCreativeCommonsAttribution-ShareAlike4.0Interna- tionalLicense. Toviewacopyofthislicense,visithttp://creativecommons.org/licenses/ by-sa/4.0/ or send a letter to Creative Commons, PO Box 1866, Mountain View, CA 94042,USA. Summary of Contents About the Authors vii Acknowledgements ix Preface xi Preface to 2016 Edition xiii Prologue 1 1 An Introduction to Combinatorics 3 2 Strings, Sets, and Binomial Coefficients 17 3 Induction 39 4 Combinatorial Basics 59 5 Graph Theory 69 6 Partially Ordered Sets 113 7 Inclusion-Exclusion 141 8 Generating Functions 157 9 Recurrence Equations 179 10 Probability 207 11 Applying Probability to Combinatorics 223 12 Graph Algorithms 233 13 Network Flows 253 vii SUMMARYOFCONTENTS 14 Combinatorial Applications of Network Flows 273 15 Pólya’s Enumeration Theorem 287 16 The Many Faces of Combinatorics 309 A Epilogue 325 B Background Material for Combinatorics 327 C List of Notation 355 Index 357 viii About the Authors About William T. Trotter William T. Trotter is a Professor in the School of Mathematics at Georgia Tech. He was first exposed to combinatorial mathematics through the 1971 Bowdoin Combi- natoricsConferencewhichfeaturedanarrayofsuperstarsofthatera,includingGian CarloRota,PaulErdős,MarshallHall,HerbRyzer,HerbWilf,WilliamTutte,RonGra- ham, Daniel Kleitman and Ray Fulkerson. Since that time, he has published more than120researchpapersongraphtheory,discretegeometry,Ramseytheory,andex- tremal combinatorics. Perhaps his best known work is in the area of combinatorics and partially ordered sets, and his 1992 research monograph on this topic has been veryinfluential. (Hetakessomeprideinthefactthatthismonographisstillinprint andcopiesarebeingsoldin2016.) Hehasmorethan70co-authors,butconsidershis extensivejointworkwithGrahamBrightwell,StefanFelsner,PeterFishburn,HalKier- steadandEndreSzemerèdiasrepresentinghisbestwork. Hiscareerincludesinvited presentationsatmorethan50internationalconferencesandmorethan30meetingsof professionalsocieties. HewasthefoundingeditoroftheSIAMJournalonDiscreteMath- ematicsandhasservedontheEditorialBoardofOrdersincethejournalwaslaunched in 1984, and his service includes an eight year stint as Editor-in-Chief. Currently, he servesontheeditorialboardsofthreeotherjournalsincombinatorialmathematics. Stillhehashisquirks. First,heinsistsonbeingcalled“Tom”,asThomasishismiddle name, while continuing to sign as William T. Trotter. Second, he has invested time andenergyserving fiveterms as department/school chair, oneat GeorgiaTech, two atArizonaStateUniversityandtwoattheUniversityofSouthCarolina. Inaddition, he has served as a Vice Provost and as an Assistant Dean. Third, he is fascinated by computeroperatingsystemsandisalwaysinstallingnewones. Inoneparticularweek, heputelevendifferentflavorsofLinuxonthesamemachine,interspersedwithfour completeinstallsofWindows7. Incidentally,theentireprocessstartedandendedwith Windows7. Fourth,helikestohitgolfballs,notplaygolf,justhitballs. Withoutthese diversions,hemightevenhavehadenoughtimetosettletheRiemannhypothesis. HehashadelevenPh.D.students,oneofwhichisnowhisco-authoronthistext. ix AbouttheAuthors About Mitchel T. Keller Mitchel T. Keller is a super-achiever (this description is written by WTT) extraordi- nairefromNorthDakota. AsagraduatestudentatGeorgiaTech,hewonalengthylist ofhonorsandawards,includingaVIGREGraduateFellowship,anIMPACTScholar- ship,aJohnR.FestaFellowshipandthe2009PriceResearchAward. Mitchisanatural leader and was elected President (and Vice President) of the Georgia Tech Graduate StudentGovernmentAssociation, rolesinwhichheservedwithdistinction. Indeed, aftercompletinghisterms,hisstudentcolleaguesvotedtoestablishacontinuingaward fordistinguishedleadership,tobenamedtheMitchelT.Kelleraward,withMitchas thefirstrecipient. Veryfewgraduatestudentswinawardsinthefirstplace,butMitch istheonlyoneIknowwhohasanawardnamedafterthem. Mitchisalsoagiftedteacherofmathematics,receivingtheprestigiousGeorgiaTech 2008OutstandingTeacherAward,acampus-widecompetition. Heisquicktoexper- iment with the latest approaches to teaching mathematics, adopting what works for himwhilerefiningandpolishingthingsalongtheway. Hereallyunderstandsthelit- eraturebehindactivelearningandtheprinciplesofengagingstudentsinthelearning process. Mitchhaseventaughthismoresenior(somesayancient)co-authorathing ortwoandgothimtotrypersonalresponsesystemsinalargecalculussection. Mitchisofftoafaststartinhisownresearchcareer,andisalreadyanexpertinthe subjectoflineardiscrepancy. Mitchhasalsomadesubstantivecontributionstoatopic knownasStanleydepth,whichisrightattheboundaryofcombinatorialmathematics andalgebraiccombinatorics. AfterfinishinghisPh.D.,Mitchreceivedanothersignalhonor,aMarshallSherfield PostdoctoralFellowshipandspenttwoyearsattheLondonSchoolofEconomics. He ispresentlyanAssistantProfessorofMathematicsatWashingtonandLeeUniversity, andafewyearsdowntheroad,he’llprobablybepresidentofsomething. Onthepersonalside,MitchisthekeeperoftheMathematicsGenealogyProject,and heisagreatcook. Hisdessertsaretodiefor. x