University of Victoria
Saturday, September 29, 2007
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 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 and Statistics at the University of Victoria in Victoria, British Columbia on Saturday, September 29, 2007.
More info, including a history and links to previous Potlatches, is at The Combinatorial Potlatch Home Page.
Schedule
All talks will be held on the University of Victoria campus in the Engineering/Computer Science Building, Room ECS 116, with registration, coffee and cookies close by. See the Getting There section for directions.
- 10:00 AM Registration and Coffee
- 11:00 AM Manley Perkel
- 12:00 PM Lunch
- 2:00 PM John Moon
- 3:00 PM Cookies, Coffee and Cokes
- 3:30 PM Anthony Quas
- 4:30 PM Happy Hour, Dinner
Talks and Abstracts
Manley Perkel, University of Puget Sound (recently Wright State University)
Antibandwidth and Cyclic Antibandwidth of Kneser Graphs
Introduced by Leung, Vornberger and Witthoff in 1984, the antibandwidth problem in graphs is to imbed an n-vertex graph G onto the path with n vertices, such that the minimum distance (measured in the path) of adjacent vertices of G is maximized. This problem can be considered as a dual to the well-studied bandwidth problem, which calls for the maximum distance to be minimized. Similarly, the cyclic antibandwith problem asks us to imbed G onto the n-vertex cycle such that the minimum distance (measured in the cycle) of adjacent vertices of G is maximized.
Since that first paper, nothing further appears to have been done on these problems until papers by Miller and Pritikin in the mid-90’s, and a couple of papers by others within the last five years.
In this talk, we first review past results and the status of these two problems. We then present recent work, joint with Pritikin and Jiang, on the antibandwith problem and cyclic antibandwidth problem, when G is the Kneser graph, K(n,k) – the graph with vertices the k-element subsets of an n-set, two such k-sets being adjacent if and only of they are disjoint. We obtain exact results when k = 2, “nearly exact” results for k = 3 and n large, and asymptotic results for k >= 4.
John Moon, University of Alberta (Emeritus)
On the Number of Proper Nodes in Rooted Trees
Let T be a rooted tree with n nodes that have been assigned the labels 1,2,…,n. We say that node v of T is a proper node if no descendant of v is assigned a label smaller than the label of v. Our main object is to investigate the mean e(n) and variance v(n) of the number of proper nodes of T over all labellings of all n-node trees T in certain families F of rooted trees. In particular, we show that if F is a simply generated family of (weighted) ordered trees whose generating function y satisfies a relation of the form y=xG(y), where G is a power series that satisfies some mild conditions, then e(n) =An+B+O(1/n) and v(n)=Cn+O(1), where A, B, and C are constants that depend on F. Explicit expressions are obtained for A, B, and C when F is a binomial family whose generating function satisfies a relation of the form y=x(1+sy)^m. (This work was done jointly with Laura L.M.Yang.)
Anthony Quas, University of Victoria
Distances in Positive Density Sets
Given a set of distances D, one can consider the graph G_{d,D} on R^d where two points are adjacent if they are separated by a distance belonging to D and ask for its chromatic number. The case where D={1} is the Hadwiger-Nelson problem and it is known that 4<=chi(G_{2,{1}})<=7. If the colour classes are required to be measurable, we obtain the measurable chromatic number \chi_m(G_{d,D}). It is known that 5<=\chi_m(G_{2,{1}})<=7.
In the case where D is unbounded, it turns out that \chi_m(G_{d,D})=\infty. We give a conceptual new proof of this and discuss possible extensions to the general (non-measurable) case.
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
All talks will be held on the University of Victoria campus in the Engineering/Computer Science Building, Room ECS 116.
The Engineering/Computer Science Building can be located on the campus map just inside the circular road at the southern end. Here is the scoop on parking, which may change as of Sept 1.
The campus is located about 7.5 km (5 miles) from central Victoria. The most convenient route from mainland US to Victoria is the Black Ball Ferry. British Columbia Ferries connect mainland Canada to Vancouver Island at Nanaimo (Swartz Bay), about 110 km (70 miles) north of Victoria. UVic's website has much more information about getting to campus. There are also more specific maps, such as bus routes or cycling routes.
Lodging
These are some ideas about lodging, which is not intended to be comprehensive.- Swans: pricey, try mentioning the conference at UVic, brewpub included
- Bedford Regency Hotel: a good compromise between convenience and cost, 33% cheaper on Expedia
- Traveller's Inns: several locations, more economical
- The Empress Hotel: just kidding
- Victoria BC Lodging.com: a longer list
Dining and Happy Hour
After Saturday's talks, we'll reconvene in town. Likely at the Canoe Club or Swans.Other ideas for dining include
Organizers
- Gary MacGillivray, University of Victoria, gmacgill (at) math (dot) uvic (dot) ca, Local Arrangements Chair
- Nancy Ann Neudauer, Pacific University, nancy (at) pacificu (dot) edu, Program Chair
- Rob Beezer, University of Puget Sound, beezer (at) ups (dot) edu, Communications Chair