On degrees of vertices in paradoxical trees (Q1970576)

The paper gives necessary and sufficient conditions for an infinite tree to be paradoxical. A tree \(T=(V,E)\) is paradoxical if it admits a partition \(V = V_1 \cup V_2\) such that \(V\), \(V_1\) and \(V_2\) are pairwise equivalent (two sets \(A, B\) are equivalent if there is a bijection \(f : A \to B\)). More precisely, the paper gives inequalities involving the total degree of subgraphs induced by the bounded neighborhoods of any finite subset \(M\), i.e. the sets of nodes at distance at most \(d\) from \(M\). The first set of conditions (Theorem 1) indicates that this sum should be somewhat bigger than the total degree of nodes in \(M\) for the tree to be paradoxical (`somewhat' meaning that we alter the sums by subtracting the total number of nodes in the neightborhood under consideration). The second set of conditions (Theorem 2) expresses the importance of nodes of degree 2 in the tree, and states similar inequalities obtained by restricting the previous sums to nodes of degree 2. The paper builds on previous results by \textit{W. A. Deuber, M. Simonovits} and \textit{V. T. Sós} [Stud. Sci. Math. Hung. 30, No. 1-2, 17-23 (1995; Zbl 0857.54030)] adding to the characterization of paradoxical trees already given in \textit{D. Fon-Der-Flaass} [On exponential trees, Eur. J. Comb. 19, No. 1, 25-27 (1998; Zbl 0897.05023)]. It contains a list of technical lemmas dealing with various inequalities on degree, number of edges and cardinality of locally finite trees, thus providing potentially useful tools for the theory.