The goal of this course is to study ``real-world'' applications of combinatorics. These include such topics as scheduling of airline crews and equipment, routing of delivery services, layout of telecommunications networks, analysis of RNA folding, and the design of technological development strategy.
This semester our text is The Web as a Graph, by A. Bonato, published in 2008. Graph theory will be our main tool and it is a picturesque subject in the sense that it can be easily visualized through simple schematic drawings with two basic elements - nodes and links. Adding in numerical information attached to nodes and links, such as capacity, cost, importance, and reliability, one obtains the notion of a network, which is a graph that carries additional structure. Furthermore, links may also carry a sense of direction - e.g., one neuron may have a synapse which influences another neuron, so directed links ("arcs" in the usual terminology) are natural for models of neuronal networks. The World Wide Web can be seen as a graph in which the nodes are the web pages and the directed links are the hyperlinks in the html code.
Bonato's book focuses on the World Wide Web (WWW). This necessarily includes the theory of stochastic processes since the WWW is not a static graph but is constantly changing and uncertain - like most large graphs which occur in applications. To avoid heavy prerequisites, we will mostly take the probabilistic results on faith without analyzing the proofs too carefully.
One of the advantages of mathematics is that the same tools can be applied to quite different situations. The idea of a random graph has recently been studied in the context of ``small-world networks'' and so we will also look beyond the specifics of the WWW to more general examples of complex stochastic graphs.
The initial assignment for students is to read the section of Chapter 1 on Graph Theory (pp. 2--9), but beware! There are misprints, and I will give the munificent sum of 25 cents to the first person who finds and corrects each of them. Actual mistakes (detected and corrected) are worth 50 cents. However, I reserve the right to cancel this policy if I start to run out of money.
It is vital to have a trustable text, so I am also going to give you a copy of relevant portions of Harary's classic book (Graph Theory) published in 1969. He was a great expositor and he uses the terminology which is now standard (and used in our book). Our reading of Bonato's book will be more adversarial (as we find and patch the mistakes), critical (as we improve and clarify his arguments), but also inspirational (since he is tackling some very difficult and socially valuable problems). All of these aspects should be helpful to you as students.
The course is intermediate-level, so both undergrads and graduate students can take it. If you have previously taken a course in graph theory or combinatorics, then you will be well prepared for this course, but in fact these days practically everyone has familiarity with networks - highways, cell phones, and computers. So students with good ``mathematical maturity'' should find the material quite accessible even without a prior course on networks or combinatorics.
This is an advanced class; I expect all students to work hard and to have fun! Many of our investigations will lead up to open problems, both in mathematics and in its applications. These may lead some of you to exciting projects, either for class, for an honor's thesis, or for consulting/practicum.