# 263-4310-00L Linear Algebra Methods in Combinatorics

Semester | Spring Semester 2017 |

Lecturers | P. Penna |

Periodicity | yearly recurring course |

Language of instruction | English |

### Courses

Number | Title | Hours | Lecturers | ||||
---|---|---|---|---|---|---|---|

263-4310-00 V | Linear Algebra Methods in Combinatorics | 2 hrs |
| P. Penna | |||

263-4310-00 U | Linear Algebra Methods in Combinatorics | 2 hrs |
| P. Penna |

### Catalogue data

Abstract | This course describes the linear algebra bound technique also called dimension argument. To learn the technique we discuss several examples in combinatorics, geometry, and computer science. Besides this technique, the course aims at showing the mathematical elegance of certain proofs and the simplicity of the statements. |

Objective | Becoming familiar with the method and being able to apply it to problems similar to those encountered during the course. |

Content | This course is (essentially) about one single technique called the "linear algebra bound" (also known as "dimension argument"). We shall see several examples in combinatorics, geometry, and computer science and learn the technique throughout these examples. 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 a famous conjecture in geometry disproved). The course also aims at illustrating the main ideas behind the proofs and how the various problems are in fact connected to each other. |

Lecture notes | Lecture notes of each single lecture will be made available (shortly after the lecture itself). |

Literature | Most of the material of the course is covered by the following book: 1. Linear algebra methods in combinatorics, by L. Babai and P. Frankl, Department of Computer Science, University of Chicago, preliminary version, 1992. Some parts are also taken from 2. Extremal Combinatorics (with Applications in Computer Science), by Stasys Jukna, Springer-Verlag 2001. |

### Performance assessment

Performance assessment information (valid until the course unit is held again) | |

Performance assessment as a semester course | |

ECTS credits | 5 credits |

Examiners | P. Penna |

Type | end-of-semester examination |

Language of examination | English |

Repetition | The performance assessment is only offered at the end after the course unit. Repetition only possible after re-enrolling. |

Additional information on mode of examination | The final exam (duration 120 minutes) will take place in the last week of the semester. 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. |

### Learning materials

Main link | Linear Algebra Methods in Combinatorics (course webpage) |

Only public learning materials are listed. |

### Groups

No information on groups available. |

### Restrictions

There are no additional restrictions for the registration. |

### Offered in

Programme | Section | Type | |
---|---|---|---|

Certificate of Advanced Studies in Computer Science | Focus Courses and Electives | W | |

Computer Science Master | Focus Elective Courses Theoretical Computer Science | W |