Moses - Algebraic Graph Theory

Display language

To modulepage Generate PDF

Module / Version:
#40986 / #1

Validity:
Seit SoSe 2020

Default display language:
English

Module title:
Algebraic Graph Theory

Credits:
6

Responsible person:
Kreutzer, Stephan

Grading:
benotet

Type of exam:
Mündliche Prüfung

Zugehörigkeit

Faculty:
Fakultät IV

Institute:
Institut für Softwaretechnik und Theoretische Informatik

Area of expertise:
34352200 FG Logik und Semantik

Prüfungsausschuss:
No information

Kontakt

Office:
TEL 7-3

Contact person:
Pilz, Jana

E-mail address:
stephan.kreutzer@tu-berlin.de

Website:
No information

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

Pflichtgruppe:

All Courses are mandatory.

Course Name	Type	Number	Cycle	Language	SWS	VZ
Algebraic Graph Theory	UE	3435 L 10587	SoSe	English	2
Algebraic Graph Theory	VL	3435 L 10590	SoSe	English	2

Workload and Credit Points

Algebraic Graph Theory (UE):

Workload description	Multiplier	Hours	Total
Attendance	15.0	2.0h	30.0h
Pre/post processing	15.0	4.0h	60.0h
			90.0h(~3 LP)

Algebraic Graph Theory (VL):

Workload description	Multiplier	Hours	Total
Attendance	15.0	2.0h	30.0h
Pre/post processing	15.0	4.0h	60.0h
			90.0h(~3 LP)

The Workload of the module sums up to 180.0 Hours. Therefore the module contains 6 Credits.

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 test application:

This module has no requirements.

Module completion

Grading

graded

Type of exam

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.

This module may be commenced in the following semesters:
Sommersemester.

Maximum Number of Participants

This module is not limited to a number of students.

Registration Procedures

Qispos

Recommended literature
Algebraic Graph Theory by C. Godsil and G. Royle
Graph Theory by Reinhard Diestel, Springer-Verlag

Assigned Degree Programs

This module is not used in any degree program.

Students of other degrees can participate in this module without capacity testing.

Master and bachelor students of Mathematics and Computer Science.

Miscellaneous

No information

Algebraic Graph Theory