A new obstruction for normal spanning trees

DOI10.1112/BLMS.12495MaRDI QIDQ5153933zbMATH OpenOpenAlexFDO

Authors Max F. Pitz

Publication date 1 October 2021

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2005.04150

zbMATH Keywords

forbidden minorsHalin's conjectureinfinite graphsnormal spanning trees

Mathematics Subject Classification ID

Trees (05C05) Infinite graphs (05C63) Graph minors (05C83)

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 does not contain a minor from two specific forbidden classes of graphs, all of cardinality $alep{h}_1$. Unfortunately, their proof contains a gap, and their result is incorrect. In this paper, we construct a third type of obstruction: an $alep{h}_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.

Recommendations

• Normal Spanning Trees, Aronszajn Trees and Excluded Minors
• Proof of Halin's normal spanning tree conjecture
• Normal Tree Orders for Infinite Graphs
• A simple existence criterion for normal spanning trees
• The structure of \(TK_ a\)-free graphs
• Quickly proving Diestel's normal spanning tree criterion
• A unified existence theorem for normal spanning trees
• Classes of locally finite ubiquitous graphs
• Excluding Infinite Trees
• Minimal obstructions for normal spanning trees

Cites work

• A unified existence theorem for normal spanning trees
• scientific article; zbMATH DE number 1533074 (Why is no real title available?)
• Minimal obstructions for normal spanning trees
• Normal Spanning Trees, Aronszajn Trees and Excluded Minors
• Normal Tree Orders for Infinite Graphs
• Notes on singular cardinal combinatorics
• On σ-Discreteness and Borel Isomorphism
• Proof of Halin's normal spanning tree conjecture
• Set theory.
• Wurzelbäume und unendliche Wege in Graphen

Cited in

(12)

• Proof of Halin's normal spanning tree conjecture
• A unified existence theorem for normal spanning trees
• A simple existence criterion for normal spanning trees
• Normal Spanning Trees, Aronszajn Trees and Excluded Minors
• Normal Tree Orders for Infinite Graphs
• Minimal obstructions for normal spanning trees
• A note on minor antichains of uncountable graphs
• Duality theorems for stars and combs III: Undominated combs
• Duality theorems for stars and combs I: Arbitrary stars and combs
• End‐faithful spanning trees in graphs without normal spanning trees
• A representation theorem for end spaces of infinite graphs
• Quickly proving Diestel's normal spanning tree criterion

This page was built for publication: A new obstruction for normal spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5153933)