Uniform distribution modulo one and binary search trees

Michel Dekking; Peter Van der Wal

Displaying similar documents to “Uniform distribution modulo one and binary search trees”

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...

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...

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 ₙ$ .

Note about sequences of extrema $(A, 2 B)$ -edge coloured trees

Urszula Bednarz, Iwona Włoch (2017)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

In this paper we determine successive extremal trees with respect to the number of all $(A, 2 B)$ -edge colourings.

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.

On operators from separable reflexive spaces with asymptotic structure

Bentuo Zheng (2008)

Studia Mathematica

Similarity:

Let 1 < q < p < ∞ and q ≤ r ≤ p. Let X be a reflexive Banach space satisfying a lower- $ℓ_{q}$ -tree estimate and let T be a bounded linear operator from X which satisfies an upper- $ℓ_{p}$ -tree estimate. Then T factors through a subspace of ${(\sum F ₙ)}_{ℓ_{r}}$ , where (Fₙ) is a sequence of finite-dimensional spaces. In particular, T factors through a subspace of a reflexive space with an $(ℓ_{p}, ℓ_{q})$ FDD. Similarly, let 1 < q < r < p < ∞ and let X be a separable reflexive Banach space satisfying an asymptotic...

The tree property at both $ℵ_{ω + 1}$ and $ℵ_{ω + 2}$

Laura Fontanella, Sy David Friedman (2015)

Fundamenta Mathematicae

Similarity:

We force from large cardinals a model of ZFC in which $ℵ_{ω + 1}$ and $ℵ_{ω + 2}$ both have the tree property. We also prove that if we strengthen the large cardinal assumptions, then in the final model $ℵ_{ω + 2}$ even satisfies the super tree property.

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...

Compactness properties of weighted summation operators on trees

Mikhail Lifshits, Werner Linde (2011)

Studia Mathematica

Similarity:

We investigate compactness properties of weighted summation operators $V_{α, σ}$ as mappings from ℓ₁(T) into $ℓ_{q} (T)$ for some q ∈ (1,∞). Those operators are defined by $(V_{α, σ} x) (t) : = α (t) \sum_{s ⪰ t} σ (s) x (s)$ , t ∈ T, where T is a tree with partial order ⪯. Here α and σ are given weights on T. We introduce a metric d on T such that compactness properties of (T,d) imply two-sided estimates for $e ₙ (V_{α, σ})$ , the (dyadic) entropy numbers of $V_{α, σ}$ . The results are applied to concrete trees, e.g. moderately increasing, biased or binary trees and to weights...

Collisions of random walks

Martin T. Barlow, Yuval Peres, Perla Sousi (2012)

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

Similarity:

A recurrent graph $G$ has the infinite collision property if two independent random walks on $G$ , started at the same point, collide infinitely often a.s. We give a simple criterion in terms of Green functions for a graph to have this property, and use it to prove that a critical Galton–Watson tree with finite variance conditioned to survive, the incipient infinite cluster in $ℤ^{d}$ with $d \geq 19$ and the uniform spanning tree in $ℤ^{2}$ all have the infinite collision property. For power-law combs and spherically...

Trees and the dynamics of polynomials

Laura G. DeMarco, Curtis T. McMullen (2008)

Annales scientifiques de l'École Normale Supérieure

Similarity:

In this paper we study branched coverings of metrized, simplicial trees $F : T \to T$ which arise from polynomial maps $f : ℂ \to ℂ$ with disconnected Julia sets. We show that the collection of all such trees, up to scale, forms a contractible space $ℙ T_{D}$ compactifying the moduli space of polynomials of degree $D$ ; that $F$ records the asymptotic behavior of the multipliers of $f$ ; and that any meromorphic family of polynomials over $Δ^{*}$ can be completed by a unique tree at its central fiber. In the cubic case we give a...

Inequalities for Taylor series involving the divisor function

Horst Alzer, Man Kam Kwong (2022)

Czechoslovak Mathematical Journal

Similarity:

Let $T (q) = \sum_{k = 1}^{\infty} d (k) q^{k}, | q | < 1,$ where $d (k)$ denotes the number of positive divisors of the natural number $k$ . We present monotonicity properties of functions defined in terms of $T$ . More specifically, we prove that $H (q) = T (q) - \frac{log (1 - q)}{log (q)}$ is strictly increasing on $(0, 1)$ , while $F (q) = \frac{1 - q}{q} H (q)$ is strictly decreasing on $(0, 1)$ . These results are then applied to obtain various inequalities, one of which states that the double inequality $α \frac{q}{1 - q} + \frac{log (1 - q)}{log (q)} < T (q) < β \frac{q}{1 - q} + \frac{log (1 - q)}{log (q)}, 0 < q < 1,$ holds with the best possible constant factors $α = γ$ and $β = 1$ . Here, $γ$ denotes Euler’s constant. This refines a result of Salem, who...

The instability of nonseparable complete Erdős spaces and representations in ℝ-trees

Jan J. Dijkstra, Kirsten I. S. Valkenburg (2010)

Fundamenta Mathematicae

Similarity:

One way to generalize complete Erdős space $_{c}$ is to consider uncountable products of zero-dimensional $G_{δ}$ -subsets of the real line, intersected with an appropriate Banach space. The resulting (nonseparable) complete Erdős spaces can be fully classified by only two cardinal invariants, as done in an earlier paper of the authors together with J. van Mill. As we think this is the correct way to generalize the concept of complete Erdős space to a nonseparable setting, natural questions arise...

Shadow trees of Mandelbrot sets

Virpi Kauko (2003)

Fundamenta Mathematicae

Similarity:

The topology and combinatorial structure of the Mandelbrot set $ℳ^{d}$ (of degree d ≥ 2) can be studied using symbolic dynamics. Each parameter is mapped to a kneading sequence, or equivalently, an internal address; but not every such sequence is realized by a parameter in $ℳ^{d}$ . Thus the abstract Mandelbrot set is a subspace of a larger, partially ordered symbol space, $Λ^{d}$ . In this paper we find an algorithm to construct “visible trees” from symbolic sequences which works whether or not the sequence...

A direct solver for finite element matrices requiring $O (N log N)$ memory places

Vejchodský, Tomáš

Similarity:

We present a method that in certain sense stores the inverse of the stiffness matrix in $O (N log N)$ memory places, where $N$ is the number of degrees of freedom and hence the matrix size. The setup of this storage format requires $O (N^{3 / 2})$ arithmetic operations. However, once the setup is done, the multiplication of the inverse matrix and a vector can be performed with $O (N log N)$ operations. This approach applies to the first order finite element discretization of linear elliptic and parabolic problems in triangular...