Combinatorial Potlatch 2011
Seattle University
Saturday, November 19, 2011

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 Seattle University in Seattle, Washington on Saturday, November 19, 2011.

More info, including a history and links to previous Potlatches, is at The Combinatorial Potlatch Home Page.

Schedule

All talks will be held in Wyckoff Auditorium, located in the Engineering Building, with registration and breaks nearby. See the Getting There section for exact locations and directions.

  • 10:00 AM Registration and Coffee
  • 11:00 AM William Stein - Sage
  • 12:00 PM Lunch
  • 2:00 PM Josh Laison - Obstacle Numbers of Graphs
  • 3:00 PM Cookies, Coffee and Cokes
  • 3:30 PM Peter Winkler - Cop vs. Drunk
  • 4:30 PM Happy Hour, Dinner

Talks and Abstracts

William Stein, University of Washington, Seattle

Sage - Creating a viable free open source alternative to Magma, Maple, Mathematica and Matlab

Sage (sagemath.org) is free open source software for doing mathematics that I started in 2005, to which hundreds of people have subsequently contributed as the project has steadily grown in popularity. I will describe my motivation for starting the project, the overall structure of the project today, and give a demo that showcases Sage.

Josh Laison, Willamette University

Obstacle Numbers of Graphs

Arrange some vertices in the plane, and some polygon "obstacles", and construct a graph by drawing a straight line edge between vertices whenever it doesn't intersect an obstacle. Given a graph, how many obstacles do you need to construct it in this way? By placing a tiny obstacle in the way of each desired non-edge, you can construct any graph with n vertices using at most n^2 obstacles. Can you do it with only n obstacles? Can you do it with only 1 obstacle? We'll answer a subset of these questions, and also consider variations on the problem where the obstacles are required to be convex polygons, line segments, or even just points in the plane. Along the way we'll see some neat connections to Ramsey numbers, the Happy Ending Theorem, visibility graphs, circular arc graphs, and more! Joint work with Hannah Alpert and Christina Koch as part of the Willamette Valley REU program.

Peter Winkler, Dartmouth College, Microsoft Research

Cop vs Drunk: Chasing the Random Walker on a Graph

A "cop" and a "drunk" begin at vertices of a connected graph G on n vertices. They alternate taking steps; the drunk moves randomly, while the cop sees all and wants to close in for an arrest. How long can this take (in expectation) in the worst case? This question, posed by U Vic grad student Ross Churchley, leads to some surprising observations. With Dartmouth grad student Natasha Komarov, we show that a smart cop can succeed in time n+o(n).

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 facilities and food for the breaks. So expressions of appreciation to the speakers and the hosts are preferred and especially encouraged. Thanks.

Getting There

Seattle University is extremely close to downtown Seattle, so there should be little trouble arranging transportation. The nearest major airport is Seattle-Tacoma International (SEA).

Seattle University's driving directions to campus from various directions.

Official word on campus parking is: "For visiting people who wish to pay for parking, since your event is on a Saturday, parking is $8 for all day parking. They will have to park in the Murphy Garage, or they can go to the 12th and Marian booth and purchase parking and see if there are spots in that main lot first." Murphy Garage is on the south side of James Way, at A1 on the campus map. The campus is very compact, and on the weekend you might find on-street parking close-by, such as on 12th Avenue.

The venue for all talks, registration and breaks is Wyckoff Auditorium, room ENGR 200 in the Engineering Building. This is just south of the central quad, in quadrant C1 of the campus map.

More Campus Maps.

Lodging

Any hotel in downtown Seattle will be a short taxi ride away from Seattle University. Downtown hotels near Madison Street will be about a one-mile walk away.

The Silver Cloud Inn is directly across the street from the campus, while the Sorrento Hotel is a nice compromise between campus and downtown, sitting atop First Hill.

  • Sorrento Hotel Call 800-426-1265 or 206 622-6400 and ask for the Seattle University Rate. At this time the November rates are: standard room from $139.00+tax per night, junior Suite from $189.00+tax per night. Parking is reportedly $40, so check on this if it matters.
  • Silver Cloud Inn Until November 7th, call 800 590-1801 or 206 325-1400 and ask for the Combinatorial Potlatch Rate which will be $119.00+tax per night.

Dining and Happy Hour

TBA: Lunch, Dinner and Happy Hour suggestions

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
  • David Neel, Seattle University, neeld (at) seattleu (dot) edu, Local Arrangements Chair
Last updated: November 14, 2011, http://buzzard.ups.edu/potlatch/2011/potlatch2011.html