Topics In online structure theory

Abstract

Kalimullin, Melnikov and Ng initiated the systematic study of the online content of mathematics by forbidding the use of unbounded search in algorithms that are applied to infinite combinatorial and algebraic structures. Since then, their study has grown to what we now know as online structure theory, which will be the focus of this thesis. We will study the connections between the punctual dimension and punctual degrees of a punctual structure and prove a new sufficient condition for a punctual structure to have infinite punctual dimension; we then apply this result to show new connections between the punctual dimension and punctual degrees of a punctual structure. Furthermore, we will investigate the punctual degrees of linear orders in an attempt to find a complete classification for density. More precisely, we will prove that the punctual degrees of (Z. n, <), for n>1, are dense, and construct a discrete linear order with non-dense punctual degrees.