A packed Ramsey's theorem and computability theory
Stephen Flood
Abstract
Open-access reader
Stephen Flood
Abstract
Open-access reader
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, there is an infinite set that is "packed together" which is given "a small number" of colors by f. We analyze the strength of this theorem from the perspective of computability theory and reverse mathematics. We show that this theorem is close in computational strength to standard Ramsey's theorem by giving arithmetical upper and lower bounds for solutions to computable instances. In reverse mathematics, we show that that this packed Ramsey's theorem is equivalent to Ramsey's theorem for exponents not equal to 2. When n=2, we show that it implies Ramsey's theorem, and that it does not imply ACA_0.
A significance statement is not available in the OpenAlex record.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
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, there is an infinite set that is "packed together" which is given "a small number" of colors by f. We analyze the strength of this theorem from the perspective of computability theory and reverse mathematics. We show that this theorem is close in computational strength to standard Ramsey's theorem by giving arithmetical upper and lower bounds for solutions to computable instances. In reverse mathematics, we show that that this packed Ramsey's theorem is equivalent to Ramsey's theorem for exponents not equal to 2. When n=2, we show that it implies Ramsey's theorem, and that it does not imply ACA_0.
Key concepts: Ramsey theory, Ramsey's theorem, Mathematics, Computability, Arithmetic function, Discrete mathematics, Gap theorem, Combinatorics