Dr. Ronald Graham
28th Kieval Lecture
Thursday, March 27, 1997
8:00 p.m., Science Bldg. B, Room 135

Searching for Efficient Networks

There are many situations in which one would like to connect a collection of points together by a network having the minimum possible total ength. Such problems occur in the design of telephone networks, railroad lines, oil and gas pipeline networks, heating and air-conditioning duct systems, and the layout of circuits on VLSI chips, for example. In this talk we give a summary of what is known (and unknown) about this problem, and how current developments in computer science have impacted it.

Math Colloquium:
Thursday, March 27, 1997
4:00 p.m., Goodwin Forum, Nelson Hall East, Room 102
(pre-colloquium tea from 3:30-4:00 p.m., Goodwin Forum)
The Mathematics of Juggling

In a certain sense, the art of juggling is a physical realization of many of the principles that mathematicians and computer scientists know and love. These include the search for patterns, the design and analysis of appropriate algorithms, and the prospect of facing problems of unbounded difficulty. In particular, juggling is typically a very discrete activity, and as such, is governed by a rich family of combinatorial constraints.
Recently, a new and unexpectedly simple way of describing juggling patterns has been discovered. This has led to a bewildering array of previously unknown patterns, as well as several new combinatorial theorems relating linear extensions of partially-ordered sets to chromatic polynomials of associated graphs. In this talk we will describe these developments, and attempt to demonstrate some of these new tricks.