Skip to content
Technische Universität Berlin Deutsch
Course catalog and module transfer system

Algebraic Graph TheoryModule description #40986 / Version 1

← Module page Deutsche Fassung
Module / Version#40986 / #1
ValiditySince Summer semester 2020
Available language(s)English
Credit points6
Person responsible for the moduleKreutzer, Stephan
GradingGraded
Exam formatOral exam
Language(s) of instructionEnglish

Affiliation

FacultyFakultät IV
InstituteInstitut für Softwaretechnik und Theoretische Informatik
Academic chair34352200 FG Logik und Semantik (LaS)

Contact

OfficeTEL 7-3
Contact personPilz, Jana
E-mail addressstephan.kreutzer@tu-berlin.de
WebsiteNot 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.

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.

Module components

Compulsory area

The following courses are mandatory for this module:

CoursesTypeNumberFrequencyLanguageHours per weekCourse catalog
Algebraic Graph TheoryExercise3435 L 10587 Summer semester[en]2 ISIS
Algebraic Graph TheoryLecture3435 L 10590 Summer semester[en]2 ISIS

Workload and credit points

Algebraic Graph Theory (Exercise)

Workload descriptionMultiplierHoursTotal
Attendance152 h30 h
Pre/post processing154 h60 h
90 h

Algebraic Graph Theory (Lecture)

Workload descriptionMultiplierHoursTotal
Attendance152 h30 h
Pre/post processing154 h60 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

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.

Mandatory requirements for the module examination registration:

This module has no examination requirements.

Completion of the module

GradingGraded
Exam formatOral exam
LanguageEnglish
Duration/Extent30-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