Colloquia — Summer 2003
Thursday, June 5, 2003
| Title |
Semigroups and the Road Coloring Problem |
| Speaker |
Professor Greg Budzban
Southern Illinois University, Carbondale |
| Time |
3:00-4:00 p.m. |
| Place |
PHY 108 |
| Sponsor |
Professor J. Ratti |
Abstract
Suppose one is given a strongly connected, aperiodic directed graph. Think of
the vertices of the directed graph as buildings connected by unnamed one-way
roads, and assume there is a person in each building. Under what conditions
can one color (that is, name) the roads, so that the same set of instructions
gets each person to the same building at the same time.
The problem above is known as the road coloring problem and has been open for
almost thirty years. Recent efforts to solve the problem use algebraic methods,
and the speaker will describe an approach using semigroup theory. Properties
of the digraph will be given semigroup formulations and it will be shown how
the structure of the minimal ideal of the “coloring semigroup” plays
a critical role in the analysis of the problem. Recent results will be surveyed
and a generalization of the problem to periodic graphs will be discussed.
Friday, May 16, 2003
| Title |
On the existence of nontrivial solutions in some elliptic
equations with slowly growing principal operators |
| Speaker |
Professor Khoi Le Vy
University of Missouri - Rolla |
| Time |
4:00-5:00 p.m. |
| Place |
PHY 118 |
| Sponsor |
Professors A. Kartsatos |
Abstract
We are interested in the existence of nontrivial solutions of mountain pass
type for certain quasilinear elliptic equations. Our main tool is a version
of the Mountain pass theorem for variational inequalities, without the
Palais-Smale condition, in some appropriate Orlicz-Sobolev space.