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.
- Finding Domatic Partitions in Infinite Regular Graphs with Matthew Jura and Tyler Markkanen. Submitted for publication.
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.
- Computable Dimension for Ordered Fields Submitted for publication.
Abstract: We study computable dimension for various classes of computable ordered fields. We show that computable ordered fields with finite transcendence degree are computably stable. We then build computable ordered fields of infinite transcendence degree which have infinite computable dimension, but also such fields which are computably categorical. Archimedean fields are shown to have computable dimension either 1 or \(\omega\), regardless of transcendence degree.
- 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.
- Controling Domination in Infinite Graphs - Joint Mathematics Meeting in San Antonio, January 13, 2015.
- Finding Small Domatic Partitions in Graphs with Large Domatic Number - ASL North American Annual Meeting, May 20, 2014.
- The Complexity of Transcendence Bases in Computable Ordered Fields - Joint Mathematics Meeting in Baltimore, January 16, 2014.
- Non-Computability in Graphs - University of Wyoming Colloquium, October 24, 2013.
- How (Not) to Compute Domatic Partitions of Graphs - Rocky Mountain Section of the MAA meeting, April 14, 2012.
- Counting Liars and Truth-tellers - Joint Mathematics Meeting in Boston, January 7, 2012
- To Infinity and Beyond - 31st Annual Coastal Carolina University High School Math Contest, 2010
- Computable Dimension of Ordered Fields - Joint Mathematics Meeting in Washington D.C., January 8th, 2009.