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 $(\aleph _0,\aleph _1)$-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.
