Research Interests

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.

Papers

The following papers, though copyrighted, may be downloaded for personal and non-profit educational use.

  • Computing Planarity in Computable Planar Graphs, with Taylor McMillan, Graphs and Combinatorics, 32:6 (2016) 2525-2539. The final publication is available at link.springer.com.

    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.

  • Computable Dimension for Ordered Fields Archive for Mathematical Logic, 55:3-4 (2016) 519--534. The final publication is available at link.springer.com.

    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.

  • A-Computable Graphs with Matthew Jura and Tyler Markkanen. Annals of Pure and Applied Logic 167:3 (2016) 235-246. Final publication available from Eslevier.

    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\).

  • Finding Domatic Partitions in Infinite Graphs with Matthew Jura and Tyler Markkanen. Electronic Journal of Combinatorics 22(3) (2015), #P3.39

    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.

  • Domatic Partitions of Computable Graphs with Matthew Jura and Tyler Markkanen. Archive for Mathematical Logic 53:1 (January 2014) 137-155. The final publication is available at link.springer.com.

    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.

  • Counting Knights and Knaves with Gerri Roberts. College Mathematics Journal 44:4 (September 2013) 300-306.

    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.

  • Embeddings of Computable Structures with Asher M. Kach and Reed Solomon. Notre Dame J. Formal Logic 51:1 (May 2010) 55-68.

    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.

  • Computability Theory, Reverse Mathematics and Ordered Fields Ph.D. thesis, UConn, 2009. Adviser: Reed Solomon.

    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.

Selected Talks

A few other teaching talks are available here.