Overview

Date: April 24, 2022
Place: University of Connecticut (in person)

Schedule

10am	Social time	MONT 201 (2nd floor lounge)
10:30am	The Lovász Local Lemma and Hindman’s Theorem Reed Solomon (University of Connecticut)	MONT 214
11:30am	Computing Non-Repetitive Sequences Using the Lovász Local Lemma Daniel Mourad (University of Connecticut)	MONT 214
12pm	Lunch
1:30pm	Cantor-Bendixson Rank of Space of Orders Waseet Kazmi (University of Connecticut)	MONT 214
2pm	Non-Uniform omega-REA Sets Peter Gerdes	MONT 214
2:30pm	Perfect Matchings in Graphs and Reverse Mathematics Tyler Markkanen (Springfield College)	MONT 214

Abstracts

Reed Solomon

The Lovász Local Lemma and Hindman’s Theorem

The Lovász Local Lemma is a probabilistic tool in combinatorics. Typically, it is used to show the existence of finite objects, although when combined with compactness, it can be used to build infinite sets. I will give an introduction to the local lemma, illustrate it with some classical examples, and give one application to a variation of Hindman’s Theorem. This application is joint work with Csima, Dzhafarov, Hirschfeldt, Jockusch and Westrick.

Daniel Mourad

Computing Non-Repetitive Sequences Using the Lovász Local Lemma

We discuss effective versions of classical results on the existence of non-repetitive sequences first proven using the Lovász Local Lemma, a non-constructive existence result from the probabilistic method. We outline the path to these constructions. First, a probabilistic resample algorithm converges to a witness to the Local Lemma in polynomial expected time. Then, the bound on the expectation is used to build a deterministic algorithm with computable convergence time. However, the resulting effective computation has constraints that make it unsuitable for constructing non-repetitive sequences. We modify the resample algorithm and show that these modifications allow us to relax these constraints.

Waseet Kazmi

Cantor-Bendixson Rank of Space of Orders

For a computable orderable group, it is a well known fact that its space of orders forms a $\Pi^0_1$ class. It is still an open question whether the converse of this is true, that is, what $\Pi^0_1$ classes can be realized as the space of orders of some computable orderable group? We present a result that gives some progress towards trying to answer this larger open question. We show the existence of orderable groups such that their space of orders has arbitrary finite Cantor-Bendixson rank.

Peter Gerdes

Non-Uniform omega-REA Sets

A well known result about \( \omega \)-REA sets tells us that if \( A \) is an \( \omega \)-REA set and \( A^{[< n]} \leq_{T} X \) for all \( n \) (i.e., every component of \( A \) is computable from \( X \) ) then \( A \leq_{T} X'' \). This bound is known to be sharp but it raises another natural hypothesis. If an \( \omega \)-REA set \( A \) computes an arithmetic (or \( n \)-REA ) set \(X\) does it follow that \( {A^{[< n]}}'' \geq_{T} X \) for some \( n \)? In this talk, I demonstrate this claim fails in the most complete way possible and present an interesting iterated use of jump-inversion in the \( n \)-REA sets inspired by the construction of an arithmetically low \( \omega \)-REA set.

Tyler Markkanen

Perfect Matchings in Graphs and Reverse Mathematics

A matching of a graph is any set of edges in which no two edges share a vertex. Steffens gave a necessary and sufficient condition for a countable graph to have a perfect matching (i.e., a matching that covers all the vertices of the graph). In this talk, we will analyze the proof-theoretic strength of Steffens’ theorem from the viewpoint of reverse math. When restricting to certain classes of graphs (e.g., graphs with bounded degree and locally finite graphs), weaker versions of the theorem fall at the level of $ACA_0$ or below. Using methods of Aharoni, Magidor, and Shore, we give a computability-theoretic result with the potential of reversing Steffens’ full theorem to $ATR_0$. Joint with Stephen Flood, Matthew Jura, and Oscar Levin.

Travel Support

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