263-4310-00L  Linear Algebra Methods in Combinatorics

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



Lehrveranstaltungen

NummerTitelUmfangDozierende
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

Katalogdaten

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.

Leistungskontrolle

Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Leistungskontrolle als Semesterkurs
ECTS Kreditpunkte5 KP
PrüfendeP. Penna
FormSemesterendprüfung
PrüfungsspracheEnglisch
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.

Lernmaterialien

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

Gruppen

Keine Informationen zu Gruppen vorhanden.

Einschränkungen

Keine zusätzlichen Belegungseinschränkungen vorhanden.

Angeboten in

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