image/svg+xml Oscar Levin, Ph.D.

Research

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.

  • The computational strength of matchings in countable graphs, with Stephen Flood, Matthew Jura, and Tyler Markkanen, Annals of Pure and Applied Logic, 173(8) (August 2022). Final version available from Eslevier.

    Abstract: In a 1977 paper, Steffens identified an elegant criterion for determining when a countable graph has a perfect matching. In this paper, we will investigate the proof-theoretic strength of this result and related theorems. We show that a number of natural variants of these theorems are equivalent, or closely related, to the “big five” subsystems of reverse mathematics.

    The results of this paper explore the relationship between graph theory and logic by showing the way in which specific changes to a single graph-theoretic principle impact the corresponding proof-theoretical strength. Taken together, the results and questions of this paper suggest that the existence of matchings in countable graphs provides a rich context for understanding reverse mathematics more broadly.

  • Puzzles of cardinality, with Tyler Markkanen, College Mathematics Journal, 52:4 (September 2021). Final version available from the journal’s website.

    Abstract: We investigate a new sort of puzzle of self-reference, in which the puzzler is asked to find the cardinality of a set defined in terms of its own cardinality. We discover which sets are the unique solution to such puzzles and see how puzzles for such sets can be made arbitrarily complex. Then we compare our new cardinality puzzles to the classic puzzles of knights and knaves.

  • Prime labelings of infinite graphs, with Matthew Kenigsberg, Involve, a journal of mathematics, 12:4 (2019) 633-646. The final publication is available from the journal’s website.

    Abstract: A finite graph on $n$ vertices has a prime labeling provided there is a way to label the vertices with the integers 1 through $n$ such that every pair of adjacent vertices has relatively prime labels. In this paper, we extend the definition of prime labeling to infinite graphs and give a simple necessary and sufficient condition for an infinite graph to have a prime labeling. We then measure the complexity of prime labelings of infinite graphs using techniques from computability theory to verify that our condition is as simple as possible.

  • 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^02). 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 1) 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.

Search