Minimal obstructions for normal spanning trees
Tom 241 / 2018
Streszczenie
Diestel and Leader have characterised connected graphs that admit a normal spanning tree via two classes of forbidden minors. One class is Halin’s -graphs: bipartite graphs with bipartition (A,B) such that | A | = \aleph _0, | B| = \aleph _1 and every vertex of B has infinite degree.
Our main result is that under Martin’s Axiom and the failure of the Continuum Hypothesis, the class of forbidden (\aleph _0,\aleph _1)-graphs in Diestel and Leader’s result can be replaced by one single instance of such a graph.
Under CH, however, the class of (\aleph _0,\aleph _1)-graphs contains minor-incomparable elements, namely graphs of binary type, and \mathcal {U}-indivisible graphs. Assuming CH, Diestel and Leader asked whether every (\aleph _0,\aleph _1)-graph has an (\aleph _0,\aleph _1)-minor that is either indivisible or of binary type, and whether any two \mathcal {U}-indivisible graphs are necessarily minors of each other. For both questions, we construct examples showing that the answer is in the negative.