Logic and Dense GraphsModule description #41349 / Version 1
- 9 CP
- Oral exam
- Graded
- Winter semester
- English
| Module / Version | #41349 / #1 |
|---|---|
| Validity | Since Winter semester 2026/27 |
| Available language(s) | English, German |
| Credit points | 9 |
| Person responsible for the module | Kreutzer, Stephan |
| Grading | Graded |
| Exam format | Oral exam |
| Language(s) of instruction | English |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Softwaretechnik und Theoretische Informatik |
| Academic chair | 34352200 FG Logik und Semantik (LaS) |
Contact
| Office | EN 25 |
|---|---|
| Contact person | Pilz, Jana |
| E-mail address | sekretariat@las.tu-berlin.de |
| Website | https://www.tu.berlin/las/studium-lehre/veranstaltungsangebot |
Learning outcomes
Students will learn a rich set of concepts and methods from areas of logic known as model theory and finite model theory as well as interesting new methods in combinatorics and graph theory. Especially they will understand how these tools from seemingly very different fields interact and can be combined to understand important graph classes within the realm of dense class and how to utilise this algorithmically.
Content
The study of the model-checking complexity of logics such as first-order logic has exhibited a deep and extremely fruitful connection between structural and algorithmic graph theory and computational logic. For a long time research in this area has concentrated on sparse classes of graphs and structures and concepts such as graph minors or sparsity theory have played a central role.
In recent years research in this area has shifted towards the study of dense classes of graphs. In graph theory, dense classes of graphs have often been studied in the form of random graphs, but these are less important in connection with model-checking problems in computational logic.
Instead, graph classes defined by concepts such as stability or independence originating in model theory have become the focus of current research. Originally defined in logical terms a rich combinatorial theory of such classes has emerged in the last few years.
The main objective of this lecture is to explore recent developments in this area. We will introduce the relevant tools from model theory that were used to define concepts such as stable and dependent classes of graphs. We will then cover important combinatorial tools proved in the last few years to better understand these concepts and cover algorithmic applications of the emerging theory.
Finally we will also introduce the concept of vertex-minors and their role in the theory of dense graphs.
Much of this lecture will cover research results that were only obtained in the last few years including some current and ongoing research projects.
Therefore the lecture will lead very close to current research.
In recent years research in this area has shifted towards the study of dense classes of graphs. In graph theory, dense classes of graphs have often been studied in the form of random graphs, but these are less important in connection with model-checking problems in computational logic.
Instead, graph classes defined by concepts such as stability or independence originating in model theory have become the focus of current research. Originally defined in logical terms a rich combinatorial theory of such classes has emerged in the last few years.
The main objective of this lecture is to explore recent developments in this area. We will introduce the relevant tools from model theory that were used to define concepts such as stable and dependent classes of graphs. We will then cover important combinatorial tools proved in the last few years to better understand these concepts and cover algorithmic applications of the emerging theory.
Finally we will also introduce the concept of vertex-minors and their role in the theory of dense graphs.
Much of this lecture will cover research results that were only obtained in the last few years including some current and ongoing research projects.
Therefore the lecture will lead very close to current research.
Module components
Compulsory area
The following courses are mandatory for this module:
| Courses | Type | Number | Frequency | Language | Hours per week | Course catalog |
|---|---|---|---|---|---|---|
| Logic and Dense Graphs | Lecture | Winter semester | [en] | 4 | WS 2026/27 (2) ISIS | |
| Logic and Dense Graphs | Exercise | Winter semester | [en] | 2 | WS 2026/27 (1) ISIS |
Courses in the course catalog
Courses created from the teaching units of this module.
Winter semester 2026/27 (3)
Logic and Dense Graphs (Lecture) 2
- Logic and Dense Graphs (Vorlesung) Vorlesung 1
- Logic and Dense Graphs (Vorlesung) Vorlesung 2
Logic and Dense Graphs (Exercise) 1
- Logic and Dense Graphs (Übung) LDG Übung
Workload and credit points
Logic and Dense Graphs (Lecture)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 4 h | 60 h |
| Pre/post processing | 15 | 8 h | 120 h |
| 180 h | |||
Logic and Dense Graphs (Exercise)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 2 h | 30 h |
| Pre/post processing | 15 | 4 h | 60 h |
| 90 h | |||
The workload of the module adds up to 270 hours. The module therefore comprises 9 credit points.
Description of teaching and learning methods
The module consists of a lecture in which the relevant material will be discussed accompanied by weekly exercise sessions designed to aid students in understanding the lecture.
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
There are no fixed set of prerequisites for this lecture. All required tools and methods will be introduced and presented in the lecture.
However, students taking this lecture are expected to have some background knowledge in logic as it is, e.g., cover in the undergraduate course "logic" in the computer science curriculum.
In addition, a strong interest in theoretical computer science and a reasonable level of what is often referred to as mathematical maturity is required.
However, students taking this lecture are expected to have some background knowledge in logic as it is, e.g., cover in the undergraduate course "logic" in the computer science curriculum.
In addition, a strong interest in theoretical computer science and a reasonable level of what is often referred to as mathematical maturity is required.
Mandatory requirements for the module examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Oral exam |
| Language | English |
| Duration/Extent | 20-45 minutes |
Duration of the module
The following number of semesters is estimated for taking and completing the module: 1 semester(s).
This module can be started in the following semesters: Winter semester.
Maximum number of participants
This module is not limited to a number of students.
Registration procedures
Students can sign up to the exam towards the end of term in the usual way.
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
available – We will compile a set of lecture notes which will be made available to students taking the course.
Recommended literature
No recommended literature given
Assigned programs
This module version is used in the following programs:
| Program / program version | Semester(s) | Curriculum component |
|---|---|---|
| Computer Engineering Computer Engineering (M. Sc.) - StuPO 2015 | WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| Computer Science (Informatik) Computer Science (Informatik) (M. Sc.) - StuPO 2015 | WS 2026/27 | Wahlpflichtbereich › Studiengebiete › Grundlagen der Informatik / Foundations of Computing |
| Electrical Engineering Electrical Engineering (M. Sc.) - StuPO 2015 | WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
Miscellaneous
Not specified