DREI '99
PRELIMINARY SYLLABUS
Barry Tesman
I.1. An Introduction to Graph Theory
Games and graphs - a natural connection. Definitions (lots of them), digraphs, & games of chance.
I.2. Connectivity
Connectivity in graphs and digraphs. k-, dis-, strongly, unilaterally, and weakly connected.
I.3. Matchings & Decomposition
Decomposition of graphs (in particular, 1-factors and cycles). Maximum and perfect matchings. Eulerian and Hamiltonian graphs.
I.4. Matchings & Colorings
Coloring the edges and/or vertices of a graph.
I.5. Matchings & Marriages
Stable marriages.
II.1. Another Introduction to Graph Theory
Graph theory from a linear algebra perspective.
II.2. N-Person Games
n players try to reach agreement about possible outcomes. The "core" as a solution.
II.3. Stability and Domination
Stability and domination.
II.4. Markov Chains
Stochastic (vs. deterministic) processes. A. A. Markov and his chains.
II.5. Applications
More applications of the week's materials.
III.1. Dr. Ecco
A lecture by Dr. Lui using The Puzzling Adventures of Doctor Ecco.
III.2. Binary Relations
Properties of binary relations and their graph theoretic interpretation.
III.3. Order Relations
Various order relations (e.g., weak, simple) and their applications.
III.4. Posets
Partially ordered sets and lattices. Hasse diagran
III.5. Dimension
Linear extensions of posets and dimension. A j ob-scheduling application.