A new obstruction for normal spanning trees. Issue 4 (6th May 2021)

• Record Type: Journal Article
• Authors: Pitz, Max
• Is Part Of: Bulletin of the London Mathematical Society. Volume 53:Issue 4(2021)
• Page Start: 1220
• Page End: 1227
• Publication Date: 2021-05-06
• Subjects: 05C83 -- 05C05 -- 05C63 (primary); Mathematics -- Periodicals; 510
• DOI: 10.1112/blms.12495
• Languages: English
• ISSNs: 0024-6093

Abstract

Abstract: In a paper from 2001 ( Journal of the LMS ), Diestel and Leader offered a proof that a connected graph has a normal spanning tree if and only if it has no minor obtained canonically from either an ( ℵ 0, ℵ 1 ) ‐regular bipartite graph or an order‐theoretic Aronszajn tree. In particular, this refuted an earlier conjecture of Halin's that only the first of these obstructions was needed to characterize the graphs with normal spanning trees. However, Diestel and Leader's proof contains a gap, and their proposed list of excluded minors is still not complete. In this paper, we construct a third type of obstruction: an ℵ 1 ‐sized graph without a normal spanning tree that contains neither of the two types described by Diestel and Leader as a minor. Further, we show that any list of forbidden minors characterising the graphs with normal spanning trees must contain graphs of arbitrarily large cardinality.