4984 Mathematics of Computer Simulations: Background

The use of discrete mathematics is becoming increasingly more wide-spread in applied mathematics. The motivation for this course is the space and time discrete dynamical system models used in simulation and analysis. Application examples include traffic models of entire cities (Transims), disease dynamics in social networks (Episims), and models of biological systems such as the immune system (Celada-Seiden model).

This course is about the mathematical structures and properties of the discrete dynamical systems used in the simulation models above. Through the framework of sequential dynamical systems and generalized cellular automata the course gives a thorough introduction to mathematical results and techniques that can be used to analyze these systems. In contrast to the continuous dynamical systems you may have seen in other courses, the techniques in this course are based on abstract algebra, combinatorics and graph theory. The course offers a great opportunity to learn how all these areas can be combined to analyze finite dynamical system.

Course Information (Spring 2007)

Instructor:	Henning S. Mortveit
Office I:	Corporate Research Center, Building XV, Room 1111
Office II:	McBryde 419
Phone:	(540) 231-5327
Email:	hmortvei@math.vt.edu
Web:	4983-15748.html

Time and Place: 9:30-10:45AM TR, McBryde Hall 207

Office Hours: Tuesdays and Thursdays 11:00-12:00 (McBryde 419).

Practical information (subject to change):

Assignments: There course has four written assignments. Additionally there are two computer assignments that can be applied as extra credit.

Text/course material: The course has no required text and is based on lecture notes that will be made available from this page or that will be distributed by email to the students. The following is a list of references that may be helpful as supplementary material. Feel free to ask me about additional references.

• Graph Theory:
  • R. Diestel: "Graph Theory", GTM vol. 173, Springer-Verlag. (Electronic version available here)
  • C. Godsil and G. Royle: "Algebraic Graph Theory", GTM vol. 207, Springer-Verlag. (A more advanced book.)
• Combinatorics:
  • Daniel Cohen: "Basic Techniques of Combinatorial Theory", John Wiley and Sons Inc, 1979. (Excellent introductory level book. Out of print.)
  • J. H. van Lint and R. M. Wilson: "A Course in Combinatorics", Cambridge University Press, 2nd edition.
  • J. Riordan: "Introduction to Combinatorial Analysis", Dover Publications. (Many recommend this book - I have not studied it.)
  • R.P. Stanley: "Enumerative Combinatorics: Volume 1", Cambridge University Press. (An excellent book on combinatorics. More advanced than the two first books.)
• Dynamical System Theory:
  • M.W. Hirsch, S. Smale, R. Devaney: "Differential Equations, Dynamical Systems, and an Introduction to Chaos", Academic Press. (Supposedly a good book. I have only studied the older book by the first two authors.)
  • R.L. Devaney: "An Introduction to Chaotic Dynamical Systems" (A graduate level book on the dynamics of iterated maps from a chaos perspective.)

Exams, Tests, Assignments, and Grading:

• Final exam: There will be a final exam on Wednesday, May 08. The exam is worth 35 pts. Mid-term exam: There will be a mid-term exam worth 25 pts on 03/01/06. If you cannot take the tests at the scheduled times, please let me know as soon as possible and before the tests. A make-up test will be given for reasons that in my judgement are acceptable.
• Assignments: There will be four written assignments for regular credit (10 pts each) and two computer-based assignments for extra credit (5 pts each). Late homework may not be accepted.
• 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-.

Attendance: Will be taken, and will be kept for Mathematics Department records. It may be applied as extra credit.

Prerequisites:

• 3034 Introduction to Proofs,
• 3124 Modern Algebra, and
• 3144 Linear Algebra I

or equivalents courses, or permission from the instructor. The two last courses can be taken in the same semester as this course.

Having taken 3134 Applied Combinatorics and Graph or some other course in combinatorics or graph theory may be helpful, but is not necessary.

Honor System. The University Honor System is in effect for in-class tests and exams.

Course Schedule Spring 2007 (Updates posted here)

