Algebraic Graph TheoryModule description #40986 / Version 1
- 6 CP
- Oral exam
- Graded
- Summer semester
- English
| Module / Version | #40986 / #1 |
|---|---|
| Validity | Since Summer semester 2020 |
| Available language(s) | English |
| Credit points | 6 |
| 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 | TEL 7-3 |
|---|---|
| Contact person | Pilz, Jana |
| E-mail address | stephan.kreutzer@tu-berlin.de |
| Website | Not specified |
Learning outcomes
After successfully completing this course, the students are able to:
- name the important theorems and their essence addressed during the lecture.
- understand the results stated during the lecture.
More precisely this means:
o the can qualitatively sketch the proofs of the main results and explain them, also via pictures.
o they can give full proofs of smaller results occurring in the lecture.
o they understand why and where certain assumptions were made and used, respectively.
- compare different (graph theoretic) invariants and prove their relationship, if it exists, as well as to give examples for such relations.
- analyse graph theoretic theorems and their proofs under the aspect whether they are (might be) a matroidal result.
- analyse graphs under algebraic aspects and use / apply algebraic techniques and invariants to obtain structural results about graphs.
- name the current research status regarding open problems that were addressed during the lecture.
- name the important theorems and their essence addressed during the lecture.
- understand the results stated during the lecture.
More precisely this means:
o the can qualitatively sketch the proofs of the main results and explain them, also via pictures.
o they can give full proofs of smaller results occurring in the lecture.
o they understand why and where certain assumptions were made and used, respectively.
- compare different (graph theoretic) invariants and prove their relationship, if it exists, as well as to give examples for such relations.
- analyse graph theoretic theorems and their proofs under the aspect whether they are (might be) a matroidal result.
- analyse graphs under algebraic aspects and use / apply algebraic techniques and invariants to obtain structural results about graphs.
- name the current research status regarding open problems that were addressed during the lecture.
Content
Basics in Matroid Theory
Connections between graphs and matroid via cut/cycle space of graphs
Planar duality and their matroidal aspects
Group actions on graphs
Transitive graphs
Cayley graphs
Spectral Graph Theory.
Connections between graphs and matroid via cut/cycle space of graphs
Planar duality and their matroidal aspects
Group actions on graphs
Transitive graphs
Cayley graphs
Spectral Graph Theory.
Module components
Compulsory area
The following courses are mandatory for this module:
Workload and credit points
Algebraic Graph Theory (Exercise)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 2 h | 30 h |
| Pre/post processing | 15 | 4 h | 60 h |
| 90 h | |||
Algebraic Graph Theory (Lecture)
| 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 180 hours. The module therefore comprises 6 credit points.
Description of teaching and learning methods
- Lecture presenting the core material
- tutorials in which examples and exercises are discussed
- tutorials in which examples and exercises are discussed
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
Students should have basic knowledge of graph theory. In addition, basic knowledge of Linear Algebra and
Group Theory may be helpful but is not a requirement.
Group Theory may be helpful but is not a requirement.
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 | 30-40 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: Summer semester.
Maximum number of participants
This module is not limited to a number of students.
Registration procedures
Qispos
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
available
Recommended literature
- Algebraic Graph Theory by C. Godsil and G. Royle
- Graph Theory by Reinhard Diestel, Springer-Verlag
Assigned programs
This module is not used in any program.
Master and bachelor students of Mathematics and Computer Science.
Miscellaneous
Not specified