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.