Course: MAT377
Instructor: Noga Alon
F 2019

Description of Course Goals and Curriculum

Combinatorics is the study of counting. As a branch of discrete mathematics, a common question is “how many X can there be if we assume Y”. Surprisingly, these questions required deep reasoning and a degree of inventiveness not found in fields with more theoretical foundations such as analysis and algebra. As a matter of fact, Combinatorics is one of the only branches of mathematics where the interest lies in HOW a result is derived rather than the result itself.

Over the years, the field has departed from answers to a collection of intellectually curious counting problems and emerged as a field with sophisticated mathematical tools and techniques for analysing and solving them. The course begins with a formal analysis of common counting techniques that arise in many areas outside of mathematics (such as combinations and permutations). It then takes you through major breakthroughs in graph theory such as Ramsey Theory and Extremal Graphs. Later in the course, you will explore techniques derived from linear algebra and probability theory- exploiting properties of finite dimensional vector spaces and proving the existence of objects by proving that we can randomly generate such objects with nonzero probability.

There are two main learning objectives of this course. First and foremost, it is to expose you to the field of combinatorics which holds a unique place in mathematics. It is a survey of some of its most beautiful theorems as well as powerful techniques that can be used to study many related problems. The second is to develop your mathematical reasoning: your ability to abstract a problem to mathematical structures and apply techniques with rigorous logical arguments. Multiple proofs will sometimes be presented to show how different ways of interpreting and solving the problem give greater insight into its nature as well as answers to related questions.

Learning From Classroom Instruction

Lectures are held twice a week for 1.5 hours each. They are not mandatory and closely follow the online notes provided to you in the beginning. For most classes in the mathematics department, this is standard and allows students to skip lectures in favour of reading the text on their own time. Each chapter is relatively independent from the others and lectures cover these chapters week by week exactly as provided in the syllabus. This makes catching up with missed topics particularly easy.

However, class attendance is strongly encouraged as Professor Alon takes great care in ensuring every student has a deep understanding of the topic. Many math professors will simply regurgitate the proofs provided in the text. Professor Alon, however, will often draw diagrams and give examples to students to imbue them with the intuition used to derive these proofs. His method of teaching is well suited for a class in combinatorics as knowing HOW we arrived at these proofs is more important than the proofs themselves as mentioned in the course description.

His clarity of exposition and his desire to communicate the ideas behind the proofs come at a cost. He teaches slowly which makes it easy to become bored and lose attention. However, there is one aspect about his teaching every mathematics student will adore. It is common for some professors to say some results are “trivial” or “left as an exercise to the student” to be done on their own time. While Professor Alon participates in this tradition, he will go a step further and provide intuition and hints for them. You will never be left with gaps in your understanding because you could not immediately grasp “trivialities”.

Overall the quality of his teaching greatly exceeds that commonly seen in the math department and greatly enhances your understanding of the topics.

Learning For and From Assignments

The assignments consisted of 5 biweekly problem sets and a take-home midterm and final. Each assignment/assessment consisted of only 5 questions.

The types of questions fall into two general categories. One is a general improvement of a result from class. For example, we have yet to find exact values for many counting problems and in most of these cases, we suffice with just a range. Some questions will ask you to enhance the proof given in order to narrow down the range of possible values. Another example is to generalize the proof to a wider case of counting problems such as adding or removing restrictions to the original problem.

The second category is to solve a new counting problem using the techniques of analysis used to solve other problems. These questions will involve using results found in class as stepping stones in your proof. An example is using similar arguments from the probabilistic method to prove a result from a separate problem.

Both of these categories serve as expectations as to what is required to learn from this course. The first category problems require an intimate understanding of the proofs given. This is not simply knowing how a proof was constructed and the ability to reproduce it. It also requires that you understand the intuition involved when the proof was first constructed. This is because a lot of the problems, as mentioned in the description, required some ingenuity. Thus, it is not always clear why certain steps were taken or how one would think to do such a thing. Solving the first category questions will test this knowledge and will leave you with a deeper understanding of the concepts. In fact, this is why you are given two weeks for just 5 problems as most of the time is spent conceptualizing and intuiting the problem.

The second category tests your ability to break down and abstract problems. Many of the questions are stated very simply but their solutions are complex. Often you will have to reinterpret how problems are represented-usually with mathematical structures such as sets and graphs. What results to use may not be clear from the problem and it is this reformulation that allows you to relate to and apply the techniques learnt in the class. This is a skill crucial to the success of any mathematician, and indeed to problem solving in general, that is emphasized in this class more than most classes in the department.

To summarize, doing the assignments will grant you a deeper understanding of the proofs discussed in class and enhance your ability to creatively decompose and relate concepts together.

External Resources

The course notes that are provided at the beginning are invaluable. It is written with clarity and refrains from being a dry summary of the teaching. As a matter of fact, it is just shy of being a comprehensive textbook. It also does a great job in portraying why combinatorics is a gem within mathematics and encourages developing interest in the field outside of the course. At the end of each chapter includes bibliography for further reading.  Though optional, they provide different perspectives and motivations for the subject at hand and help mature your understanding and ability to think combinatorially (important skills for this class).  Best of all, most are easily accessible online or through the university library.

Office hours are encouraged. If they cannot be made, Professor Alon is beyond accommodating, often scheduling one on ones with the students. As mentioned above, he is an excellent teacher in class. During office hours, and especially during his one on ones, he will put all of his energy in helping you understand what was done in class. He will also help you understand questions in the problem sets and give excellent guidance in tackling them. As the questions are often very difficult, nearing the due date Professor Alon will be generous with both his time and information so you may never be stressed or discouraged from the course.

As a final note, many of the results seen later on in the course (particularly with the probabilistic method), Professor Alon pioneered. Where better to learn than from the creator himself?

What Students Should Know About This Course For Purposes Of Course Selection

This combinatorics course is unique from other mathematics courses. It deviates from the standard axiomatic pedagogy seen in other courses whereby everything is built up from base principles and theories are constructed as the boundaries of knowledge are pushed. Instead, this course emphasises the aspects about mathematics that attracted and inspired many students to pursue this major initially. In particular, it rewards creative abstraction and clever problem solving. By virtue of the deep reasoning and intuition needed for some problems, it can make coming up with a solution an absolutely satisfying journey that leaves you feeling triumphant.

For students of mathematics, this course will greatly develop your mathematical maturity and ability to creatively solve problems. However, as the focus is on techniques to analyse various counting problems, many results will seem unrelated and students may doubt the usefulness outside of combinatorics. This is unfortunately enhanced when one considers that combinatorics is one of the newest fields in mathematics. The course benefits from being fun and forming an experience unique from any other mathematics course. It also counts towards the discrete mathematics requirement for the degree.

For students of computer science, this course is a great followup to Graph Theory. Some results have important applications in theoretical computer science, particularly with algorithm analysis which often boil down to counting problems.

There are also some students who take this course simply to reminisce about their times partaking in mathematics competitions in earlier school years. This is because many problems in mathematics competitions are precisely combinatorics problems as the field rewards the skills needed most for the development of great mathematicians: strong abstraction and clever reasoning. All being mentioned, the prerequisites for this course are minimal. As a matter of fact, the only real requirement is appropriate mathematical maturity (otherwise stated as the ability to write and understand proofs). Any background in discrete mathematics is either taught or can be found in the short but comprehensive appendix from the notes provided. Only the basic results from linear algebra (vector spaces, linear independence, inner product) are ever used and knowledge of probability is not assumed and is thus taught from the basic (albeit quickly).

Combinatorial Mathematics

Add a Strategy or Tip