Overview

Date: April 15, 2023
Place: Springfield College, Locklin Hall 232 (Campus map)

Schedule

10:30am	Coffee, Tea & Snacks
11am	Justin Miller (Dartmouth College)
12pm	Lunch in Cheney Dining Hall
1:30pm	Jenna Zomback (Williams College)
2pm	Teerawat Thewmorakot (University of Connecticut)
2:30pm	Matthew Jura (Manhattan College)

Speakers

Matthew Jura (Manhattan College)

Asymptotic Density and Equitable Colorings of Computable Graphs

An equitable k-coloring of a finite graph is one in which the number of vertices in any two color classes differs by no more than one. Equitable colorings have also been defined and studied in the context of Borel graphs. In this talk, we will give a definition of equitable k-coloring for countable graphs using asymptotic density. Then we will investigate some properties of equitable colorings of computable graphs, and discuss some results related to asymptotic density. This work is joint with Stephen Flood, Oscar Levin, and Tyler Markkanen.

Justin Miller (Dartmouth College)

Order, Disorder, and Adaptivity for Stochasticity

Consider a game show where an infinite number of coins are hidden under cups. The contestant’s goal is to demonstrate that the coin pattern was not obtained by random flips via selecting an infinite subsequence of coins which shows a bias towards heads or tails. Given a set A representing a coin pattern, is there a computable strategy which wins on A? Categorizing the different types of strategy and the sets which they succeed on gives us different notions of stochasticity. Historically, the focus has been on adaptive stochasticity notions like KL-stochasticity and MWC-stochasticity: strategies are allowed to use previous information in making decisions. We shall focus on non-adaptive strategies, and give a constructive proof that disorderly non-adaptive strategies outperform orderly non-adaptive strategies. We shall also use the techniques from this proof to shed some light on the relationship between orderly, adaptive strategies and disorderly, non-adaptive strategies.

Teerawat Thewmorakot (University of Connecticut)

Computable Categoricity of Polish Metric Spaces

In 2013, Melnikov proposed a way to adapt notions and methods of computable structure theory on countable algebras to Polish metric spaces. For example, some of these methods can be used to measure the complexity of classification problems for classes of Polish metric spaces, or to study computable categoricity of Polish metric spaces. In this talk, we will discuss some results on computable categoricity of Polish metric spaces.

Jenna Zomback (Williams College)

Ergodic Theorems Along Trees

In the classical pointwise ergodic theorem for a probability measure preserving (pmp) transformation T, one takes averages of a given integrable function over the intervals (x, Tx, T^2 x,…,T^n x) in front of the point x. We prove a “backward” ergodic theorem for a countable-to-one pmp T, where the averages are taken over subtrees of the graph of T that are rooted at x and lie behind x (in the direction of T^-1). Surprisingly, this theorem yields forward ergodic theorems for countable groups, in particular, one for pmp actions of free groups of finite rank, and can be extended to yield ergodic theorems for pmp actions of free semigroups as well. In each case, the averages are taken along subtrees of the standard Cayley graph rooted at the identity. This is joint work with Anush Tserunyan.

Travel Support

Limited funding is provided from the NSF to support participation by students and others to NERDS. If interested, please email Russell Miller.