My primary interests lie in effective algebra, computability theory, reverse mathematics, and mathematical logic. Effective algebra endeavors to understand results of algebra and combinatorics from a viewpoint of computability theory. My Ph.D. dissertation concerns the effective content of ordered fields. For more information on the types of questions I like to study, as well as my approach to research, check out my papers and talks below.
The following papers, though copyrighted, may be downloaded for personal and non-profit educational use.
Abstract: We use methods from computability theory to answer questions about infinite planar graphs. A graph is computable if there is an algorithm which decides whether given vertices are adjacent. Having a procedure for deciding the edge set might not help compute other properties or features of the graph, however. The goal of this paper is to investigate the extent to which features related to the planarity of a graph might or might not be computable. We propose three definitions for what it might mean for a computable graph to be computably planar and for each build a computable planar graph which fails to be computably planar. We also consider these definitions in the context of highly computable graphs, those for which there is an algorithm which computes the degree of a given vertex.
Abstract: The computable dimension of a structure counts the number of computable copies up to computable isomorphism. In this paper, we consider the possible computable dimensions for various classes of computable ordered fields. We show that computable ordered fields with finite transcendence degree are computably stable, and thus have computable dimension 1. We then build computable ordered fields of infinite transcendence degree which have infinite computable dimension, but also such fields which are computably categorical. Finally, we show that 1 is the only possible finite computable dimension for any computable archimedean field.
Abstract: We consider locally finite graphs with vertex set \(\mathbb{N}\). A graph \(G\) is computable if the edge set is computable and highly computable if the neighborhood function \(N_G\) (which given \(v\) outputs all of its adjacent vertices) is computable. Let \(\chi(G)\) be the chromatic number of \(G\) and \(\chi^c(G)\) be the computable chromatic number of \(G\). Bean showed there is a computable graph \(G\) with \(\chi(G) = 3\) and \(\chi^c(G) = \infty\), but if \(G\) is highly computable then \(\chi^c(G) \leq 2\chi(G)\).
In a computable graph the neighborhood function is \(\Delta^0_2\). In highly computable graphs it is computable. It is natural to ask what happens between these extremes.
A computable graph \(G\) is \(A\)-computable if \(N_G \leq_T A\). Gasarch and Lee showed that if \(A\) is c.e. and not computable then there exists an \(A\)-computable graph \(G\) such that \(\chi(G) = 2\) but \(\chi^c(G) = \infty\). Hence for \(A\) noncomputable and c.e., \(A\)-computable graphs behave more like computable graphs than highly computable graphs. We prove analogous results for Euler paths and domatic partitions. Gasarch and Lee left open what happens for other \(\Delta^0_2\) sets \(A\). We show that there exists an \(\emptyset <_T A <_T \emptyset'\) such that every \(A\)-computable graph \(G\) with \(\chi(G) < \infty\) has \(\chi^c(G) < \infty\). Finally, we classify all such \(A\).
Abstract: We investigate the apparent difficulty of finding domatic partitions in graphs using tools from computability theory. We consider nicely presented (i.e., computable) infinite regular graphs and show that even if the domatic number is known, there might not be any algorithm for producing a domatic partition of optimal size. However, smaller domatic partitions can be constructed. We consider various approaches to this question. Additionally, we establish similar results for total domatic partitions.
Abstract: Given a graph \(G\), we say that a subset \(D\) of the vertex set \(V\) is a dominating set if it is near all the vertices, in that every vertex outside of \(D\) is adjacent to a vertex in \(D\). A domatic \(k\)-partition of \(G\) is a partition of \(V\) into \(k\) dominating sets. In this paper, we will consider issues of computability related to domatic partitions of computable graphs. Our investigation will center on answering two types of questions for the case when \(k = 3\). First, if domatic 3-partitions exist in a computable graph, how complicated can they be? Second, a decision problem: given a graph, how difficult is it to decide whether it has a domatic 3-partition? We will completely classify this decision problem for highly computable graphs, locally finite computable graphs, and computable graphs in general. Specifically, we show the decision problems for these kinds of graphs to be \(\Pi^0_1\)-, \(\Pi^0_2\)-, and \(\Sigma^1_1\)-complete, respectively.
Abstract: To better understand some of the classic knights and knaves puzzles, we count them. Doing so reveals a surprising connection between puzzles and solutions, and highlights some beautiful combinatorial identities.
Abstract: We study what the existence of a classical embedding between computable structures implies about the existence of computable embeddings. In particular, we consider the effect of fixing and varying the computable presentations of the computable structures.
Abstract: The effective content of ordered fields is investigated using tools of computability theory and reverse mathematics. Computable ordered fields are constructed with various interesting computability theoretic properties. These include a computable ordered field for which the sums of squares are reducible to the halting problem, a computable ordered field with no computable set of multiplicatively archimedean class representatives, and a computable ordered field every transcendence basis of which is immune. The question of computable dimension for ordered fields is posed, and answered for archimedean fields, fields with finite transcendence degree, and some purely transcendental fields with infinite transcendence degree. Several results from the reverse mathematics of ordered rings and fields are extended.
A few other teaching talks are available here.