% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.33}{23(2)}{2016} \usepackage{amsthm,amsmath,enumerate,amssymb} \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \def\COMMENT{} \def\NST{normal spanning tree} \def\TKA{$T K_{\aleph_0}$} \def\T{T} \def\dcl(#1){\lceil #1 \rceil} \def\ucl(#1){\lfloor #1 \rfloor} \def\sm{\smallsetminus} \def\H{I} \def\sube{\subseteq} \let\sub=\sube \def\subne{\subsetneqq} \def\supe{\supseteq} \def\wrt{with respect to} \def\looseproof#1{\bigbreak\noindent {{\bf #1.}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\bf A simple existence criterion for\\ normal spanning trees} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Reinhard Diestel\\ \small Mathematisches Seminar\\[-0.8ex] \small Hamburg University\\[-0.8ex] \small Germany} % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Apr 11, 2016}{Apr 29, 2016}{May 13, 2016}\\ \small Mathematics Subject Classifications: 05C, 05C05, 05C63, 05C75, 05C83} \begin{document} \maketitle \begin{abstract} \noindent Halin proved in 1978 that there exists a normal spanning tree in every connected graph $G$ that satisfies the following two conditions: (i)~$G$~contains no subdivision of a `fat'~$K_{\aleph_0}$, one in which every edge has been replaced by uncountably many parallel edges; and (ii)~$G$ has no $K_{\aleph_0}$ subgraph. We show that the second condition is unnecessary.\par % keywords are optional \bigskip\noindent \textbf{Keywords:} infinite graph, spanning tree, normal, forbidden topological minor \end{abstract} \section{Introduction} A spanning tree of an infinite graph is {\it normal\/} if the endvertices of any chord are comparable in the tree order defined by some arbitrarily chosen root. (In finite graphs, these are their `depth-first search' trees; see~\cite{DiestelBook10noEE} for precise definitions.) Normal spanning trees are perhaps the most important single structural tool for analysing an infinite graph~-- see~\cite{DiestelLeaderBGC} for a typical example, and the exercises in~\cite[Chapter~8]{DiestelBook10noEE} for many more~-- but they do not always exist. The question of which graphs have \NST s thus is an important question. All countable connected graphs have \NST s~\cite{DiestelBook10noEE}. But not all connected graphs do. For example, if $T$ is a \NST\ of~$G$ and $G$ is complete, then $T$ defines a chain on its vertex set. Hence $T$ must be a single path or ray, and $G$ is countable. For connected graphs of arbitrary order, there are three characterizations of the graphs that admit a \NST: \begin{theorem}\label{Characterizations} The following statements are equivalent for connected graphs~$G$. \begin{enumerate}[{\rm (i)}]\itemsep=0pt \item $G$ has a \NST{\/\rm;} \item $V(G)$ is a countable union of dispersed sets {\rm(}Jung~{\rm\cite{jung69,RDsBanffSurvey});} \item $|G|$ is metrizable~{\rm\cite{diestelESST};} \item $G$ contains neither an $(\aleph_0,\aleph_1)$-graph nor an Aronszajn-tree graph as a minor~{\rm\cite{DiestelLeaderNST}.} \end{enumerate} \end{theorem} \goodbreak \noindent Here, a set of vertices in $G$ is {\it dispersed\/} if every ray can be separated from it by some finite set of vertices. (The levels of a \NST\ are dispersed; see~\cite{DiestelBook10noEE}.) The dispersed vertex sets in a graph~$G$ are precisely those that are closed in the topological space~$|G|$ of~(iii), which consists of $G$ and its ends~\cite{diestelESST}. The space $|G|$ will not concern us in this note, so we refer to~\cite{diestelESST} for the definition of the topology on~$|G|$. But we shall use the equivalence of (i) and~(iv) in our proof, and the forbidden minors mentioned in~(iv) will be defined in Section~\ref{secProof}. Despite the variety in Theorem~\ref{Characterizations}, it can still be hard in practice to decide whether a given graph has a \NST.% \footnote{In particular, the two types of graph mentioned in~(iv) are not completely understood; see~\cite{DiestelLeaderNST} for the~-- quite intriguing~-- problem of how to properly understand (or meaningfully classify) the $(\aleph_0,\aleph_1)$-graphs.} In most applications, none of these characterizations is used, but a simpler sufficient condition due to Halin. This condition, however, is much stronger, and hence does not always hold even if a \NST\ exists. It is the purpose of this note to show that this condition can be considerably weakened. \section{The result}\label{secResults} Halin's~\cite{halin78} most-used sufficient condition for the existence of a \NST\ in a connected graph is that it does not contain a $\T K_{\aleph_0}$. This is usually easier to check than the conditions in Theorem~\ref{Characterizations}, but it is also quite a strong assumption. However, Halin~\cite{halin78} also proved that this assumption can be replaced by the conjunction of two independent much weaker assumptions: % \begin{itemize}\itemsep=0pt \item $G$ contains no {\it fat $\T K_{\aleph_0}$}: a subdivision of the multigraph obtained from a $K_{\aleph_0}$ by replacing every edge with $\aleph_1$ parallel edges; \item $G$ contains no $K_{\aleph_0}$ (as a subgraph). \end{itemize} We shall prove that the second condition is unnecessary: \begin{theorem}\label{Main} Every connected graph not containing a fat $\T K_{\aleph_0}$ has~a~\NST. \end{theorem} We remark that all the graphs we consider are simple, including our fat $\T K_{\aleph_0}$s. When we say, without specifying any graph relation, that a graph $G$ {\it contains\/} another graph~$H$, we mean that $H$ is isomorphic to a subgraph of~$G$. Any other undefined terms can be found in~\cite{DiestelBook10noEE}. \section{The proof}\label{secProof} Our proof of Theorem~\ref{Main} will be based on the equivalence (i)$\leftrightarrow$(iv) in Theorem~\ref{Characterizations}, so let us recall from~\cite{DiestelBook10noEE} the terms involved here. An {\it Aronszajn tree\/} is a poset $(T,\le)$ with the following properties:% \footnote{Unlike the perhaps better known Suslin trees~-- Aronszajn trees in which even every anti\-chain must be countable~-- Aronszajn trees can be shown to exist without any set-theoretic assumptions in addition to~ZFC.} \begin{itemize}\itemsep=0pt \item $T$ that has a least element, its {\it root\/}; \item the down-closure of every point in $T$ is well-ordered; \item $T$ is uncountable, but all chains and all levels in $T$ are countable. \end{itemize} % Here, the {\it down-closure\/} $\dcl(t)$ of a point $t\in T$ is the set $\{\,x\mid x\le t\,\}$; its {\it up-closure\/} is the set $\ucl(t) := \{\,y\mid t\le y\,\}$.\vadjust{\penalty-500} More generally, if $x x}$ has a neighbour $t'$ with $x\le t' < t$, by the second condition, and hence the interval contains for each of its elements~$t$ the vertices of a $t$--$x$ path in~$G$. Similarly, $G$~itself is connected, because every vertex can be linked to the unique root of~$T$.\looseness=-1 An {\it $(\aleph_0,\aleph_1)$-graph with bipartition $(A,B)$\/} is a bipartite graph with vertex classes $A$ of size~$\aleph_0$ and $B$ of size~$\aleph_1$ such that every vertex in $B$ has infinite degree. Replacing the vertices $x$ of a graph $X$ with disjoint connected graphs~$H_x$, and the edges $xy$ of $X$ with non-empty sets of $H_x$--$\,H_y$ edges, yields a graph that we shall call an~$\H X$ (for `inflated~$X$'). More formally, a graph {\it $H$ is an~$\H X$} if its vertex set admits a partition ${\{\,V_x\mid x\in V(X)\,\}}$ into connected subsets~$V_x$ such that distinct vertices $x,y\in X$ are adjacent in $X$ if and only if $H$ contains a $V_x$--$V_y$ edge. The sets $V_x$ are the {\it branch sets of the~$\H X$\/}. Thus, $X$~arises from $H$ by contracting the subgraphs~$H_x$, without deleting any vertices or edges (other than loops or parallel edges arising in the contraction). A~graph $X$ is a {\it minor\/} of a graph $G$ if $G$ contains an~$\H X$ as a subgraph. See~\cite{DiestelBook10noEE} for more details. For our proof of Theorem~\ref{Main} from Theorem~\ref{Characterizations}\ (i)$\leftrightarrow$(iv) it suffices to show the following: \begin{equation}\tag{\ensuremath{*}} \begin{minipage}[c]{0.8\textwidth}\em Every $\H X$, where $X$ is either an $(\aleph_0,\aleph_1)$-graph or an AT-graph, contains a fat $\T K_{\aleph_0}$ (as a subgraph). \end{minipage} \end{equation} \medskip\noindent The rest of this section is devoted to the proof of~$(*)$. \begin{lemma}\label{AAproperties} Let $X$ be an $(\aleph_0,\aleph_1)$-graph, with bipartition $(A,B)$ say. \begin{enumerate}[{\rm (i)}]\itemsep=0pt \item $X$ has an $(\aleph_0,\aleph_1)$-subgraph $X'$ with bipartition into $A'\sub A$ and ${B'\sub B}$ such that every vertex in $A'$ has uncountable degree in~$X'$. \item For every finite set $F\sub A$ and every uncountable set $U\sub B$, there exists a vertex $a\in A\sm F$ that has uncountably many neighbours in~$U$. \end{enumerate} \end{lemma} \goodbreak \begin{proof} (i) Delete from $X$ all the vertices in~$A$ that have only countable degree, together with their neighbours in~$B$. Since this removes only countably many vertices from~$B$, the remaining set~$B'\sub B$ is still uncountable.\vadjust{\penalty-2000} Every $b'\in B'$ has all its $X$-neighbours in the set $A'$ of the vertices in~$A$ that we did not delete, as otherwise $b'$ would have been deleted too. Thus, $b'$~still has infinite degree in the subgraph $X'$ of $X$ induced by $A'$ and~$B'$. In particular, $A'$~is still infinite, and $X'$ is the desired $(\aleph_0,\aleph_1)$-subgraph of~$X$. (ii) If there is no vertex $a\in A\sm F$ as claimed, then each vertex $a\in A\sm F$ has only countably many neighbours in~$U$. As $A\sm F$ is countable, this means that $U\sm N(A\sm F)\ne\emptyset$. But every vertex in this set has all its neighbours in~$F$, and thus has finite degree. This contradicts our assumption that $X$~is an $(\aleph_0,\aleph_1)$-graph. \end{proof} \begin{lemma}\label{AAfat} Let $X$ be an $(\aleph_0,\aleph_1)$-graph with bipartition $(A,B)$. Let $A'\sub A$ be infinite and such that for every two vertices $a,a'$ in $A'$ there is some uncountable set $B(a,a')$ of common neighbours of $a$ and~$a'$% \COMMENT{} in~$B$. Then $A'$ is the set of branch vertices of a fat~\TKA\ in $X$ whose subdivided edges all have the form $aba'$ with $b\in B(a,a')$. \end{lemma} \begin{proof} We have to find a total of $\aleph_0^2\cdot\aleph_1 = \aleph_1$ independent paths in $X$ between vertices in~$A'$. Let us enumerate these desired paths as $(P_\alpha)_{\alpha < \omega_1}$; it is then easy to find them recursively on~$\alpha$, keeping them independent. \COMMENT{} \end{proof} \begin{lemma}\label{IAAfat} Every $\H X$, where $X$ is an $(\aleph_0,\aleph_1)$-graph, contains a fat $\T K_{\aleph_0}$. \end{lemma} \begin{proof} Let $H$ be an $\H X$ for an $(\aleph_0,\aleph_1)$-graph $X$ with bipartition $(A,B)$, with branch sets $V_x$ for vertices $x\in X$. Replacing $X$ with an appropriate $(\aleph_0,\aleph_1)$-subgraph $Y$ (and $H$ with the corresponding~$\H Y\sub H$) if necessary, we may assume by Lemma~\ref{AAproperties} (i) that every vertex in~$A$ has uncountable degree in~$X$. We shall find our desired fat \TKA\ in~$H$ as follows. We construct, inductively, an infinite set $A' = \{a_0,a_1,\dots\}\sub A$ such that, for each $a_i\in A'$, there is an uncountable subdivided star $S(a_i)\sub H[V_{a_i}]$ whose leaves send edges of~$H$ to the branch sets of distinct vertices $b\in B$. The sets $B_i$ of these~$b$% \COMMENT{} will be nested as $B_0\supe B_1\supseteq\dots$. We shall then apply Lemma~\ref{AAfat} to find a fat \TKA\ in~$X$, and translate this to the desired fat \TKA\ in~$H$. Pick $a_0\in A$ arbitrarily. For each of the uncountably many neighbours $b$ of $a_0$ in $B$ we can find a vertex $v_b\in V_b$ that sends an edge of~$H$ to~$V_{a_0}$. For every~$b$, pick one neighbour $u_b$ of $v_b$ in~$V_{a_0}$. Consider a minimal connected subgraph $H_0$ of~$H[V_{a_0}]$ containing all these vertices~$u_b$, and add to it all the edges~$u_b v_b$ to obtain the\vadjust{\penalty-200} graph~$T = T(a_0)$. By the minimality of~$H_0$, \begin{equation}\tag{\ensuremath{1}} \begin{minipage}[c]{0.8\textwidth}\em $T$~is a tree in which every edge lies on a path between two vertices of the form~$v_b$. \end{minipage} \end{equation} Since there are uncountably many~$b$% \COMMENT{} and their $v_b$ are distinct, $T$~is uncountable and hence has a vertex $s_0$ of uncountable degree. For every edge $e$ of $T$ at~$s_0$ pick a path in $T$ from $s_0$ through $e$ to some~$v_b$; this is possible by~(1). Let $S(a_0)$ be the union of all these paths. Then $S(a_0)$ is an uncountable subdivided star with centre~$s_0$ all whose non-leaves lie in~$V_{a_0}$ and whose leaves lie in the branch sets $V_b$ of distinct vertices $b\in B$. Let $B_0\sub B$ be the (uncountable) set of these~$b$, and rename the vertices $v_b$ with $b\in B_0$ as~$v_b^0$. Assume now that, for some $n\ge 1$, we have picked distinct vertices $a_0,\dots,a_{n-1}$ from~$A$ and defined uncountable subsets $B_0\supe \dots\supe B_{n-1}$ of~$B$ so that each $a_i$ is adjacent in $X$ to every vertex in~$B_i$. By Lemma~\ref{AAproperties} (ii) there exists an $a_n\in A\sm \{a_0,\dots,a_{n-1}\}$ which, in~$X$, has uncountably many neighbours in~$B_{n-1}$. As before, we can find an uncountable subdivided star $S(a_n)$ in~$H$ whose centre $s_n$ and any other non-leaves lie in $V_{a_n}$ and whose leaves $v_b^n$ lie in the branch sets $V_b$ of (uncountably many) distinct vertices $b\in B_{n-1}$. We let $B_n$ be the set of those~$b$. Then $B_n$ is an uncountable subset of~$B_{n-1}$, and $a_n$~is adjacent in~$X$ to all the vertices in~$B_n$, as required for~$n$ by our recursion. By construction, every two vertices $a_i,a_j$ in $A' := \{a_0, a_1,\dots\}$ have uncountably many common neighbours in~$B$: those in $B_j$ if $i