DCI '01
PRELIMINARY SYLLABUS
Barry Tesman
Education Program Director
I.1. Introduction: Games and graphs - a natural connection.
Definitions, digraphs and games of chance.
I.2. Connectivity
Connectivity in graphs and digraphs. k-, dis-, strongly, unilaterally and weakly connected.
I.3. Decomposition and Matchings
Decomposition of graphs (in particular, 1-factors and cycles). Maximum and perfect matchings. Eulerian and Hamiltonian graphs.
I.4. Matchings and Colorings
Coloring the edges and/or vertices of a graph.
I.5. Matchings and Marriages
Stable marriages.
II.1. Stability and Domination
Stability and domination.
II.2. Markov Chains
Stochastic (vs. deterministic) processes. A.A. Markov and his chains.
II.3. Dr. Ecco
The Puzzling Adventures of Doctor Ecco.
II.4. Binary Relations/Order Relations/Posets
Properties of binary relations and their graph theoretic interpretation. Various order relations (e.g., weak, simple) and their applications. Partially ordered sets and lattices. Hasse diagrams and dimension.
II.5. Applications
More applications of the week's materials.