Times: 2026 Mar 28 from 10:45AM to 12:00PM (Central Time (US & Canada))
Abstract:
The Kneser graphs KG(n,k) are a classically studied family of graphs, wherein vertices are subsets of size k from a set of n elements, and vertices are connected if the sets they correspond to are disjoint. The chip-firing game is a combinatorial game played with poker chips relevant to various fields of mathematics and physics (see the dollar game, probabilistic abacus, Abelian sandpile model). Gonality is the graph invariant corresponding to the minimum number of chips needed to win the chip-firing game after one chip has been removed from one of the vertices of the graph. Gonality has applications in various mathematical fields, from combinatorics to algebraic geometry and coding theory, relating most notably to finding solutions to equations defining algebraic curves. Various techniques for upper and lower bounding gonality exist; using one such technique, we give (n-1) choose k as an upper bound for the gonality of KG(n,k) when n > 2k. We also apply the recent result that the invariant scramble number is a lower bound for gonality to show that the gonality of KG(n,k) is exactly (n-1) choose k when n is greater than (3k 2 + k + 2)/2, and improvement on existing results towards the conjectured n > 4k. Finally, we conjecture that an even stricter polynomial bound may hold by considering a specific scramble.