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
VancouverSponsored 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 graph11: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 groups14:30-15:00 coffee break 15:00-16:00 Jozsef Solymosi (University of British Columbia)
Bounds on incidences and problems from additive number theory16:00- social event (optional) ABSTRACTS:
XUDING ZHU (National Sun Yat-sen University, Taiwan)
The game chromatic number of a graphTwo 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 groupsWe 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 theoryThere 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:
Some other useful links:
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/
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?yvrCONTACT 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