Showing math.LOShow all
2 papers · 1 filter
math.LO2020
The computational strength of matchings in countable graphs
Stephen Flood, Matthew Jura, Oscar Levin +1
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 stre…
math.LO2013
A packed Ramsey's theorem and computability theory
Stephen Flood
Ramsey's theorem states that each coloring has an infinite homogeneous set, but these sets can be arbitrarily spread out. Paul Erdos and Fred Galvin proved that for each coloring f…