The Pacific Institute for the Mathematical Sciences launched a new web site on March 31, 2005. If there is any discrepancy between the information on this page and the new site, the information on the new site should be used.

COMBINATORIAL POTLATCH 2004

Saturday 20 November 2004

Room 1700, Labatt Hall
SFU Harbour Centre Campus
515 West Hastings Street
Vancouver

Sponsored by SFU and PIMS

---

Combinatorial Potlatches have been held for many years at various locations around Puget Sound and southern British Columbia, and are an opportunity for combinatorialists to gather informally for a day of invited talks and conversation.  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.]

REGISTRATION:

Registration is free but let us know you are coming by registering online.

SCHEDULE:

9:30-10:20	coffee
10:20	opening
10:30-11:30	Xuding Zhu (National Sun Yat-sen University, Taiwan) The game chromatic number of a graph
11:30-13:30	lunch (many restaurants in the area)
13:30-14:30	John Gimbel (University of Alaska Fairbanks) The traveling sales rep gets into abelian groups
14:30-15:00	coffee break
15:00-16:00	Jozsef Solymosi (University of British Columbia) Bounds on incidences and problems from additive number theory
16:00-	social event (optional)

ABSTRACTS:

XUDING ZHU (National Sun Yat-sen University, Taiwan)
The game chromatic number of a graph

Two players, Alice and Bob, alternately colour the vertices of a graph G with colours from a colour set C. Adjacent vertices must be coloured by distinct colours. The game ends if either all vertices are coloured or there is no legal colour for the remaining uncoloured vertices. Alice wins the game if all vertices are coloured, and Bob wins otherwise. The game chromatic number of G is the least number of colours in the colour set C so that Alice has a winning strategy for this game. The problem of calculating the game chromatic number of planar graphs first appeared in Martin Gardner's columns "Mathematical Games" (contributed by Steven Brams) in 1981. In 1991, it was independently introduced by Hans Bodlaender, whose interest was to study the complexity of the game. In recent years, the problem has attracted some attention from graph theorists, where the main interest is the maximum values of the game chromatic number for various classes of graphs. In this talk, I will explain a particular strategy for Alice to play such a game. For many classes of graphs, including forests, outerplanar graphs, planar graphs, partial k-trees, the best upper bounds on the game chromatic number are proved by using this strategy.

JOHN GIMBEL (University of Alaska Fairbanks)
The traveling sales rep gets into abelian groups

We consider graphs where the edge set is labeled with elements from an abelian group. Special attention is paid to labellings where the sum of edges in the hamiltonian cycles is constant. We pay particular attention to the group of real numbers with addition. We will further focus attention on complete graphs, cubes and complete bipartite graphs. When restricted to these families, the concept is equivalent to some rather simple properties which are easy to test.

JOZSEF SOLYMOSI (University of British Columbia)
Bounds on incidences and problems from additive number theory

There are interesting connections between some problems in additive number theory and incidence problems in discrete geometry. It is an old conjecture of Erdos, that if A is an n-element set of numbers, then the sumset, A+A, or the product-set, A*A, should be "large", almost n^2. Using a result of Szemeredi and Trotter about the bound on the maximum number of incidences between lines and points on the plane, we show that |A+A|+|A*A|> n^{14/11}/log n, improving earlier bounds. If time permits, we will see further examples.

ACCOMMODATION SUGGESTIONS:

Here are some suggestions:

Budget:
YWCA Hotel/Residence 733 Beatty Street, http://www.ywcahotel.com/
Sandman Hotel, 180 West Georgia, http://www.sandmanhotels.com/hotels/bc/vancouver.asp

Moderate:
Ramada, 435 West Pender Street, http://www.ramadadowntownvancouver.com/
Holiday Inn, 1110 Howe Street, http://www.ichotelsgroup.com/h/d/HIIS/hd/YVRDT

Expensive:
Delta Vancouver Suites, 550 West Hastings Street, http://www2.deltahotels.com/hotels/hotels.php?hotelId=21
Fairmont Waterfront Hotel, 900 Canada Place Way, http://www.fairmont.com/waterfront/
Pan Pacific Hotel, 300-999 Canada Place Way, http://vancouver.panpacific.com/

Some other useful links:
Harbour Centre SFU, http://www.harbour.sfu.ca/
BC Ferries, http://www.bcferries.com/
Translink - Public Transit, http://www.translink.bc.ca
Vancouver International Airport, http://www.yvr.ca
Harbour Air, http://www.harbour-air.com/
Tourism Vancouver, http://www.tourismvancouver.com/
Vancouver weather, http://weatheroffice.ec.gc.ca/forecast/city_e.html?yvr

CONTACT ORGANIZER:

Any questions about this event should be emailed to Petr Lisonek plisonek AT cecm.sfu.ca.

---

© 2007 Pacific Institute for the Mathematical Sciences Last Modified: Monday, 25-Oct-2004 21:51:01 PDT