2013/02/09 by Stephen Flood, Flood, Stephen
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Primary 03D80 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1302.2256
openalex publication_date 2013/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ACA0.