DARTMOUTH COLLEGE

DEPARTMENT OF MATHEMATICS

GRADUATE PROGRAM

COMBINATORICS: Syllabus for Graduate Certification

Because of the unusual breadth of combinatorial mathematics, the topics in the subject relevant to the graduate certification requirement have been divided into primary and secondary topics. The student is required to have a basic knowledge of each of the three primary topics and at least one of the secondary topics. The primary topics are (1) Classical Combinatorics, (2) Algebraic Techniques, and (3) Graph Theory. The secondary topics include (A) Ordered Sets, (B) Coding Theory, (C) Combinatorial Geometry and Matroids, (D) Matching Theory, (E) Random Graphs and the Probabilistic Method, (F) Symmetric Functions, and (G) Representations of the Symmetric Group. Other topics could serve as secondary topics with the approval of the GEC in consultation with the combinatorics faculty.

PRIMARY TOPICS

1.

Classical Combinatorics Counting functions: arbitrary, injective or surjective functions with domain and range either distinguishable or indistinguishable. Classical Enumeration: sets, multisets, permutations, multiset permutations, partitions, set partitions, and compositions; Applications to Bell numbers, Stirling numbers of the first and second kinds, and Eulerian numbers; Producing and solving recurrence relations, bijective methods in proofs, with applications of these techniques to the Catalan and Fibonacci families. Finite Configurations: Latin squares; Balanced and incomplete block designs, symmetry, and construction techniques; Relationships of the design parameters; Finite, affine, and projective geometries and their relations to designs and Latin squares. Ramsey's Theorem: At least one significant application; upper and lower bounds on Ramsey numbers.

2.

Algebraic Techniques Generating functions: The algebra of the formal power series ring C[[x]]; Ordinary and exponential generating functions; Applications to partition problems, Stirling numbers of the first kind, permutation statistics, and Bell numbers. Gaussian polynomials: Connections with partitions, the lattice of subspaces of a vector space over a finite field, and the $q$-binomial Theorem. Group actions: Counting orbits using the Burnside Lemma; Polya's Theorem with at least one significant application such as counting unlabeled graphs or trees. Sieve techniques: The Fundamental Theorem of Möbius inversion and its relation to number theoretic Möbius inversion and to the principle of inclusion and exclusion; Computation of the Möbius function of simple partially ordered sets, of the set partition lattice, and of the subspace lattice; At least one significant application such as counting labeled connected graphs.

3.

Graph Theory Basic concepts: Euler and Hamiltonian cycles; Connectedness, $n$-connectedness, and Menger's Theorem (both point and line forms); Adjacency matrix and incidence matrix; Bipartite graphs; Tournaments. Topology: Isomorphism; Planarity and the planar dual; Line graphs; Euler's formula and related inequalities for planarity; Graph coloring including the Four and Five Color Theorems; Deletion/Contraction and the chromatic polynomial. Networks: Flows, cuts, and flow-augmenting paths; The Max-Flow Min-Cut Theorem; Integral flows and Menger's Theorem. Special topics: Interval graphs; Chordal graphs; Perfect graphs; Spanning trees and the Matrix Tree Theorem; Counting labeled trees and Prüfer's correspondence; Factorization and Tutte's Theorem on 1-factors.

SECONDARY TOPICS

A.

Ordered Sets Partial orders and lattices; Distributive, complemented, geometric, and modular lattices; The Fundamental Theorem on Finite Distributive Lattices; Birkhoff's Theorem for uniquely complemented lattices; Chains, multichains, and antichains; Sperner's Theorem; The incidence algebra; Basic concepts of dimension theory; Interval orders; Special cases and generalizations of interval orders.

B.

Coding Theory Linear and nonlinear block codes; Bounds on the size of codes of length $n$ and minimum distance $d$; The major properties of Hamming, BCH, Reed-Muller, Golay, Cyclic, and Quadratic Residue codes; Dual codes, the MacWilliams Theorem on the relationship between the weight enumerator of a code and its dual code, and applications of this theorem; Association schemes and their relationship with coding theory; Relationship between codes and designs.

C.

Combinatorial Geometry and Matroids Matroids and combinatorial geometries; Equivalence of definitions by closures, circuits, bases, the greedy algorithm, and rank functions; Connectivity; Geometric lattices; Modular geometric lattices and projective geometries; The lattice of flats of a combinatorial geometry; Relationship of combinatorial geometries and matroids to graphs; Representable and nonrepresentable geometries; Möbius functions and characteristic polynomials.

