5415/17411 Discrete Dynamical Systems - Spring 2011

[ Syllabus | Course Topics | Course Material | Supplementary Literature | Assignments | Exams ]


This course is about some of the fascinating mathematics behind modeling and analysis of dynamical processes on networks. Examples of such processes include the spread of disease on a social contact network (epidemiology), flow of data packet on a cellular phone network (tele-communication), voter processes (social science), the Ising model (statistical mechanics), and the dynamics occurring in a collection of cells (biology). Here we will use graph dynamical systems (GDSs) as a mathematical framework for these processes. Important sub-classes of GDSs include sequential dynamical systems and generalized cellular automata which include Boolean networks. Both these system classes will be explored in the course where the main focus is on the underlying mathematical theory.

A cut-and-dry definition of graph dynamical systems is given here. The fact that GDSs are discrete dynamical systems (time evolves in discrete steps, and state space is typically finite) means that the techniques used in analysis and proofs rely on for example graph theory, algebra, combinatorics and general discrete mathematics. This course offers an opportunity to see how these areas can be combined and used in the study of dynamical processes on graphs.


Instructor: Henning S. Mortveit Email: henning@vt.edu
Office I: 1111 RBXV, Corporate Research Center Phone I: (231-5327)
Office II: 419 McBryde Hall Phone II: -
Class hours: Tu/Th 9:30-10:45AM Room: McBryde 240
Prerequisite: (i) Math 3124 or Math 4124 and (ii) Math 3134 or Math 4164. Some equivalent background in graph theory, combinatorics and algebra may be acceptable; please contact me with questions.
Office hours: Hours for Office II TBD - Also by appointment in Office I/II

Texts: The main text will be the book An Introduction to Sequential Dynamical Systems by Henning S. Mortveit & Christian M. Reidys from the Springer Verlag's Universitext series. [Springer|Amazon]. This book will be supported by lecture notes and papers that will be listed below.

Lecture Notes

Lecture notes are posted on the Scholar site for this course. If you follow the course but have not been added to the Scholar site please contact Henning Mortveit via email to be added (include your VT PID).

Slide Sets


Course goals: Learn about graph dynamical systems as a mathematical framework for describing dynamical processes on graphs. Obtain a fundamental understanding of how the structure of the network, properties of vertex functions and update mechanism govern their dynamical properties.
Exams: There will be one in-class exam tentatively scheduled for March. A two-hour final exam (Section 09T) is scheduled for May 10 from 10:05PM to 12:05PM. The final exam will take place in McBryde 240 unless stated otherwise. If you cannot take an exam at the scheduled time, please let me know as soon as possible and before the exam. A make-up exam will be given for reasons that in my judgment are acceptable.
Homework: The course will tentatively have 4 assignments to be completed and handed in by their deadlines. The assignments are an integral part of this course, and the 4 assignments should be considered a minimal effort - working through additional problems is strongly encouraged.
Attendance: Graduate student policy for attendance is in effect.
Grading: Is on a curve. However, 90% will be at least an A-, 80% will be at least a B-,70% will be at least a C-, and 60% will be at least a D-. Each assignment is worth 30 points, the in-class exam 50 points, and the final exam 80 points.
Honor system: The University Honor System is in effect for assignments and exams (see http://www.honorsystem.vt.edu). Discussion of class topics among students is encouraged, but the solutions to assignments that you hand in must be your own. All exams are closed-book, closed-notes.
Students with special needs: Students with disabilities, special needs or special circumstances should meet with the instructor during the first week of classes to discuss accommodations.
General Notes: Read Professor Bud Brown's hints for learning success - available at http://www.math.vt.edu/people/brown/hints.html.)

Course topics:

The following is a tentative list of topics to be covered in the course, and it will be expanded with details as the course progresses. Some of the topics like stochastic systems and stability will be covered if time permits.

Supplementary literature:

GDS articles Algebra Combinatorics Graph Theory


Solution notes and comments will be posted here.

In-class exam: Date TBD

A PDF copy of the exam with answers will be posted here.

Final exam: May 10

A PDF copy of the exam with answers will be posted here.


Assignments, and solutions with comments are/will be posted on the Scholar site for this course. Contact Henning Mortveit for access if necessary.

Sun Dec 5 12:53:22 EST 2010