Graph Theory And Combinatorics Notes

[Ken Reels]

Althoughthe course will be largely divided into two parts (graph theory in the first half and additive combinatorics in the second), we will emphasize the interactions between the two topics and highlight the common themes.

Each student taking the class for credit is expected to write course notes on one (or more, depending on class size) lecture(s). The LaTeX files are hosted on our Overleaf project (registered class participants have received a separate link by email allowing read-write access to the project).

Late policy. Submissions are due on Stellar by midnight of each due date. Late submissions will be penalized by 20% per each late day. For example, for an assignment due on Friday, a submission worth x points if turned in on time will be worth $0.6x$ points if submitted on Sunday.

Here is a somewhat haphazard list of sources on algebraic combinatorics which appear to be suited to undergraduates (I have not personally read most of them, so I am making semi-educated guesses here). My notion of "algebraic combinatorics" includes such things as binomial coefficient identities, symmetric functions, lattice theory, enumerative problems, Young tableaux, determinant identities; it does not include graph theory (except for its most algebraic parts) or extremal combinatorics.

If some of the links below are inaccessible, try adding */ before the link. For example, _online/cgt.pdf would become */ _online/cgt.pdf. This will take you to an archived version of the link (assuming that archive.org has made such a version).

Stanley's EC (Enumerative Combinatorics) is supposed to be a challenging read for graduate students. In its (rather successful) attempt at being encyclopedic, it has very little space for details and leaves a lot to the reader. There are many other texts on combinatorics, and I suspect that the average among them will be easier to read than EC1 (although probably less "from the horse's mouth"). In no particular order:

Richard Stanley, Algebraic Combinatorics. This is still Stanley, but now explicitly writing for undergrads. Unlike EC1-2, this is not trying to survey everything, and so what it does is given more space. The 2nd edition is out already.

Edward A. Bender and S. Gill Williamson, Foundations of Combinatorics with Applications, 2006. This covers both enumeration and graph theory; the specific choice of topics appears tailored to computer scientists.

Bruce Sagan, Combinatorics: The Art of Counting. This is a draft of a book that has been published by AMS in 2020. It is meant for readers "at the advanced undergraduate or beginning graduate level" and appears to assume some knowledge of abstract algebra. Errata.

Geir Helleloid, Algebraic combinatorics (fall 2008). Rough draft of a grad-level course with some newer results. No longer easily found online, but downloadable from gen.lib (as many other books that are not easily found online...).

Kenneth P. Bogart, Combinatorics Through Guided Discovery. (Specifically, the 2017 version is the most up-to-date so far.) This is a heavily introductory text, written as a collection of exercises with ample hints and motivation. (Yes, there is a version with solutions in the tar.gz source archive.) I have seen lots of people use this text in classes, so I assume it's good.

Nicholas A. Loehr, Bijective Combinatorics, 2011. See his website for errata. What little I've seen of this book is great, and I have used it in my teaching. It is one of very few sources defining formal power series properly. There is a 2nd edition out, which is just called Combinatorics and seems to feature new sections on quasisymmetric functions as well as shuffled-around material on power series; your mileage may vary as to whether that update is worth the money.

David R. Mazur, Combinatorics: A Guided Tour, MAA 2010. An introduction into various kinds of combinatorics (including both counting and graph theory). Claims to be graduate-level, although I would place it at (late) undergraduate level based on its content. I have heard good things about it.

Drew Armstrong, Discrete mathematics, 2019. An introductory undergraduate class that includes the basics of enumerative combinatorics (up until Prfer codes for trees) and of graph theory, probably quite appropriate as an appetizer before most of the other texts here. Armstrong writes in an intriguing conversational way that exposes not just proofs but also motivations and thought processes (as well as tidbits of tangential context).

Nicolaas Govert de Bruijn, J. W. Nienhuys, Ling-Ju Hung, Tom Kloks, de Bruijn's Combinatorics. These are notes from a class by de Bruijn himself. Might be terse in places, but probably worth it for the informal classroom style. (The only useful file I've ever found on viXra...)

Peter J. Cameron, Notes on Combinatorics; see also the rest of his notes, including the "St Andrews Notes on Advanced Combinatorics" (errata to part 1). Unfortunately, this has the classical British terseness as far as the proofs are concerned; I wouldn't recommend it for self-learning.

Torsten Ueckerdt, Lecture notes Combinatorics, scribed by Stefan Walzer; see also the class site. (Old version from 2015.) These notes are more suited for grad students due to their brevity, but an undergrad will likely find something of interest in there. Unofficial errata.

