On sequences of ±1's defined by binary patterns

David W. Boyd; Janice Cook; Patrick Morton

Displaying similar documents to “On sequences of ±1's defined by binary patterns”

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

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

Weak square sequences and special Aronszajn trees

John Krueger (2013)

Fundamenta Mathematicae

Similarity:

A classical theorem of set theory is the equivalence of the weak square principle $□_{μ} *$ with the existence of a special Aronszajn tree on μ⁺. We introduce the notion of a weak square sequence on any regular uncountable cardinal, and prove that the equivalence between weak square sequences and special Aronszajn trees holds in general.

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

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

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.

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.

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

Signpost systems and spanning trees of graphs

Ladislav Nebeský (2006)

Czechoslovak Mathematical Journal

Similarity:

By a ternary system we mean an ordered pair $(W, R)$ , where $W$ is a finite nonempty set and $R \subseteq W \times W \times W$ . By a signpost system we mean a ternary system $(W, R)$ satisfying the following conditions for all $x, y, z \in W$ : if $(x, y, z) \in R$ , then $(y, x, x) \in R$ and $(y, x, z) \notin R$ ; if $x \neq y$ , then there exists $t \in W$ such that $(x, t, y) \in R$ . In this paper, a signpost system is used as a common description of a connected graph and a spanning tree of the graph. By a ct-pair we mean an ordered pair $(G, T)$ , where $G$ is a connected graph and $T$ is a spanning tree of $G$ . If $(G, T)$ is a ct-pair, then by...

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