Introductory description

Combinatorics is the study of finite mathematical structures, and is one of the most widely applicable fields of mathematics. Enumerative combinatorics, i.e. the study of counting problems, is one of the oldest parts of mathematics, and a vast wealth of ideas and techniques aimed at combinatorial problem-solving have been developed — these ideas underpin arguments across all fields of mathematics and the sciences. Graph theory, the study of networks and connectivity, is an extremely broad and rich area, whose origin is often credited to Euler. Graph theory also has widespread applications in mathematics and the sciences, especially in computer science. The aim of this module is to introduce many of the basic concepts, ideas, and techniques in the theory, and most importantly, to give students the opportunity to use these techniques to solve combinatorial problems.

Module web page

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

I Enumerative combinatorics
-Basic counting (Lists with and without repetitions, Binomial coefficients and the Binomial Theorem)
-Applications of the Binomial Theorem (Multinomial Theorem, Multiset formula, Principle of inclusion/exclusion)
-Linear recurrence relations and the Fibonacci numbers
-Generating functions and the Catalan numbers
-Permutations, Partitions and the Stirling and Bell numbers

II Graph Theory
-Basic concepts (isomorphism, connectivity, Euler circuits)
-Trees (basic properties of trees, spanning trees, counting trees)
-Planarity (Euler's formula, Kuratowski’s theorem, the Four Colour Problem)
-Matching Theory (Hall's Theorem and Systems of Distinct Representatives)
-Elements of Ramsey Theory
III Boolean Functions

Learning outcomes

By the end of the module, students should be able to:

• Combine current techniques with their own creativity to solve combinatorial problems
• Work with definitions and theorems of enumerative combinatorics, graph theory, and Ramsey theory
• Construct bijective proofs of numerical identities
• Adapt the ideas and skills of the module to understand new combinatorial structures
• Adapt the ideas of proofs of theorems in the module to independent settings

Indicative reading list

Edward E. Bender and S. Gill Williamson, Foundations of Combinatorics with Applications, Dover Publications, 2006. Available online at the author's website: http://www.math.ucsd.edu/~ebender/CombText/
John M. Harris, Jeffry L. Hirst and Michael J. Mossinghoff, Combinatorics and graph theory, Springer-Verlag, 2000.

Subject specific skills

Creative problem-solving in a broad range of mathematical contexts, learning to recognize when a given problem is equivalent to a previously-known one, learning to compute examples and spot recursions or other patterns that allow one to solve the general problem, comfort working with generating functions, ability to construct rigorous arguments in graph theory.

Transferable skills

Students will acquire key reasoning and problem solving skills which will empower them to address new problems with confidence.