Combinatorial Potlatch 2014
Western Washington University
Saturday, November 22, 2014

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 Western Washington University at their campus in Bellingham, Washington on Saturday, November 22, 2014.

Significant funding is being provided by the Western Washington University Department of Mathematics. Their support is gratefully acknowledged.

### Schedule

All talks will be held in the Biology Building, Room 234 (BI 234), with registration and breaks nearby. See the Getting There section for exact locations and directions.

The day's schedule is:

• 10:00 AM Registration, Bagels and Coffee
• 11:00 AM Jane Butterfield, Line-of-Sight Pursuit in Sweepable Polygons
• 12:00 PM Lunch @ The Soy House Restaurant
•   2:30 PM Steven Klee, Face Enumeration on Simplicial Complexes
•   3:30 PM Cookies, Coffee and Cokes
•   4:00 PM Richard Anstee, Forbidden Configurations
•   5:30 PM Happy Hour, Dinner @ The Copper Hog

### Line-of-Sight Pursuit in Sweepable Polygons

We examine a turn-based pursuit-evasion game in a simply connected polygonal environment. One pursuer chases one evader, each of whom takes turn moving in straight lines a distance of at most one. The pursuer wins if she is within unit distance of the evader; the evader wins by eluding capture forever. Although both players have complete information of the polygonal environment, the pursuer has only line-of-sight visibility of the evader. We provide a winning strategy for the pursuer in monotone polygons and sweepable polygons. Our algorithm uses a capture strategy that is new to the pursuit-evasion field, which we call the 'rook strategy'. This strategy is similar in spirit to the well-known 'lion strategy', which does not seem to be suitable for sweepable polygons.

### Face Enumeration on Simplicial Complexes

A simplicial complex is a combinatorial object that can be represented as a topological space. Just as a graph is made up of vertices and edges, a simplicial complex is made up of vertices, edges, triangles, tetrahedra, and higher-dimensional simplices. The most natural combinatorial statistics to collect on a simplicial complex are its face numbers, which count the number of vertices, edges, and higher-dimensional faces in the complex.

This talk will give a survey on face numbers of simplicial complexes, beginning with planar graphs and extending to spheres and manifolds of higher dimensions. We will undertake two main questions in this talk: First, what is the relationship between the face numbers of a simplicial complex and its topological invariants? Second, how can we infer extra combinatorial information from properties of the underlying graph of a simplicial complex, such as graph connectivity and graph colorability?

### Forbidden Configurations

I have been exploring a problem in extremal combinatorics for many years. I will highlight a few recent results. One (joint with Lincoln Lu) relates to Ramsey Theory and improves a bound of Balogh and Bollobás from a double exponential to a single exponential. Another (joint with Attila Sali) uses the remarkable recent Block Design results of Keevash. I will mention VC-dimension which has proved to have many applications. And always the three most important proof techniques are induction, induction, and induction.

Some precise definitions: We say a matrix $F$ is a configuration in $A$ , written $F\prec A$, if there is a submatrix of $A$ which is a row and column permutation of $F$. We say a matrix is simple if it is a $(0,1)$-matrix with no repeated columns (a simple matrix corresponds to a set system). Let ${\cal F}$ be a set of matrices. We write Avoid$(m,{\cal F})$ for the set of $m$-rowed simple matrices $A$ with $F\not\prec A$ for each $F\in{\cal F}$. Let $\|A\|$ denote the number of columns of $A$. Our extremal problem is to compute forb$(m,{\cal F})=\max\{\|A\|\,:\,A\in\text{Avoid}(m,{\cal F})\}$.

### Registration

The Combinatorial Potlatch has no permanent 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, and the sponsoring institutions provides facilities, food for the breaks and some support for speakers' travel. So expressions of appreciation to the speakers and the hosts are preferred and especially encouraged. Thanks.

### Getting There

All talks will be held in the Biology Building, Room 234 (BI 234), with registration and breaks nearby. The building is in the south-central portion of the map below, marked "BI" or use the pull-down "Building" menu. Parking will be free in lot 12A, at the south end of campus, just south of West College Way. (Baby blue area on map linked below).

Campus Map

### Lodging

We have rooms reserved at the Best Western Hotel on Lakeway.

1. Discounted rate: \$99/\$109 depending on room type.
2. Rooms are held until November 15.
3. Book with the hotel directly at 1-360-671-1011, 1-800-671-1011.

Nearby Hotels (from WWU, organized by price).

You might wish to avoid the hotels in the Devil's Triangle.

### Dining and Happy Hour

We have reservations for no-host lunch and dinner at two local restaurants. We hope you can join other participants, and your guests are welcome to join us also.

Lunch: The Soy House Restaurant, 400 W Holly St, 360.393.4857

Happy Hour, Dinner: The Copper Hog, 1327 N. State St, 360.927.7888

### 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
• Amites Sarkar, Western Washington University, amites.sarkar (a) wwu (dot) edu, Local Arrangements Chair
Last updated: November 18, 2014, http://buzzard.ups.edu/potlatch/2014/potlatch2014.html