Inspired by Ramseys theorem for pairs, Rival and Sands proved what we refer to as an inside/outside Ramsey theorem: every infinite graph $G$ contains an infinite subset $H$ such that every vertex of $G$ is adjacent to precisely none, one, or infinitely many vertices of $H$. We analyze the Rival-Sands theorem from the perspective of reverse mathematics and the Weihrauch degrees. In reverse mathematics, we find that the Rival-Sands theorem is equivalent to arithmetical comprehension and hence is stronger than Ramseys theorem for pairs. We also identify a weak form of the Rival-Sands theorem that is equivalent to Ramseys theorem for pairs. We turn to the Weihrauch degrees to give a finer analysis of the Rival-Sands theorems computational strength. We find that the Rival-Sands theorem is Weihrauch equivalent to the double jump of weak K{o}nigs lemma. We believe that the Rival-Sands theorem is the first natural theorem shown to exhibit exactly this strength. Furthermore, by combining our result with a result of Brattka and Rakotoniaina, we obtain that solving one instance of the Rival-Sands theorem exactly corresponds to simultaneously solving countably many instances of Ramseys theorem for pairs. Finally, we show that the uniform computational strength of the weak Rival-Sands theorem is weaker than that of Ramseys theorem for pairs by showing that a number of well-known consequences of Ramseys theorem for pairs do not Weihrauch reduce to the weak Rival-Sands theorem. We also address an apparent gap in the literature concerning the relationship between Weihrauch degrees corresponding to the ascending/descending sequence principle and the infinite pigeonhole principle.
Download