|10:00-11:00||Welcoming reception (David Strong Building - in the foyer)|
|11:00*||Andrzej Proskurowski, University of Oregon|
Width parameters of graphs and discrete optimization problems
Abstract: Optimization problems on graphs are often expressed in some formalism: logic, algebra, graph rewriting. Sometimes, such formalisms have corresponding classes of graphs for which these problems are efficiently solvable even when they are intractable in general. Examples of such graph classes are those with bounded "width" parameters: the pre-classical bandwidth, classical branchwidth, treewidth and pathwidth, fairly recent cliquewidth. Often, classes of graphs defined by some structural properties have bounded width parameter values. Exploring these interplay of problems, graphs and width parameters is the main theme of my talk.
|12:00-2:00|| Lunch - participants on their own.|
Place to eat around campus (pdf file).
|2:00-3:00||Branko Grunbaum, University of Washington|
Polyhedra: Combinatorial and Geometric
Abstract: The theory of convex polyhedra (and their higher-dimensional analogues) has been developed in great detail and depth during the last fifty years. In contrast, nonconvex (that is, not necessarily convex) polyhedra have been only sporadically discussed, and the understanding of the topic is unsatisfactory. The reason for this situation is that there has never been a precise delineation of the concepts involved and that stunning logical errors were committed by respected researchers. The talk will address these issues, and present an approach to nonconvex polyhedra that is internally consistent, has been useful in several previously unsettled problems, and leads to open questions that are susceptible to reasonable solutions.
|3:00-3:30||break (David Strong Building Building - in the foyer)|
|3:30-4:30||Jozef Siran, Slovak University of Technology|
Links between graph theory, group theory, geometry, Riemann surfaces, and Galois theory
Abstract: There are fascinating connections between graphs embedded on surfaces, groups acting on embedded graphs, hyperbolic geometry, complex functions, and Galois theory. In the talk we will attempt to give at least a partial survey of basic ideas behind these connections.
|4:30-6:30||Beer at some pub.|
* or whenever the daytrippers from Vancouver arrive.
Pacific Institute for
the Mathematical Sciences
Last Modified: Thursday, 07-Nov-2002 14:21:58 PST