D.

Matching Theory Hall's Theorem on systems of distinct representatives and its generalizations; Dilworth's Theorem with application to Birkhoff's Theorem on doubly stochastic matrices; König's Theorem on 0-$1$ matrices; Relations between SDR's, 0-$1$ matrices, and Latin squares; The assignment problem and algorithms for finding SDR's; Berge's criterion on alternating paths.

E.

Random Graphs and the Probabilistic Method Probabilistic models for graphs; Markov's inequality, Chebyshev's inequality, and the second moment method; Threshold functions with at least one application; The evolution of random graphs; The probabilistic method with application to diagonal Ramsey numbers; The deletion method; Discrepancy and the pusher--chooser game; The Lovász Local Lemma with application to diagonal Ramsey numbers.

F.

Symmetric Functions The graded ring of symmetric functions; Descriptions of the five natural bases: monomial, elementary, complete homogeneous, power sum, and Schur symmetric functions; Relationships between the five bases; Jacobi--Trudi determinants; The Hall involution and its properties; The Hall inner product and orthogonality; The Robinson--Schensted--Knuth correspondence and its properties; The Littlewood--Richardson rule; Plethysm.

G.

Representations of the Symmetric Group Matrix representations; $G$-modules and the group algebra of a finite group; Reducibility; Maschke's Theorem; Schur's Lemma; Irreducible characters and orthogonality; Decomposition of the group algebra; Restriction and induction; Young subgroups; Tableaux and tabloids; The standard basis for the Specht module $S^{\lambda}$; the semistandard basis for $\textrm{Hom}(S^{\lambda},M^{\mu})$; Kostka numbers; Young's rule.

REFERENCES

1.

Classical Combinatorics Bogart, Introductory Combinatorics, Second Edition (Chapters 1,2,6) Graham, Rothschild, and Spencer, Ramsey Theory (Chapter 1) Liu, Introduction to Combinatorial Mathematics Riordan, Combinatorial Mathematics (Chapters 2--4) Stanley, Enumerative Combinatorics, Volume 1 (Chapter 1)

2.

Algebraic Techniques Aigner, Combinatorial Theory Bogart, Introductory Combinatorics, Second Edition (Chapters 3, 8) Stanley, Enumerative Combinatorics, Volume 1 (Chapters 1--3)

3.

Graph Theory Bogart, Introductory Combinatorics, Second Edition (Chapters 4,5) Bollobas, Graph Theory: An Introductory Course Bondy and Murty, Graph Theory With Applications Golumbic, Algorithmic Graph Theory and Perfect Graphs

A.

Ordered Sets Birkhoff, Lattice Theory Davey and Priestley, Introduction to Lattices and order Bogart, Introductory Combinatorics, Second Edition (Chapter 7) Stanley, Enumerative Combinatorics, Volume 1 Trotter, Combinatorics and Partially Ordered Sets: Dimension Theory (Chapter 3)

B.

Coding Theory Berlekamp, Algebraic Coding Theory Peterson and Weldon, Error-Correcting codes Pless, Intorduction to the Theory of Error-Correcting Codes Sloane and MacWilliams, The Theory of Error Correcting Codes Van Lint, Coding Theory

C.

Combinatorial Geometry and Matroids Aigner, Combinatorial Theory Crapo and Rota, On the Foundations of Combinatorial Theory: Combinatorial Geometries Oxley, Matroid Theory Welsh, Matroid Theory

D.

Matching Theory Bogart, Introductory Combinatorics, Second Edition (Chapter 5) Hall, Combinatorial Theory Mirsky, Transversal Theory: An Account of Some Aspects of Combinatorial Mathematics Ryser, Combinatorial Mathematics

E.

Random Graphs and the Probabilistic Method Bollobas, Random Graphs Palmer, Graphical Evolution Spencer, Ten Lectures on the Probabilistic Method

F.

Symmetric Functions Macdonald, Symmetric Functions and Hall Polynomials (Chapter 1) Sagan, The Symmetric Group (Chapters 3,4)

G.

Representations of the Symmetric Group Sagan, The Symmetric Group (Chapters 1,2)