 |
Abstract: Consider the following seemingly unrelated problems:
1. You have a network of some kind, e.g. electrical, water supply, transportation, internet connections, etc. The individual linkages fail with some known probability. Can you predict the probability of the network itself failing?
2. Several courses are offered which the registrar's office must assign to rooms. The registrar's office wants to use the classroom space as efficiently as possible, but some of the course times conflict with one another. What is the fewest number of classrooms needed to accommodate all the courses?
3. You have a sheet of some physical material (e.g. a metal) with a magnetic field and given temperature. The magnetic orientations at lattice points approximating this sheet change, but are influenced by the orientations of their neighbors. Furthermore, the magnetism seems to `melt away' as the temperature passes a critical point. How do you model the behavior of such a system?
Not only can all of these problems (like many others) be modeled by graphs, but they all have a special kind of reduction that simplifies the problem. If G is a graph that models the problem, then the answer is a (weighted) sum of the two graphs you get by deleting and contracting an edge of G. This process can then be repeated on the two new graphs, and so on, until there are no edges left and you can read off the answer.
The Tutte polynomial is a two-variable graph polynomial with the universal property that essentially any graph invariant that can be computed via a deletion-contraction reduction must be an evaluation of it. Because of the richness of its applications, the Tutte polynomial is a well-studied object. This means that there is a lot of information available for any problem that can be shown to have a deletion-contraction reduction.
For the examples above, this is good news and bad news.
This talk will be accessible to undergraduates.
|