Combinatorial Potlatch

November 9, 2002
University of Victoria
Victoria, BC Canada


Lectures will take place in the David Strong Bulding - Room 116.

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:00Branko 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:30Jozef 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.

© 2007 Pacific Institute for the Mathematical Sciences
Last Modified: Thursday, 07-Nov-2002 14:21:58 PST