Saturday, November 19, 2005
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 two or 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.]
More info, including a history and links to previous Potlatches, is at The Combinatorial Potlatch Home Page.
- 10:00 AM Registration, Coffee and Donuts
- 11:00 AM Bojan Mohar, Small Separations in Symmetric Graphs
- 12:00 PM Lunch
- 2:00 PM Jenny Quinn, Determinants Via Determined Ants
- 3:00 PM Cookies, Coffee and Cokes
- 3:30 PM John Caughman, How Distance-Regular Graphs Got All Tangled Up with the Theory of Knots
- 4:30 PM Happy Hour, Dinner
Bojan Mohar, University of Ljubljana (Slovenia) and Simon Fraser University
Small Separations in Symmetric Graphs
The study of expansion in vertex transitive graphs and in groups divides naturally into the study of local expansion, or connectivity, and the study of global expansion (the growth). The expansion properties of a group are those of its Cayley graphs, and vertex transitive graphs are a more general setting.
There are a number of classic results concerning local expansion in vertex transitive graphs. For instance, a result of Mader shows that every finite connected d-regular vertex transitive graph is d-edge-connected. This result was refined by Lovasz and Watkins who proved that if S is a d-edge-cut in a simple finite connected vertex transitive graph of degree d and A is the smallest component in G-S, then either A is a singleton, a clique of size d (which forms a block of imprimitivity), or d=2 (so the graph is a cycle) and A is a path. There are analogues of the above theorems for digraphs and vertex cuts.
Some new results, a joint work with Matt DeVos, about local expansion in vertex transitive graphs will be presented. They are also meaningful for groups, and have some asymptotic applications. The goal is to prove a rough structure theorem for small cuts which is close in spirit to the Lovasz-Watkins result. Our main theorem gives rough structure of vertex-cuts of bounded size in arbitrary vertex transitive graphs.
Jenny Quinn, Occidental College and University of Puget Sound
Determinants Via Determined Ants
Determinants of n x n matrices will be understood combinatorially by marching n ants along the arcs of a directed graph. Using this approach, we tackle determinantal identities involving Fibonacci numbers, binomial coefficients, and more. Thus providing more evidence to support Ernst Mach's belief that "There is no problem in all mathematics that cannot be solved by direct counting."
John Caughman, Portland State University
How Distance-Regular Graphs Got All Tangled Up with the Theory of Knots
For more than a century, the theory of knots has inspired much work in algebraic topology and geometry. More recently, however, graph theory and combinatorics have begun to play an increasingly important role. In 1990, Vaughn Jones won the Fields medal for his work introducing methods from statistical mechanics to the study of knots. His work introduced not only the famous Jones polynomial, but also a more general link invariant constructed using a combination of two things: a graph representing the knot (called the Tait graph of the knot), and a particularly nice kind of matrix, known as a spin model.
The connection to graph theory goes deeper than just the Tait graph, however. In 1996, Francois Jaeger discovered that spin model matrices are always contained in a certain kind of matrix algebra, and this algebra was often the adjacency algebra of some graph. For the construction to work, however, the graph would have to be distance-regular. It is natural then to ask WHICH distance-regular graphs contain a spin model matrix in their adjacency algebra. Several known families exist, and it is conjectured that the known list is complete. This question remains open.
In this talk we intend motivate this connection to graph theory and to give a broadly comprehensible introduction to this exciting field of study.
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. It also greatly helps the hosts if you can send a quick email if you plan to attend, so they can accurately plan the amount of food to order. In this case, please contact David Neel (neeld (at) seattleu (dot) edu) to confirm your attendance. Thanks.
The day's activities will occur in, and close by, Room 102 of the Bannan Building (#14 on the campus map linked below).
First choice for parking is the Pigott lot (P7 on campus map), second choice is the Murphy Lot at 11th and Cherry (P2 on campus map). Purchase permits at the yellow pay box centrally located in the Pigott Parking Lot or on the first floor of the Murphy Parking Garage. Visitor parking fees are as follows: $5.50 for 0-4 hours, $6.50 for 4-6 hours, and $7.50 for 6-24 hours. The pay box accepts cash, Visa, and Mastercard. On-street parking in the vicinity might also be a possibility.
The Silver Cloud Hotel is just across the street from the university, and is within an easy mile's walk of both downtown Seattle to the west and the vibrant Broadway neighborhood to the north. Online reservation rate is $119/night. Or you can telephone Marita at the Silver Cloud at 800-590-1801 or 204-1183 (local) and mention the "Combinatorial Potlatch Conference" to get the same rate.
The Sorrento Hotel is a few blocks away from campus. It is very nice, at the top of the hill overlooking downtown and Elliott Bay, and is priced accordingly.
Wyndham Suites is about a 15 minute walk from campus.
The major downtown Seattle hotels are all about a 25-30 minute walk to campus.
We have reserved some tables for lunch at the Elysian Brewing Company and there will be other options as well for lunch. A list of suggested close-by locations for lunch and dinner will be available at the meeting.
There will be a no-host Happy Hour at Bad Juju Lounge after the last talk and lasting until folks disperse for dinner.
- David Neel, Seattle University, neeld (at) seattleu (dot) edu, 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