Applied Combinatorics (2017)

William T. Trotter, a Professor of Mathematics at Georgia Tech, has made significant contributions to the field of combinatorial mathematics. His journey began at the 1971 Bowdoin Combinatorics Conference, where he encountered leading figures like Gian-Carlo Rota, Paul Erdős, and others. Since then, he's authored over 120 research papers covering graph theory, discrete geometry, Ramsey theory, and extremal combinatorics. His most recognized work centers on combinatorics and partially ordered sets (posets), evidenced by his influential 1992 research monograph which remains in print as of 2016. He boasts over 70 co-authors and particularly values collaborations with Graham Brightwell, Stefan Felsner, Peter Fishburn, Hal Kierstead, and Endre Szemerédi. His extensive career includes numerous invited presentations at both international conferences and professional society meetings; he was the founding editor of the SIAM Journal on Discrete Mathematics, served an eight-year term as Editor-in-Chief of the journal Order (since its 1984 launch), and currently sits on the editorial boards of three additional combinatorial mathematics journals. Beyond his academic achievements, he's held administrative positions including department/school chair roles at Georgia Tech, Arizona State University, and the University of South Carolina, as well as serving as a Vice Provost and Assistant Dean. His personal interests include a fascination with computer operating systems (notably installing various Linux distributions and Windows versions) and hitting golf balls.

Mitchel T. Keller is described as a 'super-achiever extraordinaire' from North Dakota. During his graduate studies at Georgia Tech, he accumulated a remarkable list of honors and awards, including a VIGRE Graduate Fellowship, an IMPACT Scholarship, a John R. Festa Fellowship, and the 2009 Price Research Award. His leadership abilities were evident in his roles as President and Vice President of the Georgia Tech Graduate Student Government Association, leading to the establishment of the Mitchel T. Keller Award for distinguished leadership, with him as its first recipient. This unique achievement highlights his exceptional contributions as a graduate student. The text notes that the intended audience for the book is familiar with linear algebra concepts such as vector spaces, bases, and dimension, indicating a certain level of mathematical background expected for the course.

MATH 3012: Applied Combinatorics, a junior-level course at Georgia Tech, is primarily designed for students pursuing a Bachelor of Science (B.S.) in Computer Science. The course aims to provide a broad understanding of combinatorial mathematics through the use of applications, which serve to highlight fundamental concepts and techniques. However, the course is not solely for computer science majors; it's also a requirement for B.S. in Mathematics students and is one of two options available to computer engineering students to fulfill a breadth requirement. The course often attracts students from other engineering and science disciplines interested in expanding their mathematical knowledge. As a result, around 250 Georgia Tech students typically enroll each semester. Students entering the course have already completed a three-semester calculus sequence, with many having bypassed one or more semesters based on advanced placement scores. The text acknowledges areas needing further refinement but highlights the incorporation of SageMath, an open-source computer algebra system, to assist with algebraic computations and to create interactive learning experiences for students using the HTML version.

