Weak square sequences and special Aronszajn trees

John Krueger

Displaying similar documents to “Weak square sequences and special Aronszajn trees”

Proper translation

Heike Mildenberger, Saharon Shelah (2011)

Fundamenta Mathematicae

Similarity:

We continue our work on weak diamonds [J. Appl. Anal. 15 (1009)]. We show that $2^{ω} = ℵ ₂$ together with the weak diamond for covering by thin trees, the weak diamond for covering by meagre sets, the weak diamond for covering by null sets, and “all Aronszajn trees are special” is consistent relative to ZFC. We iterate alternately forcings specialising Aronszajn trees without adding reals (the NNR forcing from [“Proper and Improper Forcing”, Ch. V]) and < ω₁-proper $^{ω} ω$ -bounding forcings adding...

Tree pattern matching from regular tree expressions

Ahlem Belabbaci, Hadda Cherroun, Loek Cleophas, Djelloul Ziadi (2018)

Kybernetika

Similarity:

In this work we deal with tree pattern matching over ranked trees, where the pattern set to be matched against is defined by a regular tree expression. We present a new method that uses a tree automaton constructed inductively from a regular tree expression. First we construct a special tree automaton for the regular tree expression of the pattern $E$ , which is somehow a generalization of Thompson automaton for strings. Then we run the constructed automaton on the subject tree $t$ . The pattern...

Closure for spanning trees and distant area

