Simon Fraser University, Harbour Centre
Saturday, November 21, 2009
About the Combinatorial Potlatch
The Combinatorial Potlatch is an irregularly scheduled, floating, one-day conference. It has been held for many years at various locations around Puget Sound and southern British Columbia, and is an opportunity for combinatorialists in the region to gather informally for a day of invited talks and conversation. While most who attend work in, or near, the Puget Sound basin, all are welcome. Typically there are three talks given by speakers who are visiting or new to the area, along with breaks for coffee and lunch. Many participants remain for dinner at a local restaurant or pub.
The American Heritage Dictionary defines "potlatch" as: A ceremonial feast among certain Native American peoples of the northwest Pacific coast, as in celebration of a marriage or an accession, at which the host distributes gifts according to each guest's rank or status. Between rival groups the potlatch could involve extravagant or competitive giving and destruction by the host of valued items as a display of superior wealth. [Chinook Jargon, from Nootka p'achitl, to make a potlatch gift.]
This fall's Potlatch is being hosted by the Department of Mathematics at Simon Fraser University at their downtown Vancouver campus on Saturday, November 21, 2009.
More info, including a history and links to previous Potlatches, is at The Combinatorial Potlatch Home Page.
Schedule
All talks will be held in Room 1700 of SFU's Harbour Centre on the "Concourse Level," with registration and breaks nearby. See the Getting There section for exact locations and directions.
- 10:00 AM Registration and Coffee
- 11:00 AM Glencora Borradaile, "Graph constrained knapsack problems"
- 12:00 PM Lunch
- 2:00 PM Louis Deaett, "New dimensions to graph coloring"
- 3:00 PM Cookies, Coffee and Cokes
- 3:30 PM Omer Angel, "Locally transitive graphs"
- 4:30 PM Happy Hour, Dinner
Talks and Abstracts
Glencora Borradaile, Oregon State University
Graph constrained knapsack problems
We consider the following knapsack problem: we are given a graph representing constraints between the nodes; each node has a weight and a profit. The goal is to find a maximum-profit set of nodes of total weight at most K such that if node x is selected, then a neighbour of x is also selected. We present greedy algorithms and prove approximation guarantees that are close to optimal. Joint work with Brent Heeringa (Williams College) and Gordon Wilfong (Bell Labs).
Louis Deaett, University of Victoria
New dimensions to graph coloring
In classical graph coloring, you must assign a color to each vertex of a graph so that adjacent vertices receive distinct colors. The essential question is, of course, "How many colors do you need?" But imagine that instead of assigning colors to the vertices, you must assign vectors, with the goal that adjacent vertices be assigned orthogonal ones. Now we ask, "How many dimensions do you need?"
Omer Angel, University of British Columbia
Locally transitive graphs
What does the local structure of a graph imply about its global structure? For example, if the ball of radius 2 around every vertex x is isomorphic to the ball in the hypercube {0,1}^n, then the graph must be finite. Other local restrictions can force the graph to be infinite. (Joint with Sheffield, Silberman, Wilson).
Registration
The Combinatorial Potlatch has no sponsoring organization and no budget. And we like it that way. Consequently, there are no registration fees because we wouldn't know what to do with them. You are on your own for meals and lodging, speakers travel at their own expense and the host institution provides food for the breaks. So expressions of appreciation to the speakers and the hosts are especially encouraged. Thanks.
Getting There
SFU's Harbour Centre is located at 515 West Hastings Street, Vancouver, British Columbia V6B 5K3. More information about location and parking is available here.
Lodging
Some information about local hotels and restaurants is available now, and we will add some more specific recommendations soon.
- YWCA Hotel: reasonable rates, modest accomodations. About a half-mile walk to the conference location.
Organizers
- Rob Beezer, University of Puget Sound, beezer (at) ups (dot) edu, Communications Chair
- Nancy Ann Neudauer, Pacific University, nancy (at) pacificu (dot) edu, Program Chair
- Luis Goddyn, Simon Fraser University, goddyn (at) math (dot) sfu (dot) ca, Local Arrangements Chair