PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

Minimal obstructions for normal spanning trees

Volume 241 / 2018

Nathan Bowler, Stefan Geschke, Max Pitz Fundamenta Mathematicae 241 (2018), 245-263 MSC: Primary 05C63, 05C75; Secondary 03E05, 03E50. DOI: 10.4064/fm337-10-2017 Published online: 16 February 2018

Abstract

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.

Authors

  • Nathan BowlerDepartment of Mathematics
    University of Hamburg
    Bundesstraße 55
    20146 Hamburg, Germany
    e-mail
  • Stefan GeschkeDepartment of Mathematics
    University of Hamburg
    Bundesstraße 55
    20146 Hamburg, Germany
    e-mail
  • Max PitzDepartment of Mathematics
    University of Hamburg
    Bundesstraße 55
    20146 Hamburg, Germany
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image