Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
with applications to geometry and computer science
This course is (essentially) about one single technique (namely the "linear algebra bound" also called "dimension argument"). We shall see several examples in combinatorics, geometry, and computer science and learn the technique throughout these examples. Besides this technique, this course aims at showing the mathematical elegance of certain proofs and the simplicity of the statements. Towards the end of the course, we shall see the power of this method in proving rather amazing results (e.g., a circuit complexity lower bound, explicit constructions of Ramsey graphs, a famous conjecture in geometry disproved).
Every week a new set of exercises will be handed out which we ask to be solved and handed in one week at the beginning of the lecture.
Exercise sets will be of one of these two types:
(1) Non-graded sets: these exercises will be discussed but will not count towards your grade. Their purpose is to help you in understanding the past lecture(s) and sometimes they will set the ground for some ideas used in future lectures. Though you do not get grades for these exercises, you are strongly encouraged to solve them. (2) Graded sets: these exercises will count towards your grade. They will be scheduled (and of course announced) in advance and they will approximately cover the material of two/three lectures (depending on the difficulty of the topic).
You may discuss the problems with other students, but we ask that all students write down their solutions individually and in their own words. The solutions will be generally handed back to the students one week later.
The total final grade will be a combination of your exercise grade (30%) and your exam grade (70%). Grades above 3.00 for both parts are required.
These books cover most of the topics that will be discussed in the course:
Further references will be given during the course.
The program of the courses is tentative and will be adapted according to the complexity of the topics.
| Lecture | Content | References | Exercises |
|---|---|---|---|
| 1 | Two simple problems (Eventown vs Oddtown) and introduction to the main technique of this course (linear algebra bound). | Lecture Notes 1 | Exercise Set 1 |
| 2 | A geometric problem (two-distance sets) and the spaces of polynomials - an extension of the previous technique with polynomials in place of vectors. Linear independence via determinants. | Lecture Notes 2 | Exercise Set 2 |
| 3 | A jigsaw puzzle with graphs and the solution based on rank of matrices - "complex" objects correspond to "high" matrix rank. | Lecture Notes 3 | Exercise Set 3 (Graded Set) |
| 4 | Ramsey theorem(s) and Ramsey graphs; Existential arguments (probabilistic method) vs explicit constructions (a simple quadratic and cubic construction). | Lecture Notes 4 | Exercise Set 4 |
| 5 | Restricted Intersection Theorems (proofs with linear algebra bound); superpolynomial explicit constructions of Ramsey graphs. | Lecture Notes 5 | Exercise Set 5 |
| 6 | Convexity and Helly's Theorem; other Helly-type theorems (Bollobas statement only). | Lecture Notes 6 | Exercise Set 6 (Graded Set - unusual deadline) |
| 7 | Vectors in "generic position" and a proof of Bollobas Theorem. | Lecture Notes 7 | No exercise set (merged with next one) |
| 8 | Razborov circuit lower bound I: polynomials vs threshold function (linear algebra method). | Lecture Notes 8 | Exercise Set 8 |
| 9 | Razborov circuit lower bound II: polynomials vs circuits (probabilistic argument). | Lecture Notes 9 | Exercise Set 9 (Graded Set) |
| 10 | Chromatic number of unit-distance graphs (proof based on restricted intersection theorems). | Lecture Notes 10 | Exercise Set 10 |
| 11 | Borsuk's conjecture (proof based on previous result). | Lecture Notes 11 | Exercise Set 11 |
| 12 | Inclusion and intersection matrices (restricted intersection theorems revisited) | Lecture Notes 12 | Exercise Set 12 (Graded Set, Earlier Deadline!) |
| 13 | Turning a square into a triangle with straight cuts; Same in 3D (Dehn invariant and impossibility) |