263-4310-00L  Linear Algebra Methods in Combinatorics

SemesterFrühjahrssemester 2018
DozierendeP. Penna
Periodizitätjährlich wiederkehrende Veranstaltung


263-4310-00 VLinear Algebra Methods in Combinatorics2 Std.
Di10:15-12:00CAB G 51 »
P. Penna
263-4310-00 ULinear Algebra Methods in Combinatorics2 Std.
Do13:15-15:00CAB G 57 »
P. Penna


KurzbeschreibungThis 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.
LernzielBecoming familiar with the method and being able to apply it to problems similar to those encountered during the course.
InhaltThis 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.
SkriptLecture notes of each single lecture will be made available (shortly after the lecture itself).
LiteraturMost 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.


Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Leistungskontrolle als Semesterkurs
ECTS Kreditpunkte5 KP
PrüfendeP. Penna
RepetitionDie Leistungskontrolle wird nur am Semesterende nach der Lerneinheit angeboten. Die Repetition ist nur nach erneuter Belegung möglich.
Zusatzinformation zum PrüfungsmodusThe 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.


HauptlinkLinear Algebra Methods in Combinatorics (course webpage)
Es werden nur die öffentlichen Lernmaterialien aufgeführt.


Keine Informationen zu Gruppen vorhanden.


Keine zusätzlichen Belegungseinschränkungen vorhanden.

Angeboten in

CAS in InformatikFokusfächer und WahlfächerWInformation
Informatik MasterWahlfächer der Vertiefung General StudiesWInformation
Informatik MasterWahlfächer der Vertiefung in Theoretical Computer ScienceWInformation