The course's approach focuses on demonstrating the practical applications and inherent beauty of combinatorics, particularly within computer science contexts. While proofs are periodically covered, the primary goal isn't proof writing instruction (as that's handled in other required courses). Students will be asked to prove minor facts; however, the rigor level is comparable to that expected in second or third-semester calculus rather than advanced mathematics courses. Despite this, the textbook avoids oversimplification, allowing for more rigorous instruction if desired by the instructor. The textbook's 2017 edition built upon the previous year's improvements, including the addition of Example 8.7, and the conversion of code snippets from C to Python/SageMath to improve accessibility and interactivity through embedded SageMath cells. This update makes use of MathBook XML, enabling features such as an improved index and a list of notations. The exercises remain unchanged between editions to provide consistency for instructors. The use of SageMath is particularly emphasized due to its open-source nature and free online availability through CoCalc, making it a cost-effective alternative to commercial CAS systems.

The initial section contrasts continuous and discrete optimization problems. Familiar examples of continuous problems, such as maximizing fenced land area or determining optimal river-crossing points, are presented. These problems allow for solutions across a continuous range of values. The text then shifts focus to discrete optimization problems, where only integer values are meaningful. This is exemplified by the introduction of Sudoku puzzles. A Sudoku puzzle is described as a 9x9 grid where each row, column, and 3x3 subgrid must contain the digits 1-9 without repetition. The text highlights the inherent difficulty of solving general discrete optimization problems, suggesting that many such problems are computationally challenging, even with significant computing power. The section subtly lays the groundwork for later discussions on computational complexity and algorithm analysis within the context of combinatorial problems.

This section introduces fundamental combinatorial counting techniques using the example of counting possible license plates. The problem involves determining the number of possible license plates given specific constraints on the number of digits and letters, and whether repetition is allowed. The text analyzes different scenarios: allowing repetition of digits and letters, prohibiting repetition of digits within the license plate number, or even restricting repetition of the leading digit of the number while allowing repetition for subsequent digits. The solutions involve applying the multiplication principle for counting the total number of possible license plates by multiplying the number of possibilities for each position. This is contrasted with permutations (P(n,k)) where order matters and repetition is not allowed. The discussion illustrates how simple changes in the constraints significantly impact the calculation and demonstrates basic combinatorial counting techniques—a core element of the overarching theme of the text. The license plate problem serves as a clear and practical illustration of fundamental counting principles crucial to understanding the more complex combinatorial problems covered in subsequent chapters.

The section begins by establishing fundamental graph theory terminology, defining key concepts such as vertices, edges, adjacency, neighbors, and the degree of a vertex. Different notations used by various authors are acknowledged. The historical context of graph theory is introduced through the famous Königsberg Bridge Problem. The problem, situated in Königsberg, Prussia (now Kaliningrad, Russia), involved determining if it was possible to traverse all seven bridges crossing the Pregel River exactly once and return to the starting point. Leonhard Euler's 1736 solution, using graph theory, is referenced as a foundational moment in the field. The problem highlights the power of graph theory to model and solve real-world problems. The section sets the stage for subsequent discussions on more advanced graph theory concepts, such as Eulerian and Hamiltonian graphs. The text emphasizes the practical relevance of graph theory by mentioning its diverse applications in various disciplines.

Building upon the foundational concepts, the text delves into Eulerian and Hamiltonian graphs. An Eulerian graph is defined as a graph possessing a sequence of vertices (with repetition allowed) that traverses each edge precisely once, returning to the starting vertex. Hamiltonian graphs are introduced, though their definition is not explicitly provided in this section. The connection between Eulerian/Hamiltonian cycles and practical applications, particularly in network routing problems, is alluded to. This section sets the stage for further analysis of these graph properties and their implications. The discussion subtly connects the theoretical aspects of graph theory to its practical applications in areas like network design and optimization. This section demonstrates how seemingly abstract mathematical concepts can be applied to solve real-world problems, underscoring the practical relevance of the mathematical concepts being studied.

The concept of planar graphs is introduced, defining a planar drawing as one where edges intersect only at vertices. The text explains that a graph is considered planar if it admits such a drawing. Kuratowski's Theorem is presented as a crucial tool for determining graph planarity. The theorem states that a graph is planar if and only if it does not contain a subgraph homeomorphic to either K5 (the complete graph on five vertices) or K3,3 (the complete bipartite graph on two sets of three vertices). The theorem's utility in planarity testing, both manually and through efficient algorithms, is highlighted. The Petersen graph is used as an example. This illustrates how Kuratowski's Theorem can be used to determine whether a given graph is planar or not; for the Petersen graph, the approach focuses on identifying a subgraph homeomorphic to K3,3. This section further emphasizes the importance of graph theory as a powerful tool for analyzing and understanding relationships in various systems.

The section introduces the Four Color Theorem, a historically significant problem in graph theory. The problem, originating from a question about coloring maps, asks whether any map can be colored using only four colors such that no two adjacent regions share the same color. The text traces its history, starting with its initial proposal by Francis Guthrie and its communication to Augustus De Morgan and others. The section notes that Sir William Rowan Hamilton, for whom Hamiltonian cycles are named, was uninterested in the problem. The transformation of the map-coloring problem into a graph theory question is explained: each region is represented by a vertex, with edges connecting vertices representing regions sharing a boundary. The historical journey of the Four Color Theorem is highlighted, including the flawed 'proof' by Alfred Bray Kempe, the corrections by Percy John Heawood, and the contributions of Peter Guthrie Tait. The eventual computer-assisted proof by Appel and Haken, and its later refinement by Robertson, Sanders, Seymour, and Thomas are mentioned, concluding with the general acceptance of the theorem in modern times. The discussion emphasizes the problem's historical importance and its evolution within the framework of graph theory.

This section introduces Cayley's Formula, a fundamental result in graph theory stating that the number of labeled trees on n vertices is given by n^(n-2). While Cayley is often credited with the result (first stated and proved in graph-theoretic terminology in 1889), the text notes that equivalent results were proven earlier by James J. Sylvester (1857) and Carl W. Borchardt (1860). The text acknowledges a debate around the completeness of Cayley's original proof. The section emphasizes that Cayley's Formula possesses numerous elegant proofs, referencing four such proofs detailed in Aigner, Ziegler, and Hofmann's Proofs from THE BOOK. The authors present a fifth proof, attributed to Prüfer (1918), which utilizes a recursive technique to establish a bijection between the set of labeled trees on n vertices and a set of strings of length n-2, where symbols are drawn from a set of n elements. This section highlights the importance of Cayley's Formula in combinatorial enumeration and graph theory, and introduces the idea of bijective proofs as a powerful tool for establishing combinatorial identities.

The core of this section is a detailed explanation of Prüfer's proof of Cayley's Formula. This proof leverages a recursive technique and a bijection between labeled trees and Prüfer codes. A Prüfer code is a sequence of length n-2 drawn from a set of n elements. The algorithm to generate a Prüfer code from a tree involves iteratively identifying and removing leaves (vertices with degree 1), recording the neighbor of the removed leaf, until only two vertices remain. The process of reconstructing a tree from its Prüfer code is also described: starting with the lowest-numbered unlisted vertex as a leaf, iteratively connect it to the first symbol of the code, remove that symbol and repeat, until the entire tree is reconstructed. This algorithm shows how this sequence uniquely identifies the labelled tree. The proof uses mathematical induction to establish the bijection for all n ≥ 2. The basis case (n=2) is trivial, while the inductive step utilizes the uniqueness of the Prüfer code and the inductive hypothesis to construct a unique tree for any given code. The proof illustrates the power of bijective arguments and recursive techniques in combinatorial proofs.

This section introduces the concept of partially ordered sets (posets). A poset is defined as a pair (X, P), where X is a set and P is a binary relation on X that is reflexive (x ≤ x for all x in X), antisymmetric (if x ≤ y and y ≤ x, then x = y), and transitive (if x ≤ y and y ≤ z, then x ≤ z). The text briefly discusses how posets can be represented visually using diagrams. The concept of the width of a poset is introduced as the maximum size of an antichain (a subset of X where no two elements are comparable). Dilworth's Theorem, a central theme of this section, is mentioned but not yet proven. The discussion also touches upon the representation of posets using 0-1 matrices and linked lists, highlighting methods for representing posets in a way suitable for computer processing, suggesting the relevance of posets to computer science applications. The text hints at the potential computational complexity of finding the width of a poset, setting the stage for further investigation in the following sections.

Dilworth's Theorem, a core result in poset theory, is introduced. The theorem states that the minimum number of chains needed to partition a poset is equal to its width. The proof of Dilworth's Theorem is presented, but the text observes that this proof doesn't directly lead to an efficient algorithm for determining the width or finding an optimal partition into chains. This observation highlights a common theme in combinatorics: a proof of existence does not automatically provide a computationally efficient method for finding the objects whose existence has been proven. The discussion of Dilworth's Theorem emphasizes the theoretical significance of the result but also emphasizes the computational challenges inherent in applying it. The text then introduces the notion of interval orders, characterized by the existence of an interval representation where x < y if and only if the interval for x lies entirely to the left of the interval for y on the real number line. The section concludes by illustrating that every interval order admits a distinguishing representation where intervals are non-degenerate, and endpoints are distinct.

The concept of interval orders is introduced. An interval order is defined as a poset that can be represented using intervals on the real line, such that x < y in the poset if and only if the interval representing x lies entirely to the left of the interval representing y. The text provides an example of an interval order representation. It's noted that in an interval representation, endpoints of intervals need not be distinct, and degenerate intervals (intervals of length zero) are allowed. A distinguishing representation is defined as one where all intervals are non-degenerate, and all endpoints are distinct. The text then states that every interval order has a distinguishing representation, suggesting a method for visualizing and potentially simplifying calculations with certain types of posets. The discussion of interval orders provides a more specialized context within the larger framework of poset theory, demonstrating the diversity of poset types and structures, and offering a glimpse into more specialized results and techniques that could be applied to subsets of posets. The section connects the theoretical aspects of posets to their potential for algorithmic implementation.

This section introduces generating functions as a powerful tool for solving combinatorial enumeration problems. A generating function is defined as a power series of the form Σ (a_n * x^n), where a_n represents the nth term of a sequence. The text emphasizes that these power series can be manipulated algebraically, much like ordinary functions, through addition, subtraction, and multiplication. Convergence of the power series is not a primary concern in this combinatorial context. The text mentions that differentiation and integration techniques from calculus can also be applied to generating functions when appropriate. The section sets the stage for subsequent sections by establishing the fundamental idea of generating functions as a way of encoding sequences of numbers and highlights the versatility of generating functions as a technique for solving enumeration problems, particularly in a combinatorial setting.

This section demonstrates the application of generating functions to solve problems involving the distribution of indistinguishable objects to distinct entities. The recurring problem of distributing apples to children is used as an example, building upon examples from earlier chapters. The section illustrates how generating functions can encode the constraints of the problem, such as ensuring each child receives at least one apple or placing upper bounds on the number of apples a child may receive. The text shows that the coefficient of x^n in the resulting generating function gives the number of ways to distribute n apples to the children under specified restrictions. The fruit basket problem is given as an example with different types of fruit that can be used in the basket. The solution uses the multiplication principle to create a generating function by multiplying individual generating functions for each fruit type, which can then be expanded to find the number of solutions based on the basket's desired total count. The example helps to illustrate the use of generating functions in solving more nuanced problems beyond simple counting.

This section delves into more advanced techniques for manipulating generating functions. The method of partial fractions is mentioned as a powerful technique to simplify generating functions into forms that are more easily expanded into power series. The text acknowledges the challenges involved in solving systems of equations resulting from partial fraction decomposition, and the need to recognize the power series expansions of the resulting functions. The use of SageMath, an open-source computer algebra system, is prominently featured as a tool to aid in manipulating and expanding generating functions. The series() method in SageMath is specifically discussed as a method to obtain the power series expansion of a function up to a specified degree, truncating the remaining terms using big-Oh notation. This section highlights the combination of theoretical mathematical techniques with computational tools to tackle more complex enumeration problems. The use of SageMath is presented as a practical tool to overcome the algebraic complexities involved in handling more intricate generating functions.