Speaker: 

Dylan King

Institution: 

Caltech

Time: 

Wednesday, May 29, 2024 - 2:00pm to 3:00pm

Host: 

Location: 

510R Rowland Hall

The Ramsey number of graphs G1 and G2, the smallest N so that any red/blue coloring of the N-clique contains either a red G1 or a blue G2, is one of the most studied notions in combinatorics. We study a related process called the online ordered Ramsey game, played between two players, Builder and Painter. Builder has two graphs, G1 and G2, each of which has a specific ordering on its vertices. Builder starts with an edgeless graph on an ordered vertex set (the integers) and attempts to build either an ordered red copy of G1 or an ordered blue copy of G2 by adding one edge at a time. When Builder adds an edge, Painter is required to decide, at the time of creation, whether an edge is red or blue. Ramsey’s Theorem tells us that Builder can eventually win; their objective is to do so using the minimum number of turns, and Painter’s objective is to delay them as long as possible. The *online ordered Ramsey number* of G1 and G2 is the number of turns taken when both players play optimally.

Online ordered Ramsey numbers were introduced by Perez-Gimenez, P. Pralat, and West in 2021. In this talk we will discuss their relation to other types of Ramsey numbers and present some results on the case when at least one of G1,G2 is sparse.

(Joint work with Emily Heath, Grace McCourt, Hannah Sheats, and Justin Wisby)