University of British Columbia
Saturday, November 21, 2015
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 University of British Columbia at their campus in Vancouver, British Columbia on Saturday, November 21, 2015.
Significant funding is being provided by the Pacific Institute of Mathematics. Their support is gratefully acknowledged.
More info, including a history and links to previous Potlatches, is at The Combinatorial Potlatch Home Page.
Schedule
All talks will be held in the Earth Sciences Building, 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
- 10:45 AM Kilian Raschel,
A Human Proof of Gessel's Lattice Path Conjecture
- 12:30 PM Lunch @ Biercraft
- 2:30 PM Daniel Johnston,
On $k$-Ramsey Numbers of Graphs
- 3:00 PM Cory Palmer,
Turán-type Theorems for Berge-Hypergraphs
- 3:30 PM Cookies, Coffee and Cokes
- 4:00 PM Alexander Holroyd,
Finitely Dependent Coloring
- 5:30 PM Happy Hour, Dinner
Talks and Abstracts
Kilian Raschel, Université de Tours
A Human Proof of Gessel's Lattice Path Conjecture
Around 2000, Ira Gessel conjectured that the number of lattice walks in the quadrant $N^2$, starting and ending at the origin $(0,0)$ and consisting of East, West, North-East and South-West steps, had a simple hypergeometric form. In the following decade, this problem became one instance in the systematic study of walks with small steps confined to the quadrant.
A complete classification of these walks according to the nature of their generating function (algebraic, $D$-finite, non-$D$-finite) is now available, but Gessel's walks remain mysterious because they are the only among the 23 $D$-finite models that had not been given an elementary solution. Instead, Gessel's conjecture was first proved using computer algebra in 2008. A year later, the associated three-variate generating function was proved to be algebraic by a computer algebra tour de force. In this talk we will present the first human proof of Gessel's conjecture (using complex analysis). This is a joint work with Alin Bostan (Inria Saclay) and Irina Kurkova (University Paris 6).
Daniel Johnston, The University of Montana
On $k$-Ramsey Numbers of Graphs
In a red-blue coloring of a graph $G$, every edge of $G$ is colored red or blue. For two graphs $F$ and $H$ and an integer $k$ with $2 \leq k \leq R(F, H)$, where $R(F, H)$ is the Ramsey number of $F$ and $H$, the $k$-Ramsey number $R_{k}(F, H)$ of $F$ and $H$ is the smallest order of a balanced complete $k$-partite graph $G$ such that every red-blue coloring of $G$ results in a red $F$ or a blue $H$. When $F$ and $H$ are bipartite, $R_{k}(F, H)$ is known to exist for each such integer $k$. When $F$ and $H$ are not bipartite that is not the case. We look at some of these results.
Cory Palmer, The University of Montana
Turán-type Theorems for Berge-Hypergraphs
Let $H$ be a hypergraph and $G$ be a graph. We say that the hypergraph $H$ contains the graph $G$ if each hyperedge $h$ of $H$ can be mapped to two vertices in $h$ such that the resulting graph has $G$ as a subgraph. We say $H$ is $G$-free if it does not contain $G$. (When $H$ is a graph this is the ordinary notion that $H$ does not have $G$ as a subgraph).
We would like to determine the maximum possible size of the sum of the vertex degrees in an $G$-free hypergraph $H$ on $n$ vertices. (When $H$ is a graph this maximum is twice the extremal number of $G$). Győri and Lemons showed that for $3$-uniform hypergraphs, when $G$ is an even cycle this maximum has the same order as the extremal number of an even cycle in graphs. Surprisingly, for cycles of length $2k+1$ the parameter is the same order as for cycles of length $2k$ (this is significantly different from the extremal number of odd cycles in graphs).
We examine this question in a slightly more general setting and show that for any graph $G$, the maximum degree sum cannot behave too differently from the extremal number of $G$. We then focus on the particular case when $G$ is a complete bipartite graph to get an analogue of the Kővári–Sós–Turán theorem.
(Joint work with Dániel Gerbner)
Alexander Holroyd, Microsoft Research
Finitely Dependent Coloring
A central concept of probability and ergodic theory is mixing in its various forms. The strongest and simplest mixing condition is finite dependence, which states that variables at sufficiently well separated locations are independent. A 50-year old conundrum is to understand the relationship between finitely dependent processes and block factors (a block factor is a finite-range function of an independent family). The issue takes a very surprising new turn if we in addition impose a local constraint (such as proper coloring) on the process. In particular, this has led to the discovery of a beautiful yet mysterious stochastic process that seemingly has no right to exist.
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 Earth Sciences Building, with registration and breaks nearby.
Parking: The closest parkade is the West Parkade
(Location Number: 5671) at 2140 Lower Mall V6T 1Z4, and is on the left side of this interactive map (which has a menu if you hit the icon in the upper-left corner). Simon Fraser and UVic have reciprocal privileges if you have a full-time parking permit. More at the UBC Parking site. You may have in-and-out privileges since the system is pay-by-plate (\$8/day). On a Saturday morning there is a positive probability of a free spot being available along Marine Drive nearby, but read the signs carefully.
This annotated map could be very helpful. Marine Drive in black, parkade in bright green and conference site outlined in red.
Lodging
Some suggestions on accomodations:
- St. John's College: Prices vary by room type:
- Private single rooms: These are basic single rooms with private shower; no coffee maker, bar fridge or TV.
- Private queen rooms: private washroom with shower, telephone, television, coffee maker, bar fridge and data port (an Ethernet cable is required).
- West Coast Suites: A deluxe hotel-like suite on campus. Suites include a telephone, flat panel TV, fully equipped kitchen and coffee service. Internet is via a LAN/Ethernet and a cable is required or can be purchased from the front desk.
- Carey Centre: Various room options available from Single to Queen with or without TV. Breakfast is available at an additional fee.
- The Listel Hotel: (Off-Campus) Located Downtown on Robson Street, Museum One King features: Single or double occupancy; Complementary breakfast (one per room) at the Forage Restaurant; telephone and voice mail; Wifi internet access (included with our Facilities Fee); Coffee makers; Lobby Computer kiosk with printer, Internet access and Microsoft Office applications; Pay-per-view television; Morning newspaper (available upon request), access to the in-house gym; and a daily wine reception from 5-6pm. Please bear in mind commute times when arriving to UBC campus (\$2.75CAD for transit and 20-30 minute commute time). To book these rooms, please call 1-800-663-5491 or email reservations@thelistelhotel.com. Nightly Rate \$165CAD. You can also book online with the promo code: PIMS.
Dining and Happy Hour
You are encouraged to join other conference participants at the various meals and other events we are planning for the day.
Lunch will be at Biercraft Wesbrook at UBC where they will be expecting us at 12:30 PM or so. [Location]
There are a few possibilities for Happy Hour and Dinner.
- Mahony and Sons Public House UBC - on the east side of campus, north of the hospital. Extensive food and drinks menus, cocktails. Not inexpensive. [Location]
- Point Grill - close by, soups, salads, burgers, sandwiches, a few entrees, beer and wine. [Location]
- Or we might return to Biercraft where we had lunch. [Location]
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
- Jozsef Solymosi, University of British Columbia, solymosi (a) math (dot) ubc (dot) ca, Local Arrangements Chair