Combinatorics, Algebra, & Topology Seminar

Fall 2022

• Nov

  18
• Jurgen Kritschgau

  Carnegie Mellon University

  Time: 12:00 PM

• Nov

  09
• Word complexity and combinatorics for subshifts

  Darren Creutz

  UNSA

  Time: 12:00 PM

  View Abstract

  Subshifts are closed, shift-invariant sets of bi-infinite sequences taking values in some finite set, the 'alphabet'. Associated to any subshift is a sequence of graphs G_q whose vertices are 'words'--finite strings of 'letters' appearing in the subshift--of length q. Using these Rauzy graphs and combinatorial properties of words, I recently proved that subshifts with word complexity p(q) = |{ words of length q }| such that \liminf p(q)/q < \infty exhibit a great deal of structure. I will discuss this and related results on low complexity subshifts; the talk will assume minimal background (basic graph theory and topology).

• Oct

  28
• The Game of Cops and Robbers

  Carolyn Reinhart

  Swarthmore College

  Time: 12:00 PM

  View Abstract

  Cops and Robbers is a graph game where some number of cops and robbers take turns moving along the edges of a graph. In the traditional game, the cops wish to capture a single robber as quickly as possible and the robber wishes to evade capture for as long as possible. Many variants of the game exist and some of the questions we can ask include: How many cops are needed to guarantee capture of the robber on a certain graph? How long will it take the cops to capture the robber? Can we be more efficient by using more than the minimum number of cops and capturing the robber more quickly? What if rather than capturing the robber, the cops want to prevent them from damaging vertices? In this talk, we will explore these questions and more.

• Oct

  13
• Michael Tait

  Villanova University

  Time: 12:00 PM

  Abstract

• Oct

  07
• The card game SET, finite affine geometry, and combinatorial number theory

  Rob Won

  George Washington University

  Time: 12:00 PM

  View Abstract

  The game SET is a card game of pattern-recognition. To play the game, twelve cards are dealt face up and all players look for SETs, which are collections of three cards satisfying a certain property. When a SET is found, it is removed and three new cards are dealt. The player who finds the most SETs is the winner. When playing the game, a natural question arises: does every collection of twelve cards contain at least one SET? Or, perhaps more precisely: how many cards are needed to guarantee the presence of a SET? This question is related to a problem that Terence Tao, in a blogpost from 2007, described as "perhaps [his] favourite open question." In this talk, we explore the connections between SET, finite affine geometry, and combinatorial number theory. We discuss recent breakthrough work of Ellenberg and Gijswijt which answers Tao's question. Finally, we introduce a generalization of this question and present some recent results