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 and, if time allows, a famous conjecture in geometry disproved).
The course starts in the second week on Wednesday 28.9.2011, there is no course and no exercise session in the first week of the semester.
Lecture: Wednesday 13:15-15:00, CHN D 42. The lecturers are:
Paolo Penna, CAB H 36.2, Phone: +41 44 632 74 06.Tomas Hruz, CAB H 33.2, Phone: +41 44 632 73 63.
Exercises: Wednesday 15:15-17:00, CHN D 42. The teaching assistant is:
Nguyen Thanh Binh, CAB F 56.1, Phone: +41 44 632 93 28.
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. You need to achieve 80% or more of the possible points to get a grade of 6.0 for the exercises (this refers to the "graded sets" only); 40% of the possible points are required for a passing grade (4.0).
The final exam will take place in the last week of the semester. The total final grade will be a combination of your exercise grade and your exam grade, each counting 50%. 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.
| Date | Content | Exercises | References |
| 28.9.2011 | Two simple problems (Eventown vs Oddtown) and introduction to the main technique of this course (linear algebra bound). | Exercise Set 1 | Lecture Notes 1 |
| 5.10.2011 | 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. | Exercise Set 2, graded | Lecture Notes 2 |
| 12.10.2011 | A jigsaw puzzle with graphs and the solution based on rank of matrices - "complex" objects correspond to "high" matrix rank. | Exercise Set 3 | Lecture Notes 3 |
| 19.10.2011 | Ramsey theorem(s) and Ramsey graphs; Existential arguments (probabilistic method) vs explicit constructions (a simple quadratic and cubic construction). | Exercise Set 4, graded | Lecture Notes 4 |
| 26.10.2011 | Restricted Intersection Theorems (proofs with linear algebra bound); superpolynomial explicit constructions of Ramsey graphs. | Exercise Set 5 | Lecture Notes 5 |
| 2.11.2011 | Convexity and Helly's Theorem; other Helly-type theorems (Bollobas statement only). | Exercise Set 6, graded | Lecture Notes 6 (reloaded) |
| 9.11.2011 | Generic position arguments and a proof of Bollobas Theorem. | Exercise Set 7 | Lecture Notes 7 |
| 16.11.2011 | Razborov circuit lower bound I: polynomials vs threshold function (linear algebra method). | Exercise Set 8, graded | Lecture Notes 8 |
| 23.11.2011 | Razborov circuit lower bound II: polynomials vs circuits (probabilistic argument). | Exercise Set 9 | Lecture Notes 9 |
| 30.11.2011 | Chromatic number of unit- distance graphs (proof based on restricted intersection theorems). | Exercise Set 10, graded | Lecture Notes 10 (reloaded) |
| 7.12.2011 | Borsuk's conjecture (proof based on previous result). | No exercises | Lecture Notes 11 |
| 21.12.2011 | Exam |
Training set of exercises.