Drawing Trees with Perfect Angular Resolution and Polynomial Area

We study methods for drawing trees with perfect angular resolution, i.e., with angles at each node $v$ equal to $2\pi /d(v)$ . We show:

1. Any unordered tree has a crossing-free straight-line drawing with perfect angular resolution and polynomial area.
2. There are ordered trees that require exponential area for any crossing-free straight-line drawing having perfect angular resolution.
3. Any ordered tree has a crossing-free Lombardi-style drawing (where each edge is represented by a circular arc) with perfect angular resolution and polynomial area.

Thus, our results explore what is achievable with straight-line drawings and what more is achievable with Lombardi-style drawings, with respect to drawings of trees with perfect angular resolution.     

Definability in substructure orderings, IV: Finite lattices

Let ${\mathcal{L}}$ be the ordered set of isomorphism types of finite lattices, where the ordering is by embeddability. We study first-order definability in this ordered set. Our main result is that for every finite lattice L, the set {?, ? ^opp} is definable, where ? and ? ^opp are the isomorphism types of L and its opposite (L turned upside down). We shall show that the only non-identity automorphism of ${\mathcal{L}}$ is the map ${\ell \mapsto \ell^{\rm opp}}$ .     

A Theory of Stationary Trees and the Balanced Baumgartner–Hajnal–Todorcevic Theorem for Trees

Building on early work by Stevo Todorcevic, we develop a theory of stationary subtrees of trees of successor-cardinal height. We define the diagonal union of subsets of a tree, as well as normal ideals on a tree, and we characterize arbitrary subsets of a non-special tree as being either stationary or non-stationary. We then use this theory to prove the following partition relation for trees: Main Theorem. Let \({\kappa}\) be any infinite regular cardinal, let ξ be any ordinal such that \({2^{|\xi|} < \kappa}\) , and let k be any natural number. Then $$non-(2^{<\kappa})-special\, tree \rightarrow (\kappa + \xi)^{2}_k.$$ This is a generalization to trees of the Balanced Baumgartner–Hajnal–Todorcevic Theorem, which we recover by applying the above to the cardinal \({(2^{< \kappa})^{+}}\) , the simplest example of a non- \({(2^{< \kappa})}\) -special tree. As a corollary, we obtain a general result for partially ordered sets: Theorem. Let \({\kappa}\) be any infinite regular cardinal, let ξ be any ordinal such that \({2^{|\xi|} < \kappa}\) , and let k be any natural number. Let P be a partially ordered set such that \({P \rightarrow (2^{< \kappa})^{1}_{2^{< \kappa}} }\) . Then $$P \rightarrow (\kappa + \xi)^{2}_{k}.$$      

Continuous Maps on Aronszajn Trees

Assuming $\diamondsuit$ : Whenever B is a totally imperfect set of real numbers, there is special Aronszajn tree with no continuous order preserving map into B.     

Laplacian Spectral Radius and Maximum Degree of Trees with Perfect Matchings

Let μ(T) and Δ(T) denote the Laplacian spectral radius and the maximum degree of a tree T, respectively. Denote by ${\mathcal{T}_{2m}}$ the set of trees with perfect matchings on 2m vertices. In this paper, we show that for any ${T_1, T_2\in\mathcal{T}_{2m}}$ , if Δ(T ₁) > Δ(T ₂) and ${\Delta(T_1)\geq \lceil\frac{m}{2}\rceil+2}$ , then μ(T ₁) > μ(T ₂). By using this result, the first 20th largest trees in ${\mathcal{T}_{2m}}$ according to their Laplacian spectral radius are ordered. We also characterize the tree which alone minimizes (resp., maximizes) the Laplacian spectral radius among all the trees in ${\mathcal{T}_{2m}}$ with an arbitrary fixed maximum degree c (resp., when ${c \geq \lceil\frac{m}{2}\rceil + 1}$ ).     

L-spaces and the P-ideal dichotomy

