Math109
Combinatorics & Graphs
Faculty
Anier Velasco Sotomayor
Lead at the ML Theory group at Cohere for AI Open Science community.
Course length
Duration
Total hours
Credits
Language
Course type
Fee for single course
Fee for degree students
Skills you’ll learn
Overview
This course is a continuation of the discrete mathematics course, covering various combinatorial structures (such as permutations, combinations, graphs, trees, and partitions) and their properties. It consists of two main parts: the first focuses on combinatorics, expanding on fundamental concepts of enumerative combinatorics, while the second covers discrete graph theory, exploring several properties, special types of graphs, and classical problems.
Learning highlights
- The goal of the course is to introduce various counting methods and to study combinatorial structures, with a particular focus on providing a comprehensive introduction to graph theory.
- By the end of the course, students should be prepared to study algorithms and data structures in computer science, as well as probability in the continuation of the mathematics programme.
Course outline
15 classes
Session 1
Intro to enumerative, existential and constructive combinatorics. Set Theory and proving recap.
Session 2
Modeling. Basic counting: Sum and Product rule. Double counting. Invariants.
Session 3
Binomial coefficients. Multinomial coefficients. Permutations and Combinations. Inclusion-Exclusion.
Session 4
Power series. Generating Functions.
Session 5
Generating Functions II: Classical problems.
Session 6
Other common sequences and counting problems.
Session 7
Midterm.
Session 8
Intro to graph theory: notions and representations.
Session 9
Trees: properties. Counting trees. Spanning Trees.
Session 10
Eulerian Graphs. Hamiltonian paths.
Session 11
Planarity.
Session 12
Graph isomorphism.
Session 13
Colorings. Matchings.
Session 14
Review.
Session 15
Final Exam.
Prerequisites
Passing the discrete mathematics course is required, along with a certain level of mathematical maturity (including an understanding of proofs and standard high-school algebra).
Additionally, although it is not a strong requirement, it is recommended to possess:
basic python programming skills (loops, functions, recursion, lists)
basic skills with power series
basic linear algebra
Methodology
The classes will be a combination of lectures, covering fundamental theory, and problem-solving sessions, where previously introduced concepts will be applied. Occasionally, there will be programming demonstrations to illustrate certain results. Different techniques will be introduced through motivating problems and then generalised.
Students are expected to study the material at home after each lecture, using the recommended bibliography and the teacher’s notes. The exam tasks will not be mere reproductions of those covered in class; therefore, students should not focus solely on memorising content.
For advanced students, additional topics may be provided (e.g., Pólya’s theory, Ramsey theory), which can be discussed outside class.
The course prioritises rigour and clarity when formulating and proving statements. While extreme formality is not required, a certain level of precision will be expected.
Grading
Anier started in computer science by doing programming Olympiads in high school, during which he obtained a gold medal in the Cuban National Olympiad and a bronze medal in the Ibero-American Olympiad in Informatics.
He has a BSc. in Computer Science and Data Science from Harbour.Space University. His main professional interest is Machine Learning Theory Research, and he’s an independent researcher.
See full profileApply for this course
Combinatorics & Graphs
by Anier Velasco Sotomayor
Total hours
45 Hours
Dates
Mar 17 - Apr 04, 2025
Fee for single course
€1500
Fee for degree students
€750
How to secure your spot
Complete the form below to kickstart your application
Schedule your Harbour.Space interview
If successful, get ready to join us on campus
FAQ
Will I receive a certificate after completion?
Yes. Upon completion of the course, you will receive a certificate signed by the director of the program your course belonged to.
Do I need a visa?
This depends on your case. Please check with the Spanish or Thai consulate in your country of residence about visa requirements. We will do our part to provide you with the necessary documents, such as the Certificate of Enrollment.
Can I get a discount?
Yes. The easiest way to enroll in a course at a discounted price is to register for multiple courses. Registering for multiple courses will reduce the cost per individual course. Please ask the Admissions Office for more information about the other kinds of discounts we offer and what you can do to receive one.