Combinatorial Potlatch 2015
University of British Columbia
Saturday, November 21, 2015

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.

### 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

### 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).

### 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.

### 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)

### 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.

### 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.

### 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
Last updated: November 7, 2015, http://buzzard.ups.edu/potlatch/2015/potlatch2015.html