Jun Fujisawa, Akira Saito, Ingo Schiermeyer (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with $d e g_{G} u + d e g_{G} v \geq n - 1$ , G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on $d e g_{G} u + d e g_{G} v$ and the structure of the distant area for u and v. We prove...

Weak Type Inequality for the Square Function of a Nonnegative Submartingale

Adam Osękowski (2009)

Bulletin of the Polish Academy of Sciences. Mathematics

Similarity:

Let f be a nonnegative submartingale and S(f) denote its square function. We show that for any λ > 0, $λ ℙ (S (f) \geq λ) \leq π / 2 ∥ f ∥ ₁$ , and the constant π/2 is the best possible. The inequality is strict provided ∥f∥₁ ≠ 0.

Pressing Down Lemma for $λ$ -trees and its applications

Hui Li, Liang-Xue Peng (2013)

Czechoslovak Mathematical Journal

Similarity:

For any ordinal $λ$ of uncountable cofinality, a $λ$ -tree is a tree $T$ of height $λ$ such that $| T_{α} | < cf (λ)$ for each $α < λ$ , where $T_{α} = {x \in T : ht (x) = α}$ . In this note we get a Pressing Down Lemma for $λ$ -trees and discuss some of its applications. We show that if $η$ is an uncountable ordinal and $T$ is a Hausdorff tree of height $η$ such that $| T_{α} | \leq ω$ for each $α < η$ , then the tree $T$ is collectionwise Hausdorff if and only if for each antichain $C \subset T$ and for each limit ordinal $α \leq η$ with $cf (α) > ω$ , ${ht (c) : c \in C} \cap α$ is not stationary in $α$ . In the last part of this note, we investigate...

On sequences of ±1's defined by binary patterns

David W. Boyd, Janice Cook, Patrick Morton

Similarity:

CONTENTS1. Introduction..............................................................52. The matrix recursion................................................83. The characteristic polynomial of A.........................124. The autocorrelation tree........................................155. The roots of the period polynomials.......................196. A recurrence relation for $s_{p} (x)$ ..........................257. An explicit formula..................................................308....

A Weak-Type Inequality for Orthogonal Submartingales and Subharmonic Functions

Adam Osękowski (2011)

Bulletin of the Polish Academy of Sciences. Mathematics

Similarity:

Let X be a submartingale starting from 0, and Y be a semimartingale which is orthogonal and strongly differentially subordinate to X. The paper contains the proof of the sharp estimate $ℙ (s u p_{t \geq 0} | Y_{t} | \geq 1) \leq 3.375 . . . ∥ X ∥ ₁$ . As an application, a related weak-type inequality for smooth functions on Euclidean domains is established.

Pruning Galton–Watson trees and tree-valued Markov processes

Romain Abraham, Jean-François Delmas, Hui He (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We present a new pruning procedure on discrete trees by adding marks on the nodes of trees. This procedure allows us to construct and study a tree-valued Markov process ${𝒢 (u)}$ by pruning Galton–Watson trees and an analogous process ${𝒢^{*} (u)}$ by pruning a critical or subcritical Galton–Watson tree conditioned to be infinite. Under a mild condition on offspring distributions, we show that the process ${𝒢 (u)}$ run until its ascension time has a representation in terms of ${𝒢^{*} (u)}$ . A similar result was obtained by...

A note on the cubical dimension of new classes of binary trees

Kamal Kabyl, Abdelhafid Berrachedi, Éric Sopena (2015)

Czechoslovak Mathematical Journal

Similarity:

The cubical dimension of a graph $G$ is the smallest dimension of a hypercube into which $G$ is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with $2^{n}$ vertices, $n \geq 1$ , is $n$ . The 2-rooted complete binary tree of depth $n$ is obtained from two copies of the complete binary tree of depth $n$ by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice...

Weak dimensions and Gorenstein weak dimensions of group rings

Yueming Xiang (2021)

Czechoslovak Mathematical Journal

Similarity:

Let $K$ be a field, and let $G$ be a group. In the present paper, we investigate when the group ring $K [G]$ has finite weak dimension and finite Gorenstein weak dimension. We give some analogous versions of Serre’s theorem for the weak dimension and the Gorenstein weak dimension.

On the (2,2)-domination number of trees

You Lu, Xinmin Hou, Jun-Ming Xu (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let γ(G) and $γ_{2, 2} (G)$ denote the domination number and (2,2)-domination number of a graph G, respectively. In this paper, for any nontrivial tree T, we show that $(2 (γ (T) + 1)) / 3 \leq γ_{2, 2} (T) \leq 2 γ (T)$ . Moreover, we characterize all the trees achieving the equalities.

A partition of the Catalan numbers and enumeration of genealogical trees

Rainer Schimming (1996)

Discussiones Mathematicae Graph Theory

Similarity:

A special relational structure, called genealogical tree, is introduced; its social interpretation and geometrical realizations are discussed. The numbers $C_{n, k}$ of all abstract genealogical trees with exactly n+1 nodes and k leaves is found by means of enumeration of code words. For each n, the $C_{n, k}$ form a partition of the n-th Catalan numer Cₙ, that means $C_{n, 1} + C_{n, 2} + . . . + C_{n, n} = C ₙ$ .

The tree property at the double successor of a measurable cardinal κ with $2^{κ}$ large

Sy-David Friedman, Ajdin Halilović (2013)

Fundamenta Mathematicae

Similarity:

Assuming the existence of a λ⁺-hypermeasurable cardinal κ, where λ is the first weakly compact cardinal above κ, we prove that, in some forcing extension, κ is still measurable, κ⁺⁺ has the tree property and $2^{κ} = κ ⁺ ⁺ ⁺$ . If the assumption is strengthened to the existence of a θ -hypermeasurable cardinal (for an arbitrary cardinal θ > λ of cofinality greater than κ) then the proof can be generalized to get $2^{κ} = θ$ .

Trees with α-labelings and decompositions of complete graphs into non-symmetric isomorphic spanning trees

Michael Kubesa (2005)

Discussiones Mathematicae Graph Theory

Similarity:

We examine constructions of non-symmetric trees with a flexible q-labeling or an α-like labeling, which allow factorization of $K_{2 n}$ into spanning trees, arising from the trees with α-labelings.

Uniform distribution modulo one and binary search trees

Michel Dekking, Peter Van der Wal (2002)

Journal de théorie des nombres de Bordeaux

Similarity:

Any sequence $x = {(x_{k})}_{k = 1}^{\infty}$ of distinct numbers from [0,1] generates a binary tree by storing the numbers consecutively at the nodes according to a left-right algorithm (or equivalently by sorting the numbers according to the Quicksort algorithm). Let $H_{n} (x)$ be the height of the tree generated by $x_{1}, \dots, x_{n} .$ Obviously $\frac{log n}{log 2} - 1 \leq H_{n} (x) \leq n - 1 .$ If the sequences $x$ are generated by independent random variables having the uniform distribution on [0, 1], then it is well known that there exists $c$ > $0$ such that...

Spanning caterpillars with bounded diameter

Ralph Faudree, Ronald Gould, Michael Jacobson, Linda Lesniak (1995)

Discussiones Mathematicae Graph Theory

Similarity:

A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most $c n^{3 / 4}$ (at most n).

Metric spaces admitting only trivial weak contractions

Richárd Balka (2013)

Fundamenta Mathematicae

Similarity:

If (X,d) is a metric space then a map f: X → X is defined to be a weak contraction if d(f(x),f(y)) < d(x,y) for all x,y ∈ X, x ≠ y. We determine the simplest non-closed sets X ⊆ ℝⁿ in the sense of descriptive set-theoretic complexity such that every weak contraction f: X → X is constant. In order to do so, we prove that there exists a non-closed $F_{σ}$ set F ⊆ ℝ such that every weak contraction f: F → F is constant. Similarly, there exists a non-closed $G_{δ}$ set G ⊆ ℝ such that every weak...