# 5415/17411 Discrete Dynamical Systems - Spring 2011

## Background

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.

## Syllabus

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

- Slide set 01 [ Presentation Version| Print Version ]

#### Papers

- Will be added during course.

**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.- Introduction:
- Background and application examples.
- Course topics overview.
- System classes: Sequential dynamical systems, Boolean networks and others.

- Phase space properties of graph dynamical systems:
- Fixed points, periodic points. Characterization and enumeration.
- Invertibility.
- Stability notions.

- Special system classes: (graphs, functions)
- Nor and Nand systems.
- Threshold systems.
- Linear systems.
- Dynamic threshold systems.

- Equivalence and neutral networks
- Functional equivalence. Enumeration and transversals.
- Dynamical equivalence.
- Orbit equivalence.

- Morphisms and system reductions
- Graph covering maps.
- The concept of simulation of systems.

- Dynamics groups
- Update sequence independent systems.

- Stability
- Examples of types of stability and relation to applications (e.g. validation and verification).

- Stochastic systems
- Examples. Sampling.
- Analysis through Markov chains.

## Supplementary literature:

**GDS articles**

- Papers from my own research are listed here.

**Algebra**

- P. B. Bhattacharya, S. K. Jain and S. R. Nagpaul,
*Basic Abstract Algebra*, Cambridge University Press. - David S. Dummit and Richard M. Foote,
*Abstract Algebra*, John Wiley. (This is the course book for 4124 Abstract Algebra.) - Thomas W. Hungerford,
*Algebra*, Springer Verlag. A classic reference.

**Combinatorics**

- Richard P. Stanley,
*Enumerative Combinatorics, Volume I*, Cambridge University Press; 2nd edition (May 2000). IBSN: 0521663512. - J.H. van Line and R. M. Wilson,
*A Course in Combinatorics*, Cambridge University Press; 2nd edition (December 2001). ISBN: 0521006015. - Cohen.

**Graph Theory**

- Reinhard Diestel,
*Graph Theory*, Springer Verlag, GTM series; 4th Edition (October, 2010).

## Exams

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

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