We extend a theorem of Todor?evi?: Under the assumption ( $ \mathcal{K} $ ) (see Definition 1.11), $$ \boxtimes \left\{ \begin{gathered} any regular space Z with countable tightness such that \hfill \\ Z^n is Lindel\ddot of for all n \in \omega has no L - subspace. \hfill \\ \end{gathered} \right. $$ We assume $ \mathfrak{p} $ > ω ₁ and a weak form of Abraham and Todor?evi?’s P-ideal dichotomy instead and get the same conclusion. Then we show that $ \mathfrak{p} $ > ω ₁ and the dichotomy principle for P-ideals that have at most ?₁ generators together with ? do not imply that every Aronszajn tree is special, and hence do not imply (ie1-4). So we really extended the mentioned theorem.     

Some relations on the ordering of trees by minimal energies between subclasses of trees

The energy of a graph is defined as the sum of the absolute values of all eigenvalues of the graph. A tree is said to be non-starlike if it has at least two vertices with degree more than 2. A caterpillar is a tree in which a removal of all pendent vertices makes a path. Let $\mathcal{T}_{n,d}$ , $\mathbb{T}_{n,p}$ be the set of all trees of order n with diameter d, p pendent vertices respectively. In this paper, we investigate the relations on the ordering of trees and non-starlike trees by minimal energies between $\mathcal{T}_{n,d}$ and $\mathbb{T}_{n,n-d+1}$ . We first show that the first two trees (non-starlike trees, resp.) with minimal energies in $\mathcal{T}_{n,d}$ and $\mathbb{T}_{n,n-d+1}$ are the same for 3≤d≤n?2 (3≤d≤n?3, resp.). Then we obtain that the trees with third-minimal energy in $\mathcal{T}_{n,d}$ and $\mathbb{T}_{n,n-d+1}$ are the same when n≥11, 3≤d≤n?2 and d≠8; and the tree with third-minimal energy in $\mathcal{T}_{n,8}$ is the caterpillar with third-minimal energy in $\mathbb{T}_{n,n-7}$ for n≥11.     

Fragility and indestructibility of the tree property

We prove various theorems about the preservation and destruction of the tree property at ω ₂. Working in a model of Mitchell [9] where the tree property holds at ω ₂, we prove that ω ₂ still has the tree property after ccc forcing of size ${\aleph_1}$ or adding an arbitrary number of Cohen reals. We show that there is a relatively mild forcing in this same model which destroys the tree property. Finally we prove from a supercompact cardinal that the tree property at ω ₂ can be indestructible under ω ₂-directed closed forcing.     

Definability in substructure orderings, III: Finite distributive lattices

Let ${{\mathcal D}}$ be the ordered set of isomorphism types of finite distributive lattices, where the ordering is by embeddability. We study first-order definability in this ordered set. We prove among other things that for every finite distributive lattice D, the set {d, d ^opp} is definable, where d and d ^opp are the isomorphism types of D and its opposite (D turned upside down). We prove that the only non-identity automorphism of ${{\mathcal D}}$ is the opposite map. Then we apply these results to investigate definability in the closely related lattice of universal classes of distributive lattices. We prove that this lattice has only one non-identity automorphism, the opposite map; that the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets of the lattice; and that for each element K of the two subsets, {K, K ^opp} is a definable subset of the lattice.     

Creature forcing and large continuum: the joy of halving

For ${f,g\in\omega^\omega}$ let ${c^\forall_{f,g}}$ be the minimal number of uniform g-splitting trees needed to cover the uniform f-splitting tree, i.e., for every branch ν of the f-tree, one of the g-trees contains ν. Let ${c^\exists_{f,g}}$ be the dual notion: For every branch ν, one of the g-trees guesses ν(m) infinitely often. We show that it is consistent that ${c^\exists_{f_\epsilon,g_\epsilon}{=}c^\forall_{f_\epsilon,g_\epsilon}{=}\kappa_\epsilon}$ for continuum many pairwise different cardinals ${\kappa_\epsilon}$ and suitable pairs ${(f_\epsilon,g_\epsilon)}$ . For the proof we introduce a new mixed-limit creature forcing construction.     

Rearrangements with supporting trees, isomorphisms and shift operators

We study rearrangement operators which admit a supporting tree. This condition implies that the associated rearrangement operator has a bounded vector valued extension to ${L^p_E}$ , where E is a UMD space. We prove the existence of a large subspace ${X_p\subset L^p}$ on which a bounded rearrangement operator acts as an isomorphism. For a class of special shift operators, we construct supporting trees explicitly by combinatorial means.     

Another proof of a result of Jech and Shelah

Shelah’s pcf theory describes a certain structure which must exist if ${\aleph _\omega }$ is strong limit and $2^{\aleph _\omega } > \aleph _{\omega 1} $ holds. Jech and Shelah proved the surprising result that this structure exists in ZFC. They first give a forcing extension in which the structure exists then argue that by some absoluteness results it must exist anyway. We reformulate the statement to the existence of a certain partially ordered set, and then we show by a straightforward, elementary (i.e., non-metamathematical) argument that such partially ordered sets exist.     

An extension of coherent sheaves defined outside holomorphically convex compact sets

We show that a coherent analytic sheaf ${\mathcal F}$ with prof ${{\mathcal F}\geq 2}$ defined outside a holomorphically convex compact set K in a 1-convex space X admits a coherent extension to the whole space X if, and only if, the canonical topology on ${H^1(X \setminus K,{\mathcal F})}$ is separated.     

Unramified forcing preserving the law of double negation

Shoenfield's unramified version of Cohen's forcing is defined in two stages: one which does not preserve double negation and the other which modifies the former so as to preserve double negation. Here we express the unramified forcing, which preserves double negation, in a single stage. Surprisingly enough, the corresponding definition of forcing for equality acquires a rather simple form. In [2] forcing ∥- is expressed in terms of strong forcing \( \Vdash * \) viap∥-Q iffp \( \Vdash * \) ¬ ¬Q for every formulaQ ofZF set theory and every elementp of a partially ordered set (P, ≦). In its turn,p \( \Vdash * \) Q is defined by the following five clauses: (1) $$p \Vdash * a \in biff(\exists c)(\exists q \geqq p)((c,q) \in b \wedge p \Vdash * a = c)$$ (2) $$\begin{gathered} p \Vdash * a \ne biff(\exists c)(\exists q \geqq p)(((c,q) \in a \wedge p \Vdash * c \notin b) \hfill \\ ((c,q) \in b \wedge p \Vdash * c \notin a)) \hfill \\ \end{gathered} $$ (3) $$p \Vdash * \neg Qiff(\forall q)(q \leqq p \to \neg (q \Vdash * Q))$$ (4) $$p \Vdash * (Q \vee S)iff(p \Vdash * Q) \vee (p \Vdash * S)$$ (5) $$p \Vdash * (\exists x)Q(x)iff(\exists b)(p \Vdash * Q(b))$$ .     

The stable trees are nested

We show that we can construct simultaneously all the stable trees as a nested family. More precisely, if $1 < \alpha < \alpha ^{\prime } \le 2$ we prove that hidden inside any $\alpha $ -stable tree we can find a version of an $\alpha ^{\prime }$ -stable tree rescaled by an independent Mittag-Leffler type distribution. This tree can be explicitly constructed by a pruning procedure of the underlying stable tree or by a modification of the fragmentation associated with it. Our proofs are based on a recursive construction due to Marchal which is proved to converge almost surely towards a stable tree.     

A variant of Mathias forcing that preserves {\mathsf{ACA}_0}

We present and analyze ${F_\sigma}$ -Mathias forcing, which is similar but tamer than Mathias forcing. In particular, we show that this forcing preserves certain weak subsystems of second-order arithmetic such as ${\mathsf{ACA}_0}$ and ${\mathsf{WKL}_0 + \mathsf{I}\Sigma^0_2}$ , whereas Mathias forcing does not. We also show that the needed reals for ${F_\sigma}$ -Mathias forcing (in the sense of Blass in Ann Pure Appl Logic 109(1–2):77–88, 2001) are just the computable reals, as opposed to the hyperarithmetic reals for Mathias forcing.     

The Lattice of Subvarieties of Semilattice Ordered Algebras

This paper is devoted to the semilattice ordered \(\mathcal{V}\) -algebras of the form (A, Ω, +?), where + is a join-semilattice operation and (A, Ω) is an algebra from some given variety \(\mathcal{V}\) . We characterize the free semilattice ordered algebras using the concept of extended power algebras. Next we apply the result to describe the lattice of subvarieties of the variety of semilattice ordered \(\mathcal{V}\) -algebras in relation to the lattice of subvarieties of the variety \(\mathcal{V}\) .     

Proof of an entropy conjecture for Bloch coherent spin states and its generalizations

Wehrl used Glauber coherent states to define a map from quantum density matrices to classical phase space densities and conjectured that for Glauber coherent states the mininimum classical entropy would occur for density matrices equal to projectors onto coherent states. This was proved by Lieb in 1978 who also extended the conjecture to Bloch SU(2) spin-coherent states for every angular momentum J. This conjecture is proved here. We also recall our 1991 extension of the Wehrl map to a quantum channel from J to ${K=J+\frac{1}{2}, J+1, ... ,}$ with ${K=\infty}$ corresponding to the Wehrl map to classical densities. These channels were later recognized as the optimal quantum cloning channels. For each J and ${J < K \leqslant \infty}$ we show that the minimal output entropy for the channels occurs for a J coherent state. We also show that coherent states both Glauber and Bloch minimize any concave functional, not just entropy.     

Domination by ergodic elements in ordered Banach algebras

We recall the definition and properties of an algebra cone in an ordered Banach algebra (OBA) and continue to develop spectral theory for the positive elements. An element $a$ of a Banach algebra is called ergodic if the sequence of sums $\sum _{k=0}^{n-1} \frac{a^k}{n}$ converges. If $a$ and $b$ are positive elements in an OBA such that $0\le a\le b$ and if $b$ is ergodic, an interesting problem is that of finding conditions under which $a$ is also ergodic. We will show that in a semisimple OBA that has certain natural properties, the condition we need is that the spectral radius of $b$ is a Riesz point (relative to some inessential ideal). We will also show that the results obtained for OBAs can be extended to the more general setting of commutatively ordered Banach algebras (COBAs) when adjustments corresponding to the COBA structure are made.     

Minimum degree of the difference of two polynomials over {\mathbb Q}, and weighted plane trees

A weighted bicolored plane tree (or just tree for short) is a bicolored plane tree whose edges are endowed with positive integral weights. The degree of a vertex is defined as the sum of the weights of the edges incident to this vertex. Using the theory of dessins d’enfants, which studies the action of the absolute Galois group on graphs embedded into Riemann surfaces, we show that a weighted plane tree is a graphical representation of a pair of coprime polynomials \(P,Q\in {\mathbb C}\,[x]\) such that: (a)  \(\deg P = \deg Q\) , and \(P\) and \(Q\) have the same leading coefficient; (b) the multiplicities of the roots of  \(P\) (respectively, of  \(Q\) ) are equal to the degrees of the black (respectively, white) vertices of the corresponding tree; (c) the degree of the difference \(P-Q\) attains the minimum which is possible for the given multiplicities of the roots of \(P\)  and  \(Q\) . Moreover, if a tree in question is uniquely determined by the set of its black and white vertex degrees (we call such trees unitrees), then the corresponding polynomials are defined over \({\mathbb Q}\) . The pairs of polynomials \(P,Q\) such that the degree of the difference \(P-Q\) attains the minimum, and especially those defined over \({\mathbb Q}\) , are related to some important questions of number theory. Dozens of papers, from 1965 (Birch et al. in Norske Vid Selsk Forh 38:65–69, 1965) to 2010 (Beukers and Stewart in J Number Theory 130:660–679, 2010), were dedicated to their study. The main result of this paper is a complete classification of the unitrees, which provides us with the most massive class of such pairs defined over  \({\mathbb Q}\) . We also study combinatorial invariants of the Galois action on trees, as well as on the corresponding polynomial pairs, which permit us to find yet more examples defined over  \({\mathbb Q}\) . In a subsequent paper, we compute the polynomials \(P,Q\) corresponding to all the unitrees.