We prove several quantitative Ramseyan results involving ternary complete trees with {0,1}-labeled edges where we attempt to find a complete binary subtree with as few labels as possible along its paths. One of these is used to answer a question of Simpson’s in computability theory; we show that there is a bounded Π10 class of positive measure which is not strongly (Medvedev) reducible to DNR3; in fact, the class of 1-random reals is not strongly reducible to DNR3.
['Rodney G. Downey', 'Noam Greenberg', 'Carl G. Jockusch', 'Kevin G. Milans']
Binary subtrees with few labeled paths