Richard A. Brualdi, Introductory Combinatorics, 5th edition 2010. See his website for errata. From what I've seen, a thorough and detailed text with a classical focus (enumeration, flows&cuts, designs).

Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan, Combinatorics: The Rota Way, CUP 2009 is a nonstandard textbook, originating from Rota's MIT classes and reflecting his interests (many of which have never hit the combinatorial mainstream). Errata and a sample chapter.

Carl G. Wagner, Basic Combinatorics. This looks like another introductory set of notes for (enumerative) combinatorics, with a somewhat algebraic touch (generating functions, difference operators and linear recursions are major topics). Also, the first chapter of Carl G. Wagner, Choice, Chance and Inference (a textbook on probability) by the same author treats the very basics of enumerative combinatorics. Finally, the recent book Carl G. Wagner, A First Course in Enumerative Combinatorics (AMS 2020) by the same author goes deeper.

Ian Goulden, Math 249 notes is more detailed than I would have expected given its length and coverage. The first half is an introduction to the uses (including some rather advanced ones) of generating functions; the second is devoted to graph theory.

David Galvin's Math 60610 Spring 2017 lecture notes mostly on enumerative combinatorics. Currently, a more up-to-date version can be found on my website (but probably will go back to David's eventually). This is a grad-level course that should work for sufficiently cultured undergraduates as well.

In Fall 2019, I started writing lecture notes on enumerative combinatorics with the eventual goal of covering all the basics with Bourbakist rigor while remaining reasonably readable. At the moment, the first two chapters are finished; more is to come when I find some time. In Fall 2022, I have also written less detailed notes that, however, go deeper into the subject. I have also started writing introductory lecture notes on algebraic combinatorics in Spring 2021. None of these are fully comprehensive, but together (even excluding the unfinished parts) they should cover a lot. (Also, somewhat informal graph theory notes from Spring 2022.)

I don't know these books/notes well enough to tell which of them are better suited for a first course (although I don't have any reasons to suspect any of them to be unsuitable), but it cannot hurt to try each of them and go as far as you can before meeting serious resistance. (And once you meet serious resistance, either keep going or try the next one.) Half of these are freely available (and so are the other half, if you search in the darker places).

Miklos Bona, Introduction to Enumerative Combinatorics, 2007. This is another Bona book, and explicitly directed at undergraduates, though it does percolate into some advanced topics as well (unimodality, magic square enumeration). A 2nd edition has come out in 2016 under the extended title Introduction to Enumerative and Analytic Combinatorics (adding, as the name change suggests, a chapter on analytic combinatorics). Errata.

Arthur Benjamin and Jennifer Quinn, Proofs that Really Count. This looks rather introductory (focusing on proofs of identities involving binomial coefficients or Fibonacci numbers using bijections). (Suggested by JSchlather.)

Titu Andreescu and Zuming Feng, A Path to Combinatorics for Undergraduates: Counting Strategies. Another introduction to enumerative combinatorics. This one takes a problem-solving approach, illustrating principles on olympiad-style problems. (Suggested by Marko Amnell.)

Dominique Foata and Guo-Niu Han, Principes de Combinatoire Classique, 2008. These are the notes (in French) of a "cursus de la matrise" (equivalent to first year of master's degree) at Strasbourg; they include several subjects not commonly found in introductions (Eulerian polynomials, Lagrange inversion, symmetric functions). Foata is one of the major names in combinatorial enumeration.

Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd edition 1994 (errata). This one is really sui generis and not fully a combinatorics book; it discusses elementary number theory, several important integer sequences, binomial coefficients and their multiple identities (unlike many texts, the focus here is less on bijective proofs and more on algebraic tricks), generating functions and some probability.

Donald E. Knuth, The Art of Computer Programming was started in 1962 as an attempt at a comprehensive textbook for programming. Four volumes are out by now, thus giving computer science its own Song of Ice and Fire to wait on. Combinatorics (enumerative and algorithmic and occasionally even algebraic) is everywhere dense in them (at least in Volumes 1, 3 and 4A), and Knuth's propensity to wildly curious digressions (one gets the impression that he even digresses from digressions) makes these books an incredibly addictive nerd-read. Volume 3 is the one most relevant to algebraic combinatorics, with its 5.1 devoted to permutations and tableaux. Few authors have dug as deep as Knuth into the history of the subject -- witness a draft of 7.2.1.7.

3a8082e126