Combinatorics, Algebra, & Topology Seminar
Fall 2022

Nov18

Jurgen KritschgauCarnegie Mellon UniversityTime: 12:00 PM

Nov09

Word complexity and combinatorics for subshiftsDarren CreutzUNSATime: 12:00 PM
View Abstract
Subshifts are closed, shiftinvariant sets of biinfinite 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).

Oct28

The Game of Cops and RobbersCarolyn ReinhartSwarthmore CollegeTime: 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.

Oct13

Michael TaitVillanova UniversityTime: 12:00 PM

Oct07

The card game SET, finite affine geometry, and combinatorial number theoryRob WonGeorge Washington UniversityTime: 12:00 PM
View Abstract
The game SET is a card game of patternrecognition. 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