SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Graph Polynomials and their Applications - NDMI101
Title: Graph Polynomials and their Applications
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: cancelled
Language: English
Teaching methods: full-time
Teaching methods: full-time
Guarantor: prof. RNDr. Martin Loebl, CSc.
Class: Informatika Bc.
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: doc. Mgr. Jan Kynčl, Ph.D. (05.05.2019)
In this course for advanced undergraduates and graduates given by Fulbright-Charles University Distinguished Chair Prof. Ellis-Monaghan, the Tutte polynomial is used to showcase a variety of principles and techniques for other graph polynomials and related topological invariants. Applications include statistical physics, knot theory and DNA sequencing.
Literature -
Last update: doc. Mgr. Jan Kynčl, Ph.D. (04.05.2019)

J. Ellis-Monaghan, C. Merino, Graph polynomials and their applications I: the Tutte polynomial, in Structural Analysis of Complex Networks, Matthias Dehmer, ed., Birkhauser, 2010.

J. Ellis-Monaghan, C. Merino, Graph polynomials and their applications II: interrelations and interpretations, in for Structural Analysis of Complex Networks, Matthias Dehmer, ed., Birkhauser, 2010.

Syllabus -
Last update: doc. Mgr. Jan Kynčl, Ph.D. (04.05.2019)

The Tutte polynomial. Several definitions and universality.

Evaluations and specializations of the Tutte polynomial.

Multivariable and topological generalizations of the Tutte polynomial

Applications of the Tutte polynomial

Transition, Martin, and Penrose polynomials.

The generalized transition polynomial with multivariable and topological extensions.

The interlace polynomial

Applications to DNA sequencing and DNA self-assembly.

Connections with knot theory.

Independence, characteristic, and matching polynomials.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html