-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathresearch.html
89 lines (64 loc) · 10.8 KB
/
research.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
---
layout: single
title: Research
header:
overlay_filter: rgba(22, 48, 94,.8)
overlay_image: /assets/images/atlanta2.png
permalink: /research/
author_profile: false
---
<h2>Research Interests</h2>
<p>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. </p>
<h2>Papers</h2>
<p>The following papers, though copyrighted, may be downloaded for personal and non-profit educational use.</p>
<ul class="no-dots">
<li><strong><a href="/papers/ComputablePlanarGraphs.pdf">Computing Planarity in Computable Planar Graphs</a></strong>, with Taylor McMillan, Graphs and Combinatorics, 32:6 (2016) 2525-2539. The final publication is available at <a href="http://link.springer.com/article/10.1007/s00373-016-1725-8" target="_blank">link.springer.com</a>.
<p><b>Abstract:</b> We use methods from computability theory to answer questions about infinite planar graphs. A graph is <i>computable</i> 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 <i>planarity</i> 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 <i>highly computable graphs</i>, those for which there is an algorithm which computes the degree of a given vertex. </p></li>
<li><strong><a href="/papers/OrderedFields-preprint.pdf">Computable Dimension for Ordered Fields</a></strong> Archive for Mathematical Logic, 55:3-4 (2016) 519--534. The final publication is available at <a href="http://link.springer.com/article/10.1007/s00153-016-0478-7" target="_blank">link.springer.com</a>.
<p><b>Abstract:</b> The computable dimension of a structure counts the number of computable copies up to <i>computable</i> 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.</p>
</li>
<li><strong><a href="/papers/AComputableGraphs.pdf">A-Computable Graphs</a></strong> with Matthew Jura and Tyler Markkanen. <i>Annals of Pure and Applied Logic</i> 167:3 (2016) 235-246. Final publication available <a href="http://dx.doi.org/10.1016/j.apal.2015.11.003" target="_blank">from Eslevier</a>.
<p><b>Abstract:</b> We consider locally finite graphs with vertex set \(\mathbb{N}\). A graph \(G\) is <i>computable</i> if the edge set is computable and <i>highly computable</i> 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)\).<br/>
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 <i>\(A\)-computable</i> 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\).</p>
</li>
<li><strong><a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/5089">Finding Domatic Partitions in Infinite Graphs</a></strong> with Matthew Jura and Tyler Markkanen. <i>Electronic Journal of Combinatorics</i> 22(3)
(2015), #P3.39
<p><b>Abstract:</b> 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.</p>
</li>
<li><strong><a href="/papers/DPCG_preprint.pdf">Domatic Partitions of Computable Graphs</a></strong> with Matthew Jura and Tyler Markkanen. <i>Archive for Mathematical Logic</i> 53:1 (January 2014) 137-155. The final publication is available at <a href="http://link.springer.com/article/10.1007%2Fs00153-013-0359-2" target="_blank">link.springer.com</a>.
<p><b>Abstract</b>: 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.</p>
</li>
<li><a href="/papers/CountingKnightsKnaves.pdf"><strong>Counting Knights and Knaves</strong></a> with Gerri Roberts. <i>College Mathematics Journal</i> 44:4 (September 2013) 300-306.
<p><b>Abstract:</b> 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.</p>
<li><a href="/papers/structures.pdf"><strong>Embeddings of Computable Structures</strong></a> with Asher M. Kach and Reed Solomon. <i>Notre Dame J. Formal Logic</i> 51:1 (May 2010) 55-68.
<p><b>Abstract:</b> 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.</p></li>
<li><a href="/papers/thesis.pdf"><strong>Computability Theory, Reverse Mathematics and Ordered Fields</strong></a> Ph.D. thesis, UConn, 2009. Adviser: Reed Solomon.
<p><b>Abstract:</b> 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.</p></li>
</ul>
<h2>Selected Talks</h2>
<ul class="no-dots">
<li><a href="/talks/2024rms/slides.html">OER textbooks with embedded
interactive assessments</a> - Rocky Mountain Section meeting, April 19, 2024.</li>
<li><a href="/talks/mathfest2018.pdf">Knights and Knaves and Naive Sets</a> - MathFest in Denver, August 4, 2018.</li>
<li><a href="/talks/maa-rms2017.pdf">A Paradox of Finite Cardinality</a> - Rocky Mountain Section of the MAA meeting, April 22, 2017.</li>
<li><a href="/talks/jmm2017talk.pdf">Graph Labelings and Computability Theory</a> - Joint Mathematics Meeting in Atlanta, January 7, 2017</li>
<li><a href="/talks/jmm2016talk.pdf">Graphs between Computable and Highly Computable</a> - Joint Mathematics Meeting in Seattle, January 8, 2016</li>
<li><a href="/talks/jmm2015talk.pdf">Controling Domination in Infinite Graphs</a> - Joint Mathematics Meeting in San Antonio, January 13, 2015.</li>
<li><a href="/talks/asl2014talk.pdf">Finding Small Domatic Partitions in Graphs with Large Domatic Number</a> - ASL North American Annual Meeting, May 20, 2014.</li>
<li><a href="/talks/jmm2014talk.pdf">The Complexity of Transcendence Bases in Computable Ordered Fields</a> - Joint Mathematics Meeting in Baltimore, January 16, 2014.</li>
<li><a href="/talks/UW2013talk.pdf">Non-Computability in Graphs</a> - University of Wyoming Colloquium, October 24, 2013.
<li><a href="/talks/maa-rms2012talk.pdf">How (Not) to Compute Domatic Partitions of Graphs</a> - Rocky Mountain Section of the MAA meeting, April 14, 2012.</li>
<li><a href="/talks/jmm2012talk.pdf">Counting Liars and Truth-tellers</a> - Joint Mathematics Meeting in Boston, January 7, 2012</li>
<li><a href="/talks/ccumc2010talk.pdf">To Infinity and Beyond</a> - 31st Annual Coastal Carolina University High School Math Contest, 2010</li>
<li><a href="/talks/jmm2009talk.pdf">Computable Dimension of Ordered Fields</a> - Joint Mathematics Meeting in Washington D.C., January 8th, 2009.</li>
</ul>
<p>A few other teaching talks are available <a href="http://discretetext.oscarlevin.com/talks.php">here</a>.</p>