Week	Days	Topics	Assignments/Exams
03	01/16, 01/18	Introduction to finite dynamical systems and applications. Examples of Sequential Dynamical Systems and Cellular automata. Application examples.
04	01/23, 01/25	Sequential Dynamical Systems and Generalized Cellular Automata. Definitions, terminology and examples.
05	01/30, 02/01	Reversible SDS. Characterization and enumeration of fixed points.
06	02/06, 02/08	Functional equivalence. Update graphs. Stanley's enumeration formula for acyclic orientations.	Assignment 1 due 02/06
07	02/13, 02/15	Last week ctd. Dynamical Equivalence. Orbit graphs. Combinatorial bounds.
08	02/20, 02/22	Last week ctd.	Assignment 2 due 02/22.
09	02/27, 03/01	Summary and examples. Midterm exam	Computer Assignment 1 due 02/27. Midterm exam 03/01
10	03/06, 03/08	Spring break.
11	03/13, 03/15	Dynamical equivalence continued. Applications of graph dynamical systems.
12	03/20, 03/22	Applications of graph dynamical systems continued. Special systems (Nor, Nand, Parity).
13	03/27, 03/29	Special systems continued. SDS with update order independent periodic points.	Computer Assignment 1 due 03/29
14	04/03, 04/05	SDS with update order independent periodic points continued. Dynamics groups.	Assignment 3 due 04/05.
15	04/10, 04/12	Linear graph dynamical systems.	Computer assignment 2 due 04/12
16	04/17, 04/19	Reduction of SDS through graph covering maps and examples of graph covering maps.
17	04/24, 04/26	To be announced.	Assignment 4 due 04/24
18	05/01	Summary
19	05/08		Final Exam

Sequential Dynamical Systems Literature

• R. Laubenbacher and B. Pareigis, Update schedules of sequential dynamical systems. Discrete Applied Mathematics, 154(6):980-994, 2006.
• L.D. Garcia, A.S. Jarrah and R. Laubenbacher, Sequential Dynamical Systems over Words. Applied Mathematics and Computation, 174(1):500-510, 2006.
• A.A Hansson, H.S. Mortveit and C.M. Reidys, On Asynchronous Cellular Automata. Advances in Complex Systems, 8(4):521-538, 2005.
• C.M. Reidys. On Certain Morphisms of Sequential Dynamical Systems Discrete Mathematics 296(2-3):245-257, 2005.
• W.Y.C. Chen, X. Li and J. Zheng. Matrix method for linear sequential dynamical systems on digraphs. Appl. Math. and Comput., 160:197--212, 2005.
• O. Colon-Reyes, R. Laubenbacher and B. Pareigis, B. Boolean Monomial Dynamical Systems (preprint version) Annals of Combinatorics, 8:425-439, 2004.
• H.S. Mortveit and C.M. Reidys. Reduction of Discrete Dynamical Systems over Graphs. Advances in Complex Systems, 7(1):1-20, 2004.
• H.S. Mortveit and C.M. Reidys. Neutral Evolution and Mutation Rates of Sequential Dynamical Systems. Advances in Complex Systems, 7(3-4):395-418, 2004.
• C.L. Barrett, H.S. Mortveit, and C.M. Reidys. ETS IV: Sequential Dynamical Systems: fixed points, invertibility and equivalence. Appl. Math. and Comput., 134(1):153-171, 2003.
• C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz and R.E. Stearns. Reachability problems for sequential dynamical systems with threshold functions. Theor. Comput. Sci. 1-3:41-64, 2003.
• C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz and R.E. Stearns. On some Special Classes of Sequential Dynamical Systems Annals of Combinatorics. 7:381-408, 2003.
• R. Laubenbacher and B. Paraigis. Decomposition and simulation of sequential dynamical systems Adv. Appl. Math., 30:655-678, 2003,
• H.S. Mortveit and C.M. Reidys. Towards a calculus of biological networks Z. Phys. Chem. 216(2):235-247, 2002.
• C.M. Reidys. Covering maps over n-cubes. Annals of Combinatorics 6(3-4):419-426, 2002.
• H.S. Mortveit and C.M. Reidys. Discrete, Sequential Dynamical Systems. Discrete Mathematics, 226(1-3):281-295, 2001.
• R. Laubenbacher and B. Paraigis. Equivalence relations on finite dynamical systems Adv. Appl. Math. 26:237-251, 2001.
• C.L. Barrett, H.S. Mortveit, and C.M. Reidys. Elements of a Theory of Simulation III: Equivalence of SDS. Appl. Math. and Comput., 122(3):325-340, 2001.
• C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, and R.E. Stearns. Analysis Problems for Sequential Dynamical Systems and Communicating State Machines. MFCS 2001, 159-172.
• C.M. Reidys. On Acyclic Orientations and Sequential Dynamical Systems Advances in Applied Mathematics, 27(4):790-804, 2001.
• C.L. Barrett, H.S. Mortveit and C.M. Reidys. Elements of a Theory of Simulation II: Sequential Dynamical Systems. Appl. Math. and Comput., 107(2-3):121-136, 2000.
• C.L. Barrett and C.M. Reidys. Elements of a theory of simulation I: Sequential CA over random graphs Appl. Math. and Comput., 98(2-3):241-259, 1999.
• C.M. Reidys. Acyclic Orientations of Random Graphs Advances in Applied Mathematics, 21(2):181-192, 1998.

© Copyright 2002 – 2006, Henning S. Mortveit, all rights reserved. Some images may not display correctly in older browsers.