Special Topics in Mathematics (MAS480B)

Special Topics in Computer Science (CS492A)

Linear Algebra in Combinatorics and Algorithms

Spring Semester 2010

Linear algebra has many applications in mathematics, and in science and engineering in general. It is less often associated with results in discrete mathematics. In this course we will meet some such results in my area of interest, combinatorics and algorithms. The appearance of linear algebra methods in these results is often unexpected, and leads to some beautiful proofs.

The course is meant for undergraduate students. Third year students who have taken second year linear algebra will have no problem to follow. I will also review some necessary linear algebra, so that students who have only taken freshman linear algebra can follow with a bit of effort.

Each result I present will be self-contained, so this course is very suitable for students who only want to audit it and can't be present in every class.

The course is cross-listed and offered as both CS492A (Special Topics in Computer Science) and MAS480B (Special Topics in Mathematics).


Otfried Cheong (Office: E3-1 3434, Phone: 3542).


Juyoung Yon (Office: E3-1 3439, Phone: 3582).


Lectures are given in English. The class meets Monday, Wednesday, and Friday from 10:00 to 10:50 in room 2445 (classroom 4) in the Computer Science Building (E3-1).

Moodle forums

Students should enroll for the course on Moodle. This will allow you to see your grades as soon as I have computed them, instead of when they are released on CAIS.

We have two forums for the course on Moodle:

Please subscribe at least to the announcement board so that you do not miss important announcements, for instance if the class is cancelled because I am sick. (Go to the announcement board and click on Subscribe to this forum in the top right corner.)

Grading policy

Students will be graded based on homeworks (40%), a final exam (40%), and participation (20%). There will be no midterm exam.


There will be a final exam on Friday, May 7, from 10:00 to 11:00 in our usual class room.

The exam is open book: You can bring one copy of the lecture notes by Jiří Matoušek. No other references are allowed.


This class will be based on lecture notes written by Jiří Matoušek. The lecture notes are not publicly available, but will be provided to students in the course.


Here is a rough list of what we will cover in each week of the semester.

Week 1 Fibonacci numbers
Week 2 Set systems with prescribed intersection patterns
Week 3 Are these distances Euclidean?
Week 4 Complete graphs from bipartite graphs
Week 5 Counting spanning trees
Week 6 Error-correcting codes
Week 7 Checking computations
Week 8 No class (midterm exam week)
Week 9 Petersen, Hoffman-Singleton, and maybe 57
Week 10 Point sets with only two distances
Week 11 A result from discrepancy theory
Week 12 Tilings
Week 13 Kakeya's conjecture for finite fields
Week 14 Shannon capacity of a graph
Week 15 Rotating the cube
Week 16 Final Exam week

Course progress

The material covered in the lectures so far:

02-01 Introduction, Odd distances, Clubs of Oddtown Ch. 6, Ch. 3
02-03 Fibonacci numbers Ch. 1, Ch. 2
02-05 Walking in the yard Ch. 20
02-10 Complete graph from bipartite graphs Ch. 8
02-17 Vector spaces, Tiling a rectangle Ch. 12
02-19 Linear codes Ch. 5
02-22 Equiangular lines, same-size intersection Ch. 9, Ch. 4
02-24 Covering a cube, Only two distances Ch. 16, Ch. 15
02-26 Joints and Lines arXiv:0906.0558
03-03 Three Petersen graphs are not enough Ch. 13
03-05 Petersen, Hoffman-Singleton, perhaps 57 Ch. 14
03-08 Counting spanning trees I Ch. 21
03-10 Counting spanning trees II, Medium-size intersection Ch. 21, Ch. 17
03-12 Borsuk's question Ch. 18
03-17 Counting tilings I Ch. 22
03-19 Counting tilings II Ch. 22
03-29 Integer partitions I Ch. 23
03-31 Integer partitions II Ch. 23
04-02 Find the triangle, Checking matrix multiplication Ch. 10, Ch. 11
04-05 Perfect matchings Ch. 24
04-07 Counting compositions Ch. 26
04-09 Is it associative? CH. 27
04-12 Spectral partitioning I Ch. 31
04-14 Spectral partitioning II Ch. 31
04-16 Sauer's lemma Smolensky's paper
04-21 Euclidean distances Ch. 7, Ch. 30
04-23 More on Euclidean distances Ch. 30
04-26 Shannon Capacity I Ch. 28
04-28 Shannon Capacity II Ch. 28
04-30 Review Homework 2
05-07 Final exam
05-10 Review Homework 3 and exam


There will be a few homework assignments in this course. You will have one or two weeks to complete an assignment. Homeworks must be submitted on paper and must be handed in at the beginning of class.

Otfried Cheong