Puzzles of Cardinality Levin, Oscar; Markkanen, Tyler
The College mathematics journal,
09/2021, Letnik:
52, Številka:
4
Journal Article
Recenzirano
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.
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-theoretic 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.
A-computable graphs Jura, Matthew; Levin, Oscar; Markkanen, Tyler
Annals of pure and applied logic,
March 2016, 2016-03-00, Letnik:
167, Številka:
3
Journal Article
Recenzirano
Odprti dostop
We consider locally finite graphs with vertex set N. A graph G is computable if the edge set is computable and highly computable if the neighborhood function NG (which given v outputs all of its ...adjacent vertices) is computable. Let χ(G) be the chromatic number of G and χc(G) be the computable chromatic number of G. Bean showed there is a computable graph G with χ(G)=3 and χc(G)=∞, but if G is highly computable then χc(G)≤2χ(G). In a computable graph the neighborhood function is Δ20. 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 NG≤TA. Gasarch and Lee showed that if A is c.e. and not computable then there exists an A-computable graph G such that χ(G)=2 but χc(G)=∞. 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 Δ20 sets A. We show that there exists an ∅<TA<T∅′ such that every A-computable graph G with χ(G)<∞ has χc(G)<∞. Finally, we classify all such A.
Finding Domatic Partitions in Infinite Graphs Jura, Matthew; Levin, Oscar; Markkanen, Tyler
The Electronic journal of combinatorics,
09/2015, Letnik:
22, Številka:
3
Journal Article
Recenzirano
Odprti dostop
We investigate the apparent difficulty of finding domatic partitions in graphs using tools from computability theory. We consider nicely presented (i.e., computable) infinite 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, we prove that smaller domatic partitions can be constructed if we restrict to regular graphs. Additionally, we establish similar results for total domatic partitions.
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
Π
1
0
-,
Π
2
0
-, and
Σ
1
1
-complete, respectively.
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.
In computable model theory, mathematical structures are studied on the basis of their computability or computational complexity. The degree spectrum DgSp(special characters omitted) of a countable ...structure special characters omitted is one way to measure the computability of the structure. Given various classes of countable structures, such as linear orders, groups, and graphs, we separate two classes special characters omitted and special characters omitted in the following way: we say that special characters omitted is distinguished from special characters omitted with respect to degree spectrum if there is an special characters omitted ∈ special characters omitted such that for all special characters omitted ∈ special characters omitted, DgSp(special characters omitted) ≠ DgSp(special characters omitted). In the dissertation, we will investigate this separation idea. We look at specific choices for special characters omitted and special characters omitted—for example, we show that linear orders are distinguished from finite-components graphs, equivalence structures, rank-1 torsion-free abelian groups, and daisy graphs with respect to degree spectrum. Out of these proofs, there comes a general pattern for the kinds of structures from which linear orders are distinguished with respect to degree spectrum. In the future, we may also replace linear orders with possibly more general kinds of structures